IIE Transactions · 1999 · 27 citations · 16 references
Natural SciencesComputer ScienceIndustrial EngineeringAlgorithmsOptimizationSchedulingCombinatorial OptimizationMachine SchedulingScheduling TheoryStochastic OptimizationStochastic ProgrammingStochastic SchedulingExpected Completion Time MinimizationExponential Time ComplexityPermutation SchedulesProject Completion GuaranteesStochastic Makespan MinimizationTwo-machine Flow Shop SchedulingTwo-machine SchedulingWorst-case Complexity
We treat the two-machine flowshop problem with the objective of minimizing the expected makespan when the jobs possess stochastic durations of arbitrary distributions. We make three contributions in this paper: (1) we propose an exact approach with exponential worst-case time complexity. We also propose approximations which are computationally modest in their requirements. Experimental results indicate that our procedure is within less than 1 % of the optimum; and (2) we provide a more elementary proof of the bounds on the project completion time based on the concepts of ‘control networks’; and (3) we extend the ‘reverse search’ procedure of Avis and Fukuda [1[ to the context of permutation schedules.
16
Scheduling: Theory, Algorithms, and Systems
Michael Pinedo · IIE Transactions · 1996 · 6.3K citations
Reverse search for enumeration
David Avis, Komei Fukuda · Discrete Applied Mathematics · 1996 · 760 citations