SOME BOUNDS ON APPROXIMATION ALGORITHMS FOR n/m/I/L_<MAX> AND n/2/F/L_<MAX> SCHEDULING PROBLEMS

In this paper, we analyze approximation algorithms for two types of scheduling problems. The first is the n jobs scheduling problem with due dates on m identical machines to minimize the maximum lateness. For this problem n/m/1/L_<max>, we propose two approximation algorithms and derive their worst case bounds. The second is the 2 × n flow shop scheduling problem with due dates to minimize the maximum lateness. For this problem n/2/F/L<max>, we first give a solvable case in the sense that the optimal schedule can be easily found. Then we again propose an approximation algorithm for general n/2/F/L_<max> and derive its worst case bound.