ANALYSIS OF HEURISTICS FOR PREEMPTIVE PARALLEL MACHINE SCHEDULING WITH BATCH SETUP TIMES
成果类型：
Article
署名作者：
MONMA, CL; POTTS, CN
署名单位：
University of Southampton
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.41.5.981
发表日期：
1993
页码：
981-993
关键词：
摘要：
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 less-than-or-equal-to 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 2 - 1/([M/2] + 1).