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.
In @cite_3 , an online variant of scheduling with setup times is considered. The authors propose a @math -competitive online algorithm for minimizing the maximum flow time if jobs arrive over time at one single machine.
@cite_3
2016555341
We address the problem of sequential single machine scheduling of jobs with release times, where jobs are classified into types, and the machine must be properly configured to handle jobs of a given type. The objective is to minimize the maximum flow time (time from release until completion) of any job. We consider this problem under the assumptions of sequence independent set-up times and item availability with the objective of minimizing the maximum flow time. We present an online algorithm that is O(1)-competitive, that is, always gets within a constant factor of optimal. We also show that exact offline optimization of maximum flow time is NP-hard.