Flow shop scheduling with synchronous and asynchronous transportation times

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 transportation device. The objective of both problems is to find a job schedule which minimizes the makespan -- the completion time of the last job.;This research also considers a new flow shop scheduling problem with synchronous material movement. The automated machining center consists of a loading/unloading (L/U) station, m processing machines, and a rotary table. The L/U station and the processing machines surround the rotary table. In this machining center, a job is first loaded onto the rotary table at the L/U station. Then, the table rotates to transfer the job to the first machine, and subsequently to the second machine and so on. After being processed by the m machines, the job is transported back to the L/U station where it is unloaded from the machining center. A rotation of the table occurs only when all stations are finished with their jobs, including the loading and unloading operations at the L/U station. The mechanism of transferring all these jobs on the rotary table simultaneously to their next stations is referred to as synchronous material movement.;Regarding the machining center with synchronous material movement, the simplest model with a single machine is studied first. The problem is shown to be NP-hard in the strong sense. A polynomial time algorithm is developed for a special case which assumes a constant unloading or loading time for all jobs. Moreover, due to the systematic structure of the problem, a dynamic programming algorithm is provided to obtain an optimal solution for a generalized version of the problem with m machines. The computational effort of the dynamic programming algorithm is also presented.;Two-phase heuristic algorithms are developed to solve the problems with one machine and two machines. For each problem, two constructive heuristics and the modified neighborhood search algorithm are proposed, and computational experiments are conducted to test the performance of the proposed algorithms. The experimental results show that the two-phase algorithms generate high quality solutions in a very short time. A tighter lower bound is also developed for each case.;In the first problem, not only transportation times are explicitly provided but also the availability of the transporter is considered. In the model, 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. A threshold value for the transporter's capacity is derived. When the capacity of the transporter is greater than or equal to the 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), which is better than the best algorithm found in the literature.