文献类型：期刊文献

英文题名：Scheduling one batch processor subject to job release dates

作者：Liu, ZH; Yu, WC

机构：[1]E China Univ Sci & Technol, Inst Appl Math, Shanghai 200237, Peoples R China

年份：2000

卷号：105

期号：1-3

起止页码：129

外文期刊名：DISCRETE APPLIED MATHEMATICS

收录：;EI(收录号：2000095346385);WOS:【SCI-EXPANDED(收录号:WOS:000089203000008)】；

语种：英文

外文关键词：scheduling; batch processor; NP-hardness; heuristic

摘要：In this paper, we consider the problem of scheduling jobs with release dates on a single-batch processor in order to minimize the makespan. This problem is proved to be NP-hard even for the case with two distinct release dates. Then a pseudopolynomial algorithm is presented for the case with a fixed number of release dates. Finally, a greedy heuristic for the general problem is shown to have the best-performance bound 2. (C) 2000 Elsevier Science B.V. All rights reserved.