Skip to main content
SpringerLink
Log in

A heuristic MBLS algorithm for the two semi-online parallel machine scheduling problems with deterioration jobs

  • Published:
Journal of Shanghai University (English Edition)

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Mosheiov G. On flow shop scheduling with deteriorating jobs [R]. Working Paper, School of Business Administration, Hebrew University, Jerusalem, Israel, 1996.

    Google Scholar 

  2. Mosheiov G. Multi-machine scheduling with linear deterioration [J]. INFOR, 1996, 36: 205–214.

    Google Scholar 

  3. Mosheiov G. Complexity analysis of job-shop scheduling with deteriorating jobs [J]. Discrete Applied Mathematics, 2002, 117: 195–209.

    Article  Google Scholar 

  4. Kononov A. Scheduling problems with linear increasing processing times [C]// Operations Research Proceedings 1996, Brunswick. Berlin: Springer verlag, 1997: 90–94.

    Google Scholar 

  5. Hsieh Y C, Bricker D L. Scheduling linearly deteriorating jobs on multiple machines [J]. Computer and Industrial Engineering, 1997, 32(4): 727–734.

    Article  Google Scholar 

  6. Graham R L. Bounds on multiprocessing timing anomalies [J]. SIAM Journal on Applied Mathematics, 1969, 17(2): 416–429.

    Article  Google Scholar 

  7. He Y, Zhang G C. Semi on-line scheduling on two identical machines [J]. Computing, 1999, 62: 179–187.

    Article  Google Scholar 

  8. 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.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, College of Sciences, Shanghai University, Shanghai, 200444, P. R. China

    Cheng Ming-bao  (程明宝) & Sun Shi-jie  (孙世杰)

Authors
  1. Cheng Ming-bao  (程明宝)
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sun Shi-jie  (孙世杰)
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sun Shi-jie  (孙世杰).

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

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11741-007-0503-3

Keywords

2000 Mathematics Subject Classification

Search

Navigation