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


NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time
Authors:JJ Yuan  TCE Cheng  CT Ng
Institution:1. Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People’s Republic of China;2. Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, People’s Republic of China
Abstract:Baker and Nuttle K.R. Baker, H.L.W. Nuttle, Sequencing independent jobs with a single resource, Naval Research Logistics Quarterly 27 (1980) 499–510] studied the following single-variable-resource scheduling problem: sequencing n jobs for processing by a single resource to minimize a function of job completion times, when the availability of the resource varies over time. When the objective function to be minimized is the total weighted completion time, Baker and Nuttle conjectured that the problem is NP-hard. We show in this note that the conjecture is true.
Keywords:Scheduling  Single-variable-resource  Total weighted completion time  NP-hardness
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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