FLOW SHOP SCHEDULING WITH SYNCHRONOUS AND ASYNCHRONOUS TRANSPORTATION TIMES
Open Access
- Author:
- Huang, Kwei-Long
- Graduate Program:
- Industrial Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- May 16, 2008
- Committee Members:
- Jose Antonio Ventura, Committee Chair/Co-Chair
Arunachalam Ravindran, Committee Member
Tao Yao, Committee Member
Terry Paul Harrison, Committee Member - Keywords:
- Material handling
Transportation
Makespan
Flow shop scheduling
Dynamic prgramming
Heuristic algorithm - Abstract:
- This research studies two flow shop scheduling problems which consider transportation times between machines. The first problem considers a special case of a two-machine flow shop scheduling problem with asynchronous transportation times and the second one consider an application of flow shop scheduling to automated manufacturing cells with a synchronous material handling device. The objective of both problems is to find a job schedule which minimizes the makespan – the completion time of the last job. Regarding the asynchronous transportation times, there is one transporter with a specific capacity to transport jobs from the first machine to the second machine. The processing times on the first machine are job-independent. When the capacity of the transporter is greater than or equal to a threshold value, a dynamic programming algorithm is developed to obtain an optimal schedule. Given that n is the number of jobs, the computational effort of the proposed dynamic programming algorithm is shown to be O(n3). A new flow shop scheduling problem with synchronous material movement is considered. Specifically, we consider an automated machining center that consists of a loading/unloading (L/U) station, m machine stations, and a material handling device. The L/U station and the machines surround the material handling device, which is a rotary table that moves jobs between stations simultaneously. In this machining center, jobs have to be loaded on the rotary table at the L/U station, be transported to the processing machines subsequently, and finally be unloaded from the rotary table at the L/U station. Given a set of jobs that need to be processed in the machining center, the objective of the problem is to find the sequence that minimizes the makespan. We show that this scheduling problem is strongly NP-hard. A dynamic programming formulation is proposed for solving the problem in a small or medium scale. For large-size problems, two-phase heuristic algorithms are developed to obtain optimal or near optimal solutions in a short time for the cases with one machine and two machines. In addition, lower bounds are also provided for the problems with one, two and m machines. A polynomial-time algorithm is developed for the one-machine case with common unloading (or loading) times.