TOC based procedure for job-shop scheduling | |
| Author | Chompoonoot Kasemset |
| Call Number | AIT Diss. no.ISE-09-07 |
| Subject(s) | Scheduling (Management) Production scheduling |
| Note | A dissertation submitted in partial fulfillment of the requirements for the Industrial Engineering and Management, School of Engineering and Technology |
| Publisher | Asian Institute of Technology |
| Series Statement | Dissertation ; no. ISE-09-07 |
| Abstract | This study presents an application of Theory of Constraints (TOC) in job-shop environment. The proposed procedure is divided into three parts following the first three steps from the five steps of TOC implementation; bottleneck identification, bottleneck exploitation and bottleneck subordination. The first step starts with the bottleneck identification via simulation technique. The aim of this step is to identify the real system bottleneck under job-shop environment that is difficult to handle due to the complicated relationship of each product that has its own sequence of operations. Bottleneck identification starts by running the simulation model of existing system to collect data on the utilization of each machine/process and the time between arrivals and departures of each machine/process. Three factors, the machine/process utilization, the process utilization factor (ρ) and the product bottleneck rate (Rb) are used to identify potential bottleneck candidates. The real bottleneck is the machine that has high values of both machine/process utilization and the utilization factor and low value for the bottleneck rate. The simulation is used again to evaluate the solution by increasing capacity of a bottleneck candidate. If no improvement in throughput is observed, then the station is not a bottleneck and the procedure is repeated again by increasing the capacity of another bottleneck candidate. After the true bottleneck is identified, bottleneck exploitation and subordination are carried out. The aim of the bottleneck exploitation is to maximize the utilization of the bottleneck while the subordination step optimizes other resources to support the bottleneck. This study proposed the way to create the job schedule to satisfy both the bottleneck exploitation and subordination. The mathematical model of the job-shop scheduling problem is presented and the solutions are obtained using three approaches; (1) A two-step approach, (2) A bi-level multi-objective mathematical model and (3) A meta-heuristic; Particle Swarm Optimization (PSO) algorithm. The first approach is called “Two-step approach for job-shop scheduling based on TOC policy”. The proposed procedure is divided into two steps. The first step starts with the creation of an initial job schedule. The aim of this step is to minimize idle time on the bottleneck following the concept of bottleneck exploitation by maximizing the bottleneck utilization. The result from the first step is the job sequence on the bottleneck(s) that minimize the idle time on the bottleneck station. The second step generates the final schedule by improving other performance measure while maintaining the maximum use of the bottleneck utilization. In this step, the final schedule is generated by optimizing other performance measures for the whole system. In this study, three factors; maximum completion time (Cmax), maximum tardiness (Tmax) and maximum earliness (Emax) are considered individually as a single objective in each scenario. Moreover, the additional set of constraint is used to fix the bottleneck’s job sequence derived from the first step. The second step is designed based on the bottleneck subordination concept that optimizes other non-bottleneck resources while providing support to the bottleneck. In addition, the concept of transfer lot is adopted in this procedure to reduce the waiting time and the completion time for the overall system which directly affects the system bottleneck utilization. The concept of transfer lot is included as the constraint on earliest starting time for each job on each machine to allow overlapped operations in the proposed procedure. The extension of the first approach is called the bi-level multi-objective mathematical model for job-shop scheduling based on TOC concept. The work describes the decisions involved in the implementation of TOC in job-shop environment as a bi-level multi-objective mathematical model. On the first level, the decision is made by minimizing idle time on the bottleneck to generate the initial schedule but the second level decision is developed to improve the multi-objective of those three performance measures while still maintaining the bottleneck sequence obtained from the first level decision. Similarly, the concept of transfer lot is adopted in this approach. The schedule obtained from this approach is more realistic because it can exploit the use of bottleneck capability (minimum idle time at bottlenecks), and at the same time try to improve other performance measures (satisfy multi-objective of each performance measure). The third procedure is a PSObased procedure for the bi-level multi-objective TOC based job-shop scheduling problem. PSO method is applied to simplify the decision process in the bi-level programming problem. Instead of solving this problem by a two-step process, the proposed PSO based procedure simplifies the solution method by simultaneously providing solutions for the objective of each level. In addition, during the schedule generation process, a specific factor called “Earliest Start Time” is considered. This factor is calculated when transfer lot is applied following TOC concept to allow the operations to overlap. Additionally, the job-shop case applied in this study is different from a classical job-shop since the machine set up time and product demands are also considered to make the model practical to use in the real situation. The numerical examples for both single and multiple bottleneck cases are given to demonstrate how this approach works. A simulation model is built with Arena simulation software for the bottleneck identification step. The commercially available optimizer, the LINGO version 5 and version 10 software packages are used to solve the examples for the small size job-shop scheduling problems. A large problem is also provided to test the effectiveness of the proposed PSO based procedure. |
| Year | 2009 |
| Corresponding Series Added Entry | Asian Institute of Technology. Dissertation ; no. ISE-09-07 |
| Type | Dissertation |
| School | School of Engineering and Technology (SET) |
| Department | Department of Industrial Systems Engineering (DISE) |
| Academic Program/FoS | Industrial Systems Engineering (ISE) |
| Chairperson(s) | Voratas Kachitvichyanukul; |
| Examination Committee(s) | Do Ba Khang ;Huynh Trung Luong; |
| Scholarship Donor(s) | Royal Thai Goverment Fellowship; |
| Degree | Thesis (Ph.D.) - Asian Institute of Technology, 2009 |