Page - IX - in Algorithms for Scheduling Problems

Preface to”AlgorithmsforSchedulingProblems” Optimal scheduling is an important area of operations research, as it has both theoretical and practical aspects. It is clear that efficient algorithms aremost desirable for practical applications, sincemost real-world schedulingproblemshave large sizes but require fast decisions. Due to this, practitioners oftenprefer to use rather simple algorithmswhichprovide schedules thatmaybe far fromoptimalwithrespect to theirquality. This book is based on a Special Issue entitled ”Algorithms for Scheduling Problems”. In the Call for Papers, we invited prospective authors to submit their latest research in the area of the development of scheduling algorithms. We were looking for new and innovative approaches to solvingschedulingproblemsexactlyorapproximately.High-qualitypapersweresolicitedtoaddress both theoretical and practical issues of scheduling algorithms. Submissions were welcome both for traditional scheduling problems, aswell as for newapplications. Wementioned that potential topics included,butwerenot limited to, sequencing insingle-stagesystemsandmulti-stagesystems withadditional constraints suchas setup timesor costs, precedenceconstraints, batching, lot sizing, resource constraints, etc., also including single- or multi-criteria objectives and a broad range of schedulingproblemsinemergingapplicationssuchassports,healthcare,andenergymanagement. Inresponse to theCall forPapers,weselectedelevensubmissions,allofwhichareofhighquality, reflecting the stable and growing interest in the area of effective and efficient algorithms to solve problems for real-worldproductionplanningandscheduling. All submissionshavebeen reviewed byatleastthreeexpertsintheoperationsresearcharea.Eachchapterofthisbookcontainsoneofthese selectedpapers.Wehope thatpractical schedulerswillfindsomeinteresting theoretical ideas in this Special Issue,while researcherswillfindnewpracticaldirections for implementing their scheduling algorithms. In the following,wegivesomeshortcommentsontheparticularchapters. The first three chapters deal with single-machine problems. Chapter 1 presents a new greedy insertion heuristic with a multi-stage filtering mechanism for energy-efficient single-machine scheduling. Theauthorswrote that inorder to improveenergyefficiencyandmaintain the stability of the power grid, time-of-use (TOU) electricity tariffs have beenwidely used around theworld, which bring both opportunities and challenges to energy-efficient scheduling problems. Although methodsbasedondiscrete-timeorcontinuous-timemodelshavebeensuggestedforaddressingthese problems, they are deficient in solution quality or time complexity, especially when dealingwith large-sizeinstances. Forsuchproblems,anewgreedyinsertionheuristicalgorithmwithamulti-stage filteringmechanism including coarse granularity andfine granularity filtering is developed in this paper. Toshowtheeffectivenessoftheproposedalgorithm,arealcasestudyisprovided,anddetailed computational resultsaregiven. Chapter 2 is devoted to a stability approach to scheduling problemswith uncertain parameters. Thestabilityapproachcombinesastabilityanalysisof theoptimalscheduleswithrespect topossible variations of the job processing times, amulti-stage decision framework, and the solution concept of aminimal dominant set of schedules,which optimally covers all possible scenarios (i.e., for any fixedscenario, thisminimaldominantsetcontainsat leastoneoptimalschedule). Incontrast tofuzzy, stochastic, androbust approaches, theaimof the stabilityapproach is to construct a schedulewhich remainsoptimal for themostpossible scenarios. If thereexistsascheduledominating theotherones forallpossiblescenarios, thenthisscheduleremainsoptimalforeachscenario,whichmayberealized. Thismaybepossible if the level of uncertainty is not high. Otherwise, adecision-makermust look ix