Consider the problem in which n jobs that are classified into k types are to be scheduled on m identical machines without preemption. A machine requires a proper setup taking s time units before processing jobs of a given type. The objective is to minimize the makespan of the resulting schedule. We design and analyze an approximation algorithm that runs in time polynomial in n, m and k and computes a solution with an approximation factor that can be made arbitrarily close to 3 2.
The scheduling problem considered in this paper is a generalization of the classical problem of scheduling jobs on identical machines without preemption and in which setup times are equal to @math . This problem has been extensively studied in theoretical research and PTASs with runtimes that are linear in the number @math of jobs are known for objective functions such as minimizing (maximizing) the maximum (minimum) completion time or sum of completion times @cite_7 @cite_10 . If the number @math of machines is constant, even FPTASs exist @cite_2 .
@cite_10 @cite_7 @cite_2
2093979815 1977276352 1992734168
The problem of scheduling a set of n jobs on m identical machines so as to minimize the makespan time is perhaps the most well-studied problem in the theory of approximation algorithms for NP-hard optimization problems. In this paper the strongest possible type of result for this problem, a polynomial approximation scheme, is presented. More precisely, for each e, an algorithm that runs in time O (( n e) 1 e 2 ) and has relative error at most e is given. In addition, more practical algorithms for e = 1 5 + 2 - k and e = 1 6 + 2 - k , which have running times O ( n ( k + log n )) and O ( n ( km 4 + log n )) are presented. The techniques of analysis used in proving these results are extremely simple, especially in comparison with the baroque weighting techniques used previously. The scheme is based on a new approach to constructing approximation algorithms, which is called dual approximation algorithms, where the aim is to find superoptimal, but infeasible, solutions, and the performance is measured by the degree of infeasibility allowed. This notion should find wide applicability in its own right and should be considered for any optimization problem where traditional approximation algorithms have been particularly elusive. We discuss scheduling problems with m identical machines and n jobs where each job has to be assigned to some machine. The goal is to optimize objective functions that solely depend on the machine completion times. As a main result, we identify some conditions on the objective function, under which the resulting scheduling problems possess a polynomial time approximation scheme. Our result contains, generalizes, improves, simplifies, and unifies many other results in this area in a natural way. Exact and approximate algorithms are presented for scheduling independent tasks in a multiprocessor environment in which the processors have different speeds. Dynamic programming type algorithms are presented which minimize finish time and weighted mean flow time on two processors. The generalization to m processors is direct. These algorithms have a worst-case complexity which is exponential in the number of tasks. Therefore approximation algorithms of low polynomial complexity are also obtained for the above problems. These algorithms are guaranteed to obtain solutions that are close to the optimal. For the case of minimizing mean flow time on m -processors an algorithm is given whose complexity is O( n log mn ).