哈尔滨工业大学学报（英文版）2005，Vol.12Issue(3)：309-313,5.
Algorithms for single machine scheduling with availability constraints
Algorithms for single machine scheduling with availability constraints
LI Bo 1SHI Bing-xin 1SHEN Bin 1LIU Ji-cheng1
作者信息
- 1. Dept. of Electronics and Information Engineering, Huazhong University of Science & Technology, Wuhan 430074, China
- 折叠
摘要
Abstract
It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling problem into a variant of the variable-sized bin packing problem, put forward eight bin packing algorithms adapted from the classic one-dimensional bin packing problem and investigated their performances from both of the worst-case and the average-case scenarios. Analytical results show that the worst-case performance ratios of the algorithms are not less than 2. Experimental results for average cases show that the Best Fit and the Best Fit Decreasing algorithm outperform any others for independent and precedence-constrained jobs respectively.关键词
Single machine scheduling/availability constraints/variable-sized bin packing/algorithmsKey words
Single machine scheduling/availability constraints/variable-sized bin packing/algorithms分类
数理科学引用本文复制引用
LI Bo,SHI Bing-xin,SHEN Bin,LIU Ji-cheng..Algorithms for single machine scheduling with availability constraints[J].哈尔滨工业大学学报（英文版）,2005,12(3):309-313,5.
