Answers are grounded in this paper and cite their sources.
The problem of preemptively scheduling N jobs on M identical parallel machines to minimize the maximum completion time is considered. Jobs are divided into B batches and a setup time on a machine is necessary whenever there is a switch from processing a job in one batch to a job in another batch. Setup times are assumed to depend only on the batch of the job to be scheduled next. Two types of heuristics are proposed and analyzed. The first type uses list scheduling for complete batches and then splits batches between selected pairs of machines. It has a time requirement of O(N + (M + B) log(M + B)). Furthermore, for a certain class of problems which includes the case that each batch contains a single job, it has a worst-case performance ratio of 3/2 − 1/(4M − 4) when M ≤ 4 and of 5/3 − 1/M when M is a multiple of 3 and M > 3. The second type of heuristic uses a procedure which resembles McNaughton's preemptive scheduling algorithm. It requires O(N) time and has a worst-case performance ratio of [Formula: see text].
No takes yet. Share an insight, caveat, or question.
Monma et al. (1993) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: