Page - X - in Algorithms for Scheduling Problems

for a schedulewhichprovidesoptimal—or close tooptimal—objective functionvalues for themost possible scenariosamongother schedules. To this end, thedesiredschedulemustdominatea larger number of the schedules. Thismaybepossible if the schedule has the largest optimality (stability) box. Theauthorsaddressasingle-machineschedulingproblemwithuncertaindurationsof thegiven jobs. Theobjective function is theminimizationof thesumof the jobcompletion times. Thestability approach is applied to the considered uncertain scheduling problem using the relative perimeter of the optimality box as a stabilitymeasure of the optimal job permutation. The properties of the optimality box are investigated andused to develop algorithms for constructing job permutations thathave the largest relativeperimetersof theoptimalitybox. Chapter3addressesaschedulingproblemwhere jobswithgivenreleasetimesandduedatesmust beprocessedonasinglemachine. Theprimarycriterionofminimizing themaximumlatenessof the given jobsmakes thisproblemstronglyNP-hard. Theauthorproposesageneralalgorithmicscheme to minimize the maximum lateness of the given jobs, with the secondary criterion of minimizing themaximum completion time of the given jobs. The problem of finding a Pareto optimal set of solutionswith the above two criteria is also stronglyNP-hard. The author states the properties of the dominance relation alongwith conditionswhen aPareto optimal set of solutions can be found in polynomial time. The proven properties of the dominance relation and the proposed general algorithmic scheme provide a theoretical background for constructing an implicit enumeration algorithmthatrequiresanexponentialrunningtimeandapolynomialapproximationalgorithm.The latterallowsfor thegenerationofaParetosub-optimal frontierwithafairbalancebetweentheabove twocriteria. Thenext three chaptersdealwithflowshopand job shopschedulingproblemsaswell as theirhybrid (flexible)variants,often inspiredbyreal-lifeapplications. In Chapter 4, the maximization of the number of just-in-time jobs in a permutation flow shop scheduling problem is considered. A mixed integer linear programming model to represent the problem as well as solution approaches based on enumerative and constructive heuristics are proposed and computationally implemented. The ten constructive heuristics proposed produce good-quality results, especially for large-scale instances in reasonable time. The twobest heuristics obtainnear-optimalsolutions,andtheyarebetter thanadaptationsof theclassicNEHheuristic. Chapter 5 addresses a scheduling problem in an actual environment of the tortilla industry. A tortilla is a Mexican flat round bread made of maize or wheat often served with a filling or topping. It is the most consumed food product in Mexico, so efficient algorithms for their production are of great importance. Since the underlying hybrid flow-shop problem is NP-hard, the authors focus on suboptimal scheduling solutions. They concentrate on a complexmulti-stage, multi-product,multi-machine, andbatchproductionenvironment consideringcompletion timeand energy consumption optimization criteria. The proposed bi-objective algorithm is based on the non-dominated sorting genetic algorithm II (NSGA-II). To tune it, the authors apply a statistical analysisofmulti-factorial variance. Abranch-and-boundalgorithmisused toevaluate theheuristic algorithm. Todemonstrate thepractical relevanceof the results, theauthorsexamined their solution onrealdata. Chapter 6 is devoted to the effectiveness in managing disturbances and disruptions in railway traffic networks, when they inevitably do occur. The authors propose a heuristic approach for solving the real-time train traffic re-schedulingproblem. This problem is interpreted as a blocking job-shopschedulingproblem, andahybridizationof themixedgraphandalternativegraph isused formodeling the infrastructureand trafficdynamicsonamesoscopic level. Aheuristic algorithmis x