Two-Machine Job-Shop Scheduling Problem to Minimize the Makespan with Uncertain Job Durations
Open Access
- 20 December 2019
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 13 (1) , 4
Abstract
We study two-machine shop-scheduling problems provided that lower and upper bounds on durations of n jobs are given before scheduling. An exact value of the job duration remains unknown until completing the job. The objective is to minimize the makespan (schedule length). We address the issue of how to best execute a schedule if the job duration may take any real value from the given segment. Scheduling decisions may consist of two phases: an off-line phase and an on-line phase. Using information on the lower and upper bounds for each job duration available at the off-line phase, a scheduler can determine a minimal dominant set of schedules (DS) based on sufficient conditions for schedule domination. The DS optimally covers all possible realizations (scenarios) of the uncertain job durations in the sense that, for each possible scenario, there exists at least one schedule in the DS which is optimal. The DS enables a scheduler to quickly make an on-line scheduling decision whenever additional information on completing jobs is available. A scheduler can choose a schedule which is optimal for the most possible scenarios. We developed algorithms for testing a set of conditions for a schedule dominance. These algorithms are polynomial in the number of jobs. Their time complexity does not exceed . Computational experiments have shown the effectiveness of the developed algorithms. If there were no more than 600 jobs, then all 1000 instances in each tested series were solved in one second at most. An instance with 10,000 jobs was solved in 0.4 s on average. The most instances from nine tested classes were optimally solved. If the maximum relative error of the job duration was not greater than , then more than of the tested instances were optimally solved. If the maximum relative error was equal to , then of the tested instances from the nine classes were optimally solved.
Keywords
This publication has 39 references indexed in Scilit:
- The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objectiveComputers & Operations Research, 2016
- Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability researchInternational Journal of Computer Integrated Manufacturing, 2009
- A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterionOperations Research Letters, 2008
- Johnson’s problem with stochastic processing times and optimal service levelEuropean Journal of Operational Research, 2006
- The two-machine stochastic flowshop problem with arbitrary processing time distributionsIIE Transactions, 1999
- Stochastically minimizing total flowtime in flowshops with no waiting spaceEuropean Journal of Operational Research, 1999
- Stochastically minimizing the makespan in two-machine flow shops without blockingEuropean Journal of Operational Research, 1999
- Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage ProductionManagement Science, 1995
- Two-machine ordered flowshop scheduling under random breakdownsMathematical and Computer Modelling, 1994
- On Johnson's Two-Machine Flow Shop with Random Processing TimesOperations Research, 1986