Abstract
The combination of online or semi-online with deterioration jobs has never been researched in scheduling problems. In this paper, two semi-online parallel machine scheduling problems with linear deterioration processing time are considered. In the first problem, it is assumed that the deterioration rates of jobs are known in an interval, that is, b j ∊ [0, α], where 0 < α ⩽ 1 and b j denotes the linear deterioration rate. In the second problem, it is assumed that the largest deterioration rate of jobs is known in advance, that is, \(b_{\max } = \mathop {\max }\limits_{1 \leqslant j \leqslant n} \{ b_j \} \). For each of the two problems, a heuristic MBLS algorithm is worked out and its worst-case ratio is analyzed. At the same time, the worst-case ratio of the list (LS) algorithm is investigated and it is proved that all the ratios are tight.
Similar content being viewed by others
References
Mosheiov G. On flow shop scheduling with deteriorating jobs [R]. Working Paper, School of Business Administration, Hebrew University, Jerusalem, Israel, 1996.
Mosheiov G. Multi-machine scheduling with linear deterioration [J]. INFOR, 1996, 36: 205–214.
Mosheiov G. Complexity analysis of job-shop scheduling with deteriorating jobs [J]. Discrete Applied Mathematics, 2002, 117: 195–209.
Kononov A. Scheduling problems with linear increasing processing times [C]// Operations Research Proceedings 1996, Brunswick. Berlin: Springer verlag, 1997: 90–94.
Hsieh Y C, Bricker D L. Scheduling linearly deteriorating jobs on multiple machines [J]. Computer and Industrial Engineering, 1997, 32(4): 727–734.
Graham R L. Bounds on multiprocessing timing anomalies [J]. SIAM Journal on Applied Mathematics, 1969, 17(2): 416–429.
He Y, Zhang G C. Semi on-line scheduling on two identical machines [J]. Computing, 1999, 62: 179–187.
He Y. Semi on-line scheduling problems for maximizing the minimum machine completion time [J]. Acta Mathematicae Applicatae Sinica (English Series), 2001, 17(1): 107–113.
Author information
Authors and Affiliations
Corresponding author
About this article
Cite this article
Cheng, Mb., Sun, Sj. A heuristic MBLS algorithm for the two semi-online parallel machine scheduling problems with deterioration jobs. J. of Shanghai Univ. 11, 451–456 (2007). https://doi.org/10.1007/s11741-007-0503-3
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/s11741-007-0503-3