Metaheuristics for the selection and scheduling of jobs with time-dependent durations
Date
2017-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
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.
Description
Thesis (MCom)--Stellenbosch University, 2017.
Keywords
Metaheuristics, Production scheduling, Time delay systems, UCTD