Browsing by Author "Le Roux, Gavin James"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
- ItemMetaheuristics for the selection and scheduling of jobs with time-dependent durations(Stellenbosch : Stellenbosch University, 2017-12) Le Roux, Gavin James; Visagie, Stephanus Esterhuyse; Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Logistics. Logistics.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.