Metaheuristics for the selection and scheduling of jobs with time-dependent durations

Le Roux, Gavin James (2017-12)

Thesis (MCom)--Stellenbosch University, 2017.

Thesis

ENGLISH SUMMARY : A scheduling problem that determines an optimal sequence of jobs to be performed on a single machine is considered. A set of available jobs is presented to management of which a subset should be selected to maximise the total weighted profit. This is because of the schedule horizon that is limited to a maximum makespan, resulting in a pool of rejected jobs that may possibly be processed at a later stage. Each job is associated with a list of possible fractions that it requires of the machine during its processing. As a result, jobs can be processed simultaneously on the machine. Furthermore, once a job has completed its processing, there is a likelihood that the machine needs to be cleaned up and prepared for the following jobs to be processed. Setup times and setup costs are therefore associated with each ordered pair of jobs. Additionally, the processing time of a job depends on the time at which it starts processing. Lastly, certain jobs are prohibited from starting its processing directly after the processing of another given set of jobs at a specified set of time periods. The five characteristics of the considered scheduling problem are therefore batch scheduling, time-dependent processing times, dependent setup times, job selection and precedence constraints. Applications of the problem may include the testing of aircraft and missile Hights on a multipurpose test range, the scheduling of resources to underprivileged communities using multiple vehicles as well as the scheduling of jobs in a busy vehicle maintenance and repair facility. A variety of metaheuristics were developed to solve the scheduling problem when jobs in a batch need to start at the same time. Three metaheuristics that use moves and/or neighbourhoods were developed, namely variable neighbourhood search (V NS), tabu search (TS) and a genetic algorithm (GA-Il) in which a chromosome is defined as a sequence of batches. Moreover, three metaheuristics that utilise decoding schemes were implemented. These algorithms are particle swarm optimisation (PSO), cuckoo search (CS) and a genetic algorithm (GA-I) in which a chromosome is defined as a string of floating point numbers. The non-identical start time batch (NSTB) algorithm is executed after a set of solutions were obtained by one of the metaheuristics. This is an algorithm that was designed to address the problem that jobs in a batch are allowed to start at different times. The set of solutions in the NSTB algorithm is evolved into a population of schedules that is presented to management to decide which trade-offs should be made when selecting a schedule to implement. There are four different steps in each iteration, namely the moving of single jobs within a batch, the merging of batches, the moving of multiple jobs within a batch and the insertion of a job into a batch. A total of 150 test cases were generated for the purpose of comparing the algorithms with one another, because real-world data are not available. Statistical hypothesis testing was performed using omnibus tests to test whether there is an overall significant difference between the profits of the algorithms for each test case. The Friedman test was used as a non-parametric statistical test with post hoc tests that included the Wilcox-on signed rank test and the sign test. Furthermore, the Welch analysis of variance (ANOVA) test was used as a parametric alternative with post hoc tests that included the Tamhane's T2, Dunnett's T3 and Games-Howell tests. Upon completion of these tests, it is recommended to use either VNS or TS for test cases in the elementary difficulty group and TS for test cases of an intermediate or challenging nature. There is a mere 0.3% increase in the average profit when VNS is used compared to TS for elementary test cases. For intermediate test cases, TS performs about 8.7% better than VNS as well as 9.8% and 12.4% better than GA-I and GA-Il, respectively. For challenging test caMS, TS most notably performs 16.6% and 16.2% better than GA-I and GA-Il, respectively, and better than PSO. CS is the worst performing metaheuristic in all difficulty groups.

AFRIKAANSE OPSOMMING : In hierdie tesis word 'n skeduleringsprobleem beskou wat 'n optimale volgorde van take op 'n enkele masjien bepaal. 'n Groep van beskikbare take word gegee en die bestuur moet dan 'n subversameling van take selekteer om wins te maksimeer. Dit is nodig omdat die skedule oor 'n eindige tyshorison opgelos moet word en daar dus 'n poel van oorskottake ontstaan wat in 'n latere skedule ingesluit kan word. Elke taak het 'n versameling moontlike breuke van die masjien wat dit in beslag kan neem. Take kan dus gelyktydig (in parallel) op die masjien geprosesseer word. Wanneer 'n taak afgehandel is, is daar 'n moontlikheid dat die masjien voorberei moet word vir 'n volgende taak. Daar is dus 'n opstelkoste vir elke onderlinge paar van die take. Die uitvoertyd van 'n taak is amanklik van sy begintyd. Laastens het sekere take ook beperkings in terme van wanneer hulle relatief tot ander take uitgevoer kan word. Die vyf eienskappe van die skeduleringsprobleem wat beskou word, is dus trosskedulering, tyd amanklike opsteltye, volgorde afhanklike opsteltye, taakseleksie en Toepassings van hierdie tipe skeduleringsprobleme is die skedulering van vliegtuig- en missieltoetse op 'n toetsbaan, die skedulering van hulpbronne aan behoeftige gemeenskappe met verskeie voertuie asook die skedulering van take by 'n besige werkswinkel wat voertuie versien. 'n Verskeidenheid van metaheuristieke is ontwikkel om die take te skeduleer in trosse waarin die take gelyktydig moet begin. Drie metaheuristieke wat skuiwe en/of omgewings gebruik is ontwikkel, naamlik 'n veranderbare-omgewing soektog (VNS), 'n taboe-soektog (NS), en 'n genetiese algoritme (GA-Il), waarin 'n chromosoom gedefinieer word as die volgorde van die trosse. Verder is drie metaheuristieke ontwikkel wat 'n dekoderingskema gebruik. Hierdie algoritmes is deeltjie-swerm-optimering (PSO), koekoe-soektog (CS) en 'n genetiese algoritme (GA-I) waarin 'n chromosoom gedefinieer word as 'n string reöle getalle. Die nie-identiese- begintyd-tros-algoritme (NSTB) word gebruik nadat 'n versameling oplossing bereken is om take op verskillende tye in die trosse te laat begin. Die versameling oplossings wat die NSTB verskaf, word gebruik om 'n populasie van skedules te skep waaruit bestuur kan kies tussen die afruilings om 'n mees gewensde skedule te vind. NSTB gebruik Vier stappe, naamlik die skuif van 'n enkele taak, samevoeging van trosse, die skuif van 'n groep take in 'n tros en die invoeging van 'n taak in 'n tros. 'n Totaal van 150 probleme is gegenereer (omdat daar nie regte wareld data bestaan nie) om algoritmes met mekaar te vergelyk. Statistiese hipotesetoetsing is uitgevoer met behulp van omnibus toetse om te bepaal of daar 'n statisties beduidende verskil tussen die wins van die verskillende algoritmes is. Die Friedmantoets is gebruik as 'n nie-parametriese statistiese toets saam met post hoc toetse wat insluit die Wilcuxon-teken-rang-toets en die teken toets. Die Welch analise van variansie (ANOVA) toets is gebruik as 'n parametriese alternatief met die post hoc toetse wat insluit Tamhane's T2, Dunnett's T3 en Games-Howell-toetse. Die aanbeveling, na afloop van hierdie toetse, is om V NS en TS te gebruik vir die klein probleme en TS vir die middel en moeiliker probleemklasse. Daar is 'n geringe 0.3% toename in die gemiddelde wins indien VNS gebruik word teenoor TS gedurende die maklike probleme. Vir die middelprobleme vaar TS ongeveer 8.7% beter as VNS sowel as 9.8% en 12.4% beter as GA-I en GA-Il, onderskeidelik. Vir die moeilike probleme vaar TS die beste en doen 16.6% en 16.2% beter as GA-I en GA-Il, onderskeidelik. TS vaar 00k 19% beter as PSO. CS vaar die swakste oor al die probleemklasse.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/102852
This item appears in the following collections: