文献类型：期刊文献

英文题名：Scheduling groups of unit length jobs on two identical parallel machines

作者：Liu, Zhaohui[1]; Yu, Wenci[1]; Cheng, T.C. Edwin[2]

机构：[1]Hong Kong Polytech Univ, Off Vice President Res & Postgrad Studies, Kowloon, Hong Kong;[2]E China Univ Sci & Technol, Inst Appl Math, Shanghai 200237, Peoples R China

年份：1999

卷号：69

期号：6

起止页码：275

外文期刊名：INFORMATION PROCESSING LETTERS

收录：;EI(收录号：1999304690907);WOS:【SSCI(收录号:WOS:000080038900003)，SCI-EXPANDED(收录号:WOS:000080038900003)】；

语种：英文

外文关键词：group technology; scheduling; algorithms

摘要：The problem of scheduling groups of unit length jobs with group sub-letting on two identical parallel machines to minimize the total completion time is known to be NP-hard. In this paper, we present a pseudopolynomial-time algorithm for the problem, thus establishing that the problem is NP-hard in the ordinary sense. We also show that the problem remains NP-hard even for the case with any fixed positive set-up time. (C) 1999 Elsevier Science B.V. All rights reserved.