首页 | 本学科首页   官方微博 | 高级检索  
     


Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem
Authors:C.T. Ng  T.C.E. ChengJ.J. Yuan
Affiliation:a Department of Management, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
b Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People's Republic of China
Abstract:We consider the single machine multi-operation jobs total completion time scheduling problem. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a set-up time. A job completes when all of its operations have been processed. The objective is to minimize the sum of the job completion times. In the literature, the computational complexity of this problem is posed as open. We show that the problem is strongly NP-hard even when the set-up times are common and the processing time of each operation is 0 or 1.
Keywords:Scheduling   Single machine multi-operation jobs
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号