Multi-criteria re-entrant jobs scheduling problems using GA and AHP

• Main Author: Lin, Danping.
• Other Authors: Chen Chun-Hsien
• Format: Theses and Dissertations
• Language: English
• Published: 2013
• Subjects: DRNTU::Engineering::Manufacturing::Production management
• Online Access: http://hdl.handle.net/10356/51160
• Institution: Nanyang Technological University

The re-entrant scheduling problem came into prominence as a new type of scheduling problem in the past years. It is found in many production systems, particularly in high-tech industries such as semiconductor wafer fabrication and repairing companies. The principle characteristic of a re-entrant shop is that some jobs would visit a certain machine or set of machines more than once before completion. As these industries are characterized as capital intensive and competition imperative, a good understanding of the re-entrant shop and a better solution for the scheduling problem are crucial. The existing studies normally focus on a deterministic number of the re-entrant job and consider quantitative factors rather than a non-deterministic re-entrant job number and qualitative factors. However, in practical terms, the circumstance is more complicated. A more practical solution that can deal with dynamic re-entrant scheduling, as well as cover both qualitative and quantitative factors, is required. This thesis aims to provide a complete study of the re-entrant phenomenon and how it affects shop scheduling. It includes a review of past studies on re-entrant shop scheduling, comprising problem definition, problem classification and applied solutions. It provides solutions to the re-entrant flow shop scheduling problems. The strategies that have been employed to achieve these objectives are 1) the conceptualization of an integrated approach combining the genetic algorithm (GA) with analytical hierarchy process (AHP) where AHP works for GA’s selection procedure, and 2) the exploitation of different scenarios of re-entrant flow shop that includes bi-objective, multiple criteria and resource constraint. The validation of the integrated system is implemented in two models. The first model is named Hybrid GA/AHP model that captures the edges of GA and AHP. The model attempts to emulate the re-entrant phenomenon in the flow shop and automate the current practice of schedule generation. The validation is conducted in two experiments, firstly single GA is implemented for the re-entrant lines and later a new combination of GA and AHP is carried out. The second model is named Multi-level Encoding GA model that particularly explores the interdependency of re-entrant possibility and execution mode selection. The experiments are applied in the small-size problems and later extended to large-size problems after the design of the experiment.