Static Multi-processor Scheduling with Ant Colony Optimisation & Local Search Graham Ritchie Master of Science Artificial Intelligence School of Informatics University of Edinburgh 2003 Abstract Efficient multi-processor scheduling is essentially the problem of allocating a set of computational jobs to a set of processors to minimise the overall execution time. There are many variations of this problem, most of which are NP-hard, so we must rely on heuristics to solve real world problem instances. This dissertation describes several novelapproaches using the ant colony optimisation (ACO) meta-heuristic and local search techniques, including tabu search, to two important versions of the prob- lem: the static scheduling of independent jobs onto homogeneous and heterogeneous processors. Finding good schedules for jobs allocated on homogeneous processors is an im- portantconsiderationifefficientuseisto bemadeofamultiple-CPUmachine,forex- ample. An ACO algorithm to solve this problem is presented which, when combined with a fast local search procedure, can outperform traditional approaches on bench- mark problems instances for the closely related bin packing problem. The algorithm cannotcompete,however,withmoremodernspecialisedtechniques. Scheduling jobs onto hetereogeneous processorsis a more general problem which has potential applications in domains such as grid computing. A fast local search procedure for this problem is described which can quickly and effectively improve solutions built by other techniques. When used in conjunction with a well-known heuristic, Min-min, it can find shorter schedules on benchmark problems than other solutiontechniquesfoundintheliterature,andinsignificantlylesstime. Atabusearch algorithm is also presented which can improve on solutions found by the local search procedure but takes longer. Finally a hybrid ACO algorithm which incorporates the local and tabu searches is described which outperforms both, but takes significantly longerto run. i Acknowledgements Iwouldliketothankmy supervisor,John Levine,forhishelpandadvicethrough- outthisproject. IwouldalsoliketothankTracyBraunandHowardSiegelforsharing their results with me, and Jon Schoenfield for providing lower bound proofs for some testproblemsusedin thisdissertation. ii Declaration I declare that this thesis was composed by myself, that the work contained herein is myownexceptwhereexplicitlystatedotherwiseinthetext,andthatthisworkhasnot beensubmittedforanyotherdegreeorprofessionalqualification exceptasspecified. (GrahamRitchie) iii Table of Contents 1 Introduction 1 2 An introductiontoantcolonyoptimisationand localsearch techniques 4 2.1 Biological inspiration . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Frominspirationto algorithm . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Localsearch mechanisms . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3.1 ACOandlocal search . . . . . . . . . . . . . . . . . . . . . 10 2.3.2 Tabu search . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.3 ACOandtabu search . . . . . . . . . . . . . . . . . . . . . . 12 2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Homogeneousmulti-processor scheduling 13 3.1 Aformal definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Comparisonwiththe BPP . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Current solutiontechniques . . . . . . . . . . . . . . . . . . . . . . . 15 3.3.1 MPSP solutiontechniques . . . . . . . . . . . . . . . . . . . 15 3.3.2 BPPsolutiontechniques . . . . . . . . . . . . . . . . . . . . 17 3.3.3 Ahybridapproach . . . . . . . . . . . . . . . . . . . . . . . 20 3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4 ApplyingACOandlocalsearch tothe homogeneousMPSP 22 4.1 Definingthe pheromonetrail . . . . . . . . . . . . . . . . . . . . . . 22 4.2 Theheuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.3 Updatingthe pheromonetrail . . . . . . . . . . . . . . . . . . . . . . 24 iv 4.4 Thefitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.5 Buildingasolution . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.6 Addinglocal search . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.7 Establishingparametervalues . . . . . . . . . . . . . . . . . . . . . 30 4.8 Experimentalresults . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.8.1 Comparisonwithotherapproaches . . . . . . . . . . . . . . . 33 4.8.2 Comparingthe componentsofthe algorithm . . . . . . . . . . 44 4.8.3 AnalysisofanexampleACOrun . . . . . . . . . . . . . . . 45 5 Heterogeneous multi-processor scheduling 47 5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.2 Simulation model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.3 Current solutiontechniques . . . . . . . . . . . . . . . . . . . . . . . 51 5.3.1 Greedyheuristics . . . . . . . . . . . . . . . . . . . . . . . . 51 5.3.2 Tabu search . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.3.3 Evolutionaryapproaches . . . . . . . . . . . . . . . . . . . . 54 5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6 ApplyingACOandlocalsearch tothe heterogeneous MPSP 56 6.1 Definingthe pheromonetrail . . . . . . . . . . . . . . . . . . . . . . 56 6.2 Theheuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.3 Thefitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.4 Updatingthe pheromonetrail . . . . . . . . . . . . . . . . . . . . . . 58 6.5 Buildingasolution . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 6.6 Addinglocal search . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6.7 Tabu search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.8 Establishingparametervalues . . . . . . . . . . . . . . . . . . . . . 64 6.9 Experimentalresults . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.9.1 Comparisonwithotherapproaches . . . . . . . . . . . . . . . 67 6.9.2 Comparingthe componentsofthe algorithm . . . . . . . . . . 73 6.9.3 AnalysisofanexampleACOrun . . . . . . . . . . . . . . . 75 v 7 Conclusions& FurtherWork 78 7.1 Further work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 7.1.1 Improvementstothe currentapproaches . . . . . . . . . . . . 78 7.1.2 Dealing withjobprecedence . . . . . . . . . . . . . . . . . . 79 7.1.3 Dynamicscheduling . . . . . . . . . . . . . . . . . . . . . . 82 7.2 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 A Example outputfrom anAntMPS forhomogeneousprocessors run 86 B Example outputfrom anAntMPS forheterogeneous processors run 89 Bibliography 92 vi Chapter 1 Introduction Theproblemofefficiently schedulingcomputationaljobsonmultipleprocessorsisan important consideration when attempting to make effective use of a multi-processor system such as a computational grid or a multiple CPU machine. The multi processor scheduling problem (MPSP) can be formulated in several ways, taking into account different constraints. Two important variations include scheduling independent jobs ontohomogenousandheterogeneousprocessors. The homogeneous MPSP is defined here as the problem of scheduling a set of n independent jobs each of which has an associated running time, onto a set of m iden- tical processors such that the overallexecution time is minimised. The heterogeneous MPSP is identical except that the rule that the processors must be identical is relaxed, and it is assumed that each job can take a different time to execute on each of the availableprocessors. There is a distinction to be made between dynamic and static multi-processor scheduling. Dynamicschedulingdealswithjobsasandwhentheyarriveatthe sched- uler and can deal with changing numbers of processors. This dissertation is, however, onlyconcernedwithstaticscheduling,andsoall necessaryinformationaboutthejobs and processors, e.g. running times, and the number and nature of the processors, are assumedtobeknowna priori. In most of its practical formulations, including the two just described, the MPSP is known to be NP-hard [Garey andJohnson,1979], so exact solution methods are unfeasibleformostprobleminstancesandheuristicapproachesmustthereforebeem- 1 Chapter1. Introduction 2 ployed to find solutions. Heuristics are by their nature non-exhaustive, and so there is often scope for different approaches to better previous solution methods accord- ing to some metric or other (e.g. execution speed, quality of solutions etc.) Tradi- tional approaches to the MPSP are as varied as the different formulations of the prob- lem,but includefast, simpleheuristics(seee.g.[Braun etal.,2001]), tabu search(e.g. [Thiesen,1998]), evolutionary approaches (e.g. [CorcoranandWainwright,1994]), and modern hybridalgorithms that consolidatethe advantagesof variousdifferent ap- proaches(e.g.[Alvimetal.,2002]). In this dissertation I describe two closely related approaches to these two ver- sions of the MPSP combining the Ant Colony Optimisation (ACO) meta-heuristic with local search methods, including tabu search. The ACO meta-heuristic was first described by Dorigo in his PhD thesis [Dorigo,1992], and was inspired by the ability of real ant colonies to efficiently organise the foraging behaviour of the colony using external chemical pheromone trails acting as a means of communica- tion. ACO algorithms have since been widely employed on many NP-hard combi- natorial optimisation problems, including many problems related to the MPSP such asbinpacking[Ducatelle,2001,LevineandDucatelle,2003]andjobshopscheduling [vanderZwaanandMarques,1999]. However,they havenot previously been applied tothetwoMPSPvariationsdescribedabove. Localsearchmethodsencompassawide array of approaches to many optimisation problems, and have been shown to be very effectivewhenusedincombinationwithanACOapproach[DorigoandStu¨tzle, 2002]. Theapproachdescribedinthisdissertationforthehomogeneousproblemperforms wellintermsofthequalityofsolutionsfoundwhencompared,usingbenchmarkprob- lems,totraditionalsolutiontechniquesfoundintheliterature,butcanoftentakelonger torun. Theapproachissuccessful,but cannotoutperformstate oftheartalgorithms. Experimental results for the heterogeneousproblem indicate that the approach de- scribed here is particularly well suited to this problem. A range of techniques are proposed which can outperform other solution techniques found in the literature both interms ofthe qualityofsolutionsfound andthetimetakentofindthem. ThereareofcourseotherpossiblevariationsoftheversionoftheMPSPthanthose studiedhere, forexamplethe problemofschedulingjobswithprecedenceconstraints, Chapter1. Introduction 3 and a discussion of possible further applications is provided in chapter 7. It is hoped however that the fundamental ideas presented here could be applied to such related problems. It should be noted that although the terminology of computational jobs and pro- cessors is used throughout this dissertation, the problem can be considered a general schedulingproblem. Theapproachesdiscussedherecouldthereforebeappliedtoother scheduling tasks, such as scheduling of industrial jobs in a factory. As long as the salientfeaturesoftheproblemareclearlyidentifiable,suchasajobhasadefiniterun- ning time, or a machine can process jobs at a certain speed, the techniques described herecould beapplied. This dissertation is organised as follows. Chapter 2 introduces the ACO meta- heuristic in detail, discussing its biological inspiration and subsequent technical evo- lution, and provides an introduction to the local search concepts used in this study. Chapter 3 provides a more detailed explanation of the homogeneous MPSP studied in thisdissertation anddiscussessomeimportant existingsolutiontechniques. Chapter4 thendescribeshowACOandlocalsearchtechniqueswereappliedtothehomogeneous problem,andprovidesexperimentalresults. Theheterogeneousproblemisintroduced indetailinchapter5alongwithsomecurrentsolutiontechniques. Chapter6describes how ACO and local search were applied to this second problem and provides experi- mental results. Chapter 7 concludes with a summary of the project, its successes and shortcomings and discusses possible future work on approaching other variations of the MPSPwithACOtechniques.