An Evolutionary Algorithm Approach for Assembly Job Shop Scheduling with Lot Streaming Technique

This dissertation, "An Evolutionary Algorithm Approach for Assembly Job Shop Scheduling With Lot Streaming Technique" by Tse-chiu, Wong, 黃資超, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled "An Evolutionary Algorithm Approach for Assembly Job Shop Scheduling with Lot Streaming Technique" Submitted by Wong Tse Chiu for the degree of Doctor of Philosophy at The University of Hong Kong in December 2007 Considerable efforts have been made by many manufacturing practitioners and researchers in recent years to solve Production and Scheduling Problems (PSPs). To solve PSPs, decision makers need to optimize the system objectives and satisfy the system constraints within a practical time limit. In this connection, a number of evolutionary approaches have been developed in this field. The Job Shop Scheduling Problem (JSSP) is one of the better-known PSPs, in which jobs are processed on machines in distinct orders. To solve a JSSP, the job processing sequence on each machine should be determined with respect to the objective functions. In fact, the classical JSSP is simplified by a number of system assumptions. One assumption is ii that a job cannot be split. Generally, a job is defined as a batch of identical items and it can only be transferred to the next machine once the whole batch has been processed. If a job is not allowed to be split, its next operation cannot be started even some items of the batch have already been processed. To relax this assumption, decision makers eventually need to decide for each job: (1) Whether the job will be split; (2) the sub-job number; and (3) the size of each sub-job. This technique is called Lot Streaming (LS). LS is defined as the process of splitting jobs into smaller sub-jobs so that successive operations of the same job can be overlapped on different machines. Nevertheless, insufficient LS models have been dedicated to JSSP. Another assumption of the classical JSSP is that there is no assembly stage. In other words, each job in JSSP is independent. If an assembly stage is appended to JSSP, the problem then becomes the Assembly Job Shop Scheduling Problem (AJSSP). In this study, the application of LS is for the first time extended to the AJSSP. As the potential of employing LS to the AJSSP has not been fully studied, an intelligent evolutionary algorithm is proposed and examined. The application of LS to JSSP is investigated first. Accordingly, an evolutionary algorithm is proposed. The research problem is divided into Sub-Problem One (SP1) and Sub-Problem Two (SP2). SP1 is defined as the determination of three LS conditions and SP2 is defined as JSSP after LS conditions have been determined. Different system parameters such as 3-level processing time range, 5-level setup time range, and 4-level system congestion index are examined. The computational results are obtained and discussed. Next, the application of LS is extended to the AJSSP. In iii this connection, the problem is considered in three parts: (a) Part I, on a simplified AJSSP; (b) Part II, on an AJSSP with 4-level part sharing; and (c) Part III, on an AJSSP with 4-level part sharing, 4-level system congestion index, and 2-level resource constraints. Correspondingly, the evolutionary algorithm is modified and improved in terms of optimization powers and computational effort. The computational results are obtained and discussed. ____________________________________________________________________ iv DOI: 10.5353/th_b3963446 Subjects: Genetic algorithms