In this thesis, the Job Shop Scheduling Problem (JSSP) is the problem of interest. The classical JSSP is well-known as an NP-hard problem. Although with current computational capabilities, the small problems are solvable using deterministic methods, it is out of reach when they are larger in size. The complexity of JSSP is further increased when process interruptions, such as machine breakdown and/or machine unavailability, are introduced. Over the last few decades, several stochastic algorithms have been proposed to solve JSSPs. However, none of them are suitable for all kinds of problems. Genetic and Memetic algorithms have proved their effectiveness in these regards, because of their diverse searching behavior. In this thesis, we have developed one genetic algorithm and three different Memetic Algorithms (MAs) for solving JSSPs. Three priority rules are designed, namely partial re-ordering, gap reduction and restricted swapping, and these have been used as local search techniques in designing our MAs. We have solved 40 well-known benchmark problems and compared the results obtained with some of the established algorithms available in the literature. Our algorithm clearly outperforms those established algorithms. For better justification of the superiority of MAs over GA, we have performed statistical significance testing (Student's t-test). The experimental results show that MA, as compared to GA, not only significantly improves the quality of solutions, but also reduces the overall computation. We have extended our work by proposing an improved local search technique, shifted gap-reduction (SGR), which improves the performance of MAs when tested with the relatively difficult test problems. We have also modified the new algorithm to accommodate JSSPs with machine unavailability and also developed a new reactive scheduling technique to re-optimize the schedule after machine breakdowns. We have considered two scenarios of machine unavailability. Firstly, where the unavailability information is available in advance (predictive), and secondly, where the information is known after a real breakdown (reactive). We show that the revised schedule is mostly able to recover if the interruptions occur during the early stages of the schedules. We also confirm that the effect of a single continuous breakdown has more impact compared to short multiple breakdowns, even if the total durations of the breakdowns are the same. Finally, for convenience of implementation, we have developed a decision support system (DSS). In the DSS, we have built a graphical user interface (GUI) for user friendly data inputs, model choices, and output generation. This DSS tool will help users in solving JSSPs without understanding the complexity of the problem and solution approaches, as well as will contribute in reducing the computational and operational costs.
| Identifer | oai:union.ndltd.org:ADTP/258703 |
| Date | January 2009 |
| Creators | Hasan, S. M. Kamrul, Engineering & Information Technology, Australian Defence Force Academy, UNSW |
| Publisher | Awarded by:University of New South Wales - Australian Defence Force Academy. Engineering & Information Technology |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | http://unsworks.unsw.edu.au/copyright |
Page generated in 0.002 seconds