Skip to main content
SpringerLink
Log in

Computational complexity of the single processor makespan minimization problem with release dates and job-dependent learning

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

In this paper, we analyse the single processor maximum completion time (makespan) minimization problem with distinct release dates of jobs and the sum-of-processing time-based learning effect. We prove that the considered problem is strongly NP-hard, if, in addition to jobs with the same learning ratio, there are jobs with constant job processing times. Such jobs are not affected by learning and model, for instance, required system upgrades or training courses.

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

  • Biskup D (1999). Single–machine scheduling with learning considerations. European Journal of Operational Research 115 (1): 173–178.

    Article  Google Scholar 

  • Biskup D (2008). A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research 188 (2): 315–329.

    Article  Google Scholar 

  • Buşoniu L, Babuška R and De Schutter B (2008). A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics—Part C: Applications and Reviews 38 (2): 156–172.

    Article  Google Scholar 

  • Chen P, Wu C-C and Lee W-C (2006). A bi-criteria two-machine flowshop scheduling problem with a learning effect. Journal of the Operational Research Society 57 (9): 1113–1125.

    Article  Google Scholar 

  • Cheng TCE, Wu C-C and Lee W-C (2008). Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects. Information Sciences 178 (11): 2476–2487.

    Article  Google Scholar 

  • Cheng TCE, Lai P-J, Wu C-C and Lee W-C (2009). Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations. Information Sciences 179 (18): 3127–3135.

    Article  Google Scholar 

  • Garey MR and Johnson DS (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman: San Francisco, CA.

    Google Scholar 

  • Graham RL, Lawler EL, Lenstra JK and Rinnooy Kan AHG (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics 5 (2): 287–326.

    Article  Google Scholar 

  • Hsu C-J, Yang S-J and Yang D-L (2011). Two due date assignment problems with position-dependent processing time on a single-machine. Computers & Industrial Engineering 60 (4): 796–800.

    Article  Google Scholar 

  • Janiak A and Rudek R (2011). A note on the learning effect in multi-agent optimization. Expert Systems with Applications 38 (5): 5974–5980.

    Article  Google Scholar 

  • Kerzner H (1998). Project Management: A System Approach to Planning, Scheduling, and Controlling. John Wiley & Sons, Inc.: New York.

    Google Scholar 

  • Koulamas C and Kyparisis GJ (2007). Single-machine and two-machine flowshop scheduling with general learning functions. European Journal of Operational Research 178 (2): 402–407.

    Article  Google Scholar 

  • Kuo W-H and Yang D-L (2011). A note on due-date assignment and single-machine scheduling with deteriorating jobs and learning effects. Journal of the Operational Research Society 62 (1): 206–210.

    Article  Google Scholar 

  • Lai P-J and Lee W-C (2011). Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects. Omega 39 (5): 467–471.

    Article  Google Scholar 

  • Lee W-C, Wu C-C and Li M-F (2009). A single-machine bi-criterion learning scheduling problem with release times. Expert Systems with Applications 36 (7): 10295–10303.

    Article  Google Scholar 

  • Lee W-C, Wu C-C and Hsu P-H (2010). A single-machine learning effect scheduling problem with release times. Omega 38 (1–2): 3–11.

    Article  Google Scholar 

  • Mosheiov G and Sidney JB (2003). Scheduling with general job-dependent learning curves. European Journal of Operational Research 147 (3): 665–670.

    Article  Google Scholar 

  • Okołowski D and Gawiejnowicz S (2010). Exact and heuristic algorithms for parallel-machine scheduling with DeJong's learning effect. Computers & Industrial Engineering 59 (2): 272–279.

    Article  Google Scholar 

  • Rudek R (2012). Some single-machine scheduling problems with the extended sum-of-processing-time based aging effect. International Journal of Advanced Manufacturing Technology 59 (1–4): 299–309.

    Article  Google Scholar 

  • Rudek R (2013). On single processor scheduling problems with learning dependent on the number of processed jobs. Applied Mathematical Modelling 37 (3): 1523–1536.

    Article  Google Scholar 

  • Wang J-B (2009). Single machine scheduling with a time-dependent learning effect and deteriorating jobs. Journal of the Operational Research Society 60 (4): 583–586.

    Article  Google Scholar 

  • Wang J-B and Wang M-Z (2012). Worst-case analysis for flow shop scheduling problems with an exponential learning effect. Journal of the Operational Research Society 63 (1): 130–137.

    Article  Google Scholar 

  • Wang J-B and Xia Z-Q (2005). Flow-shop scheduling with a learning effect. Journal of the Operational Research Society 56 (11): 1325–1330.

    Article  Google Scholar 

  • Whiteson S and Stone P (2004). Adaptive job routing and scheduling. Engineering Applications of Artificial Intelligence 17 (7): 855–869.

    Article  Google Scholar 

  • Wu C-C (2005). A makespan study of the two-machine flowshop scheduling problem with a learning effect. Journal of Statistics and Management Systems 8 (1): 13–25.

    Article  Google Scholar 

  • Wu C-C and Lee W-C (2009). Single-machine and flowshop scheduling with a general learning effect model. Computers & Industrial Engineering 56 (4): 1553–1558.

    Article  Google Scholar 

  • Wu C-C and Liu C-L (2010). Minimizing the makespan on a single machine with learning and unequal release times. Computers & Industrial Engineering 59 (3): 419–424.

    Article  Google Scholar 

  • Yang D-L and Kuo W-H (2007). Single-machine scheduling with an actual time-dependent learning effect. Journal of the Operational Research Society 58 (10): 1348–1353.

    Article  Google Scholar 

  • Yang S-J and Yang D-L (2010). Single-machine group scheduling problems under the effects of deterioration and learning. Computers & Industrial Engineering 58 (4): 754–758.

    Article  Google Scholar 

  • Yelle LE (1979). The learning curve: Historical review and comprehensive study. Decision Science 10 (2): 302–328.

    Article  Google Scholar 

Download references

Acknowledgements

We are grateful to the Editor and the Referees for their valuable comments on an earlier version of our paper. This work was supported by the Polish National Science Centre under grant no. DEC-2012/05/D/HS4/01129.

Author information

Authors and Affiliations

  1. Wrocław University of Economics, Wrocław, Poland

    R Rudek

Authors
  1. R Rudek
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to R Rudek.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rudek, R. Computational complexity of the single processor makespan minimization problem with release dates and job-dependent learning. J Oper Res Soc 65, 1170–1176 (2014). https://doi.org/10.1057/jors.2013.19

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2013.19

Keywords

Search

Navigation