Maximizing service level in a β-robust job shop scheduling model

Document Type : Research Paper


1 Department of Industrial Engineering, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran.

2 Research group for Operations Management, KU Leuven, Belgium.


In the realm of scheduling problems, different sources of uncertainty such as probabilistic durations of jobs or stochastic breakdowns of machines can arise. Given this, one highly desirable characteristic of an intelligent schedule is to bring better punctuality with less efficiency-loss because a dominant factor in customer appreciation is punctuality. It is also one of the most intangible topics for managers when a due date is predetermined to deliver jobs. In this paper, we address the β-robust job shop scheduling problem when the processing time of each operation is a normal random variable. We intend to minimize the deviation of makespan from a common due date for all jobs which corresponds to maximizing the service level, defined as probability of the makespan not exceeding the given due date. We develop a branch-and-bound algorithm to solve the problem. Using a set of generated benchmark instances, the performance of the developed algorithm has been evaluated.


Main Subjects

Adams J, Balas E and Zawack D (1988). The shifting bottleneck procedure for job-shop scheduling. Management Science 34: 391-401.
Alidaee B and Panwalkar SS (1993). Single stage minimumabsolute lateness problem with a common due date on non-identicalmachines. Journal of the Operational ResearchSociety 44: 29–36.
Applegate D and Cook W (1991). A computational study of job-shop scheduling. ORSA Journal of Computing 3: 149-156.
Brucker P, Jurisch B and Kramer A (1994). The job-shop problem and immediate selection. Annals of Operations Research 50: 73-114.
Carlier J and Pinson E (1989). An algorithm for solving the job-shop problem. Management Science 35: 164-176.
Daniels RL and Carrillo JE (1997). Beta-Robust scheduling for single-machine systems with uncertain processing times. IIE Transactions 29: 977-985.
Golenko-Ginzburg D and Gonik A (2002). Optimal job-shop scheduling with random operations and cost objectives. International Journal of Production Economics 76: 147-154.
Graham RL, Lawler EL, Lenstra JK and RinnooyKan AHG (1979). Optimization and approximation in deterministic sequencing and scheduling theory: a survey. Annals of Discrete Mathematics 5: 287-326.
Lenstra JK, RinnooyKan AHG and Brucker P (1977). Complexity of machine scheduling problems. In: P.L. Hammer, E.L. Johnson, B.H. Korte& G.L. Nemhauser, Studies in integer programming (Vol. 1, pp. 343-362). North-Holland, Amsterdam: Annals of Discrete Mathematics.
Lin S W, Chou S Y and Ying K C (2007). A sequential exchange approach for minimizing earliness–tardiness penalties of single-machine scheduling with a common due date. European Journal of Operational Research 177: 1294-1301.
Luh PB, Cheng D and Thakur LS (1999). An effective approach for job shop scheduling with uncertain processing requirements. IEEE Transactions on Robotics and Automation 15: 328–339.
Malcolm DG, Roseboom JH, Clark CE ,Fazar W (1959). Application of a Technique for Research and Development Program Evaluation. Operations Research 7(5): 646-669.
Pardalos P, Shylo O, Vazacopoulos A (2010). Solving job shop scheduling problems utilizing the properties of backbone and “big valley”. Computational Optimization and Applications 47: 61-76.
Pinedo ML (2014). Scheduling: theory, algorithms, and systems. Springer.
Ranjbar M and NajafianRazavi M (2012). A hybrid metaheuristic for concurrent layout and scheduling problem in a job shop environment. Advanced Manufacturing Technology 62: 1249-1260.
Ranjbar M, Davari M and Leus R (2012a). Two branch-and-bound algorithms for the robust parallel machine scheduling problem. Computers & Operations Research 39: 1652-1660.
Ranjbar M, Khalilzadeh M, Kianfar F, Etminani K (2012b). An optimal procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem. Computers & Industrial Engineering 62: 264-270.
Roy B and Sussmann B (1964). Les problemesd'ordonnancement avec contraintesdisjonctives. In: Note D. S. 9. Paris: SEMA.
Sarin SC, Nagarajan B, Liao L (2014). Stochastic scheduling: expectation-variance analysis of a schedule. Cambridge University Press.
Singer M and Pinedo M (1998). A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops. IIE Transactions 30: 109-118.
Spanos AC, Ponis ST, Tatsiopoulos IP, Christou IT and Rokou E (2014). A new hybrid parallel genetic algorithm for the job-shop scheduling problem. International Transaction in Operational Research 21: 479-499.
Tavakkoli-Moghaddam R, Jolai F, Vaziri F, Ahmed PK and Azaron A (2005). A hybrid method for solving stochastic job shop scheduling problem. Applied Mathematics and Computation 170: 185-206.
Tuong NH, Soukhal A, Billaut JC (2010). A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines. European Journal of Operational Research 202: 646-653.
Wu CW, Brown KN and Beck CJ (2009). Scheduling with uncertain durations: modeling beta-robust scheduling with constraints. Computers & Operations Research 36: 2348-2356.
Zhang CY, Li PG, Rao YQ and Guan ZL (2008). A very fast TS/SA algorithm for the job shop scheduling problem. Computers & Operations Research 35: 282-294.