Skip to main content
SpringerLink
Log in

A branch-and-bound approach for the single machine maximum lateness stochastic scheduling problem to minimize the value-at-risk

  • Published:
Flexible Services and Manufacturing Journal Aims and scope Submit manuscript

Abstract

The research in the field of robust scheduling aims at devising schedules which are not sensitive—to a certain extent—to the disruptive effects of unexpected events. Nevertheless, the protection of the schedule from rare events causing heavy losses is still a challenging aim. The paper presents a novel approach for protecting the quality of a schedule by assessing the risk associated to the different scheduling decisions. The approach is applied to a stochastic scheduling problem with a set of jobs to be sequenced on a single machine. The release dates and processing times of the jobs are generally distributed independent random variables, while the due dates are deterministic. A branch-and-bound approach is taken to minimise the value-at-risk of the distribution of the maximum lateness. The viability of the approach is demonstrated through a computational experiment and the application to an industrial problem in the tool making industry.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  • Agrawal MK, Elmaghraby SE (2001) On computing the distribution function of the sum of independent random variables. Comput Oper Res 28(5):473–483

    Article  MathSciNet  MATH  Google Scholar 

  • Alfieri A, Tolio T, Urgo M (2011) A project scheduling approach to production planning with feeding precedence relations. Int J Prod Res 49(4):995–1020

    Article  Google Scholar 

  • Alfieri A, Tolio T, Urgo M (2012) A two-stage stochastic programming project scheduling approach to production planning. The International Journal of Advanced Manufacturing Technology 62(1–4):279–290

    Article  Google Scholar 

  • Artigues C, Leus R, Talla Nobibon F (2013) Robust optimization for resource-constrained project scheduling with uncertain activity durations. Flex Serv Manuf J 25(1):175–205

    Article  Google Scholar 

  • Artzner P, Delbaen F, Eber J-M, Heath D (1999) Coherent measures of risk. Math Financ 9(3):203–228

    Article  MathSciNet  MATH  Google Scholar 

  • Atakan S, Bülbül K, Noyan N (2016) Minimizing value-at-risk in single-machine scheduling. Ann Oper Res 248:25–73

    Article  MathSciNet  MATH  Google Scholar 

  • Attia E-A, Duquenne P, Le-Lann J-M (2014) Considering skills evolutions in multi-skilled workforce allocation with flexible working hours. Int J Prod Res 52(15):4548–4573

    Article  Google Scholar 

  • Baker KR, Su ZS (1974) Sequencing with due dates and early start times to minimize tardiness. Naval Res Logist Q 21:171–176

    Article  MathSciNet  MATH  Google Scholar 

  • Baker KR, Trietsch D (2009) Safe scheduling: setting due dates in single-machine problems. Eur J Oper Res 196(1):69–77

    Article  MathSciNet  MATH  Google Scholar 

  • Baker KR, Trietsch D (2014) Safe scheduling. In: INFORMS Tutorials in Operations Research, pp 79–101

  • Benmansour R, Allaoui H, Artiba A (2012) Stochastic single machine scheduling with random common due date. Int J Prod Res 50(13):3560–3571

    Article  Google Scholar 

  • Bob++ (2012) A framework to solve combinatorial optimization problems. http://www.prism.uvsq.fr/~blec/bobpp/

  • Boost (2013) Boost C++ libraries. http://www.boost.org

  • Burdett RL, Kozan E (2014) Performance profiling for predictive train schedules. J Rail Transp Plan Manag 4:98–114

    MATH  Google Scholar 

  • Burdett RL, Kozan E, Strickland C (2012) A practical approach for identifying expected solution performance and robustness in operation research applications. ASOR Bull 31(2):1–28

    Google Scholar 

  • Cai X, Zhou X (2005) Single-machine scheduling with exponential processing times and general stochastic cost functions. J Global Optim 31(2):317–332

    Article  MathSciNet  MATH  Google Scholar 

  • Cai X, Wang L, Zhou X (2007) Single-machine scheduling to stochastically minimize maximum lateness. J Sched 10(4):293–301

    Article  MathSciNet  MATH  Google Scholar 

  • Cao Q, Patterson JW, Griffin TE (2001) On the operational definition of processing time uncertainty. Int J Prod Res 39(13):2833–2849

    Article  MATH  Google Scholar 

  • Carlier J (1982) The one-machine sequencing problem. Eur J Oper Res 11:42–47

    Article  MathSciNet  MATH  Google Scholar 

  • Chandra C, Liu Z, He J, Ruohonen T (2014) A binary branch and bound algorithm to minimize maximum scheduling cost. Omega 42:9–15

    Article  Google Scholar 

  • Chang C-S, Yao DD (1993) Rearrangement, majorization and stochastic scheduling. Math Oper Res 18(3):658–684

    Article  MathSciNet  MATH  Google Scholar 

  • De P, Ghosh JB, Wells CE (1992) Expectation-variance analysis of job sequences under processing time uncertainty. Int J Prod Econ 28(3):289–297

    Article  Google Scholar 

  • Djerrah A, Le Cun B, Cung V.-D, Roucairol C (2006) Bob++: framework for solving optimization problems with branch-and-bound methods. In: 2006 15th IEEE international symposium on high performance distributed computing, pp 369–370

  • Fang C, Kolisch R, Wang L, Mu C (2015) An estimation of distribution algorithm and new computational results for the stochastic resource-constrained project scheduling problem. Flex Serv Manuf J 27(4):585–605

    Article  Google Scholar 

  • Gafarov ER, Dolgui A, Werner F (2014) A new graphical approach for solving single-machine scheduling problems approximately. Int J Prod Res 52(13):3762–3777

    Article  Google Scholar 

  • Grabowski J, Nowicki E, Zdrzałka S (1986) A block approach for single-machine scheduling with release dates and due dates. Eur J Oper Res 26:278–285

    Article  MathSciNet  MATH  Google Scholar 

  • Kellerer H (2004) Minimizing the maximum lateness. In: J. Y.-T. Leung (ed) Handbook of scheduling: algorithms, models and performance analysis. Computer & information science series. Chapman & Hall/CRC, USA

    Google Scholar 

  • Lenstra J, Kan AR, Brucker P (1977) Complexity of machine scheduling problems. Ann Discret Math 1:343–362

    Article  MathSciNet  MATH  Google Scholar 

  • Liu Z (2010) Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints. Comput Oper Res 37:1537–1543

    Article  MathSciNet  MATH  Google Scholar 

  • Ma C, Wong WK (2010) Stochastic dominance and risk measure: a decision-theoretic foundation for VaR and C-VaR. Eur J Oper Res 207(2):927–935

    Article  MathSciNet  MATH  Google Scholar 

  • Makris S, Chryssolouris G (2010) Customer’s behaviour modelling for manufacturing planning. Int J Comput Integr Manuf 23(7):619–629

    Article  Google Scholar 

  • Mogre R, Wong CY, Lalwani CS (2014) Mitigating supply and production uncertainties with dynamic scheduling using real-time transport information. Int J Prod Res 52(17):5223–5235

    Article  Google Scholar 

  • Mourtzis D, Doukas M, Psarommatis F (2012) Design and planning of decentralised production networks under high product variety demand. Procedia CIRP 3(1):293–298

    Article  Google Scholar 

  • Nonaka Y, Erdos G, Kis T, Nakano T, Váncza J (2012) Scheduling with alternative routings in CNC workshops. CIRP Ann Manuf Technol 61(1):449–454

    Article  Google Scholar 

  • Pinedo ML (2008) Scheduling—theory, algorithms, and systems. Springer, New York

    MATH  Google Scholar 

  • Radke AM, Tolio T, Tseng MM, Urgo M (2013) A risk management-based evaluation of inventory allocations for make-to-order production. CIRP Ann Manuf Technol 62(1):459–462

    Article  Google Scholar 

  • Rockafellar RT, Uryasev S (2002) Conditional value-at-risk for general loss distributions. J Bank Financ 26(7):1443–1471

    Article  Google Scholar 

  • Ross SM (1983) Stochastic processes, 2nd edn. Holden Day, Amsterdam

    MATH  Google Scholar 

  • Sarin S, Nagarajan B, Jain S, Liao L (2009) Analytic evaluation of the expectation and variance of different performance measures of a schedule on a single machine under processing time variability. J Comb Optim 17(4):400–416

    Article  MathSciNet  MATH  Google Scholar 

  • Scholz-Reiter B, Hildebrandt T, Tan Y (2013) Effective and efficient scheduling of dynamic job shops—combining the shifting bottleneck procedure with variable neighbourhood search. CIRP Ann Manuf Technol 62(1):423–426

    Article  Google Scholar 

  • Shaked M, Shanthikumar JG (2007) Stochastic orders. Springer series in statistics. Springer, New York

    Book  MATH  Google Scholar 

  • Tolio T, Urgo M (2007) A rolling horizon approach to plan outsourcing in manufacturing-to-order environments affected by uncertainty. CIRP Ann Manuf Technol 56(1):487–490

    Article  Google Scholar 

  • Tolio T, Urgo M (2013) Design of flexible transfer lines: a case-based reconfiguration cost assessment. J Manuf Syst 32(2):325–334

    Article  Google Scholar 

  • Tolio T, Urgo M, Váncza J (2011) Robust production control against propagation of disruptions. CIRP Ann Manuf Technol 60(1):489–492

    Article  Google Scholar 

  • Wu X, Zhou X (2008) Stochastic scheduling to minimize expected maximum lateness. Eur J Oper Res 190(1):103–115

    Article  MathSciNet  MATH  Google Scholar 

  • Yin Y, Wu W-H, Cheng TCE, Wu C-C (2014) Due-date assignment and single-machine scheduling with generalised position-dependent deteriorating jobs and deteriorating multi-maintenance activities. Int J Prod Res 52(8):2311–2326

    Article  Google Scholar 

  • Zhou X, Cai X (1997) General stochastic single-machine scheduling with regular cost functions. Math Comput Modell 26(3):95–108

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This research has been developed in the framework of the XVII Executive Programme of Scientific and Technological Cooperation between the Republic of Hungary and the Republic of Italy and GINOP-2.3.2-15-2016-00002 Grant.

Author information

Authors and Affiliations

  1. Department of Mechanical Engineering, Politecnico di Milano, Milano, Italy

    M. Urgo

  2. EPIC Center of Excellence for Production Informatics and Control, Institute for Computer Science and Control, Hungarian Academy of Sciences, Budapest, Hungary

    J. Váncza

  3. Department of Manufacturing Science and Technology, Budapest University of Technology and Economics, Budapest, Hungary

    J. Váncza

Authors
  1. M. Urgo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. Váncza
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. Urgo.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Urgo, M., Váncza, J. A branch-and-bound approach for the single machine maximum lateness stochastic scheduling problem to minimize the value-at-risk. Flex Serv Manuf J 31, 472–496 (2019). https://doi.org/10.1007/s10696-018-9316-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10696-018-9316-z

Keywords

Search

Navigation