Flowshop scheduling problems without intermediate queues but with sequence dependent setup times

Abstract

In this thesis, four flowshop scheduling problems in which no queues are allowed at any intermediate machine are considered. Firstly, a problem in which jobs have sequence dependent setup times only at the first machine is treated. The objective is to minimize the weighted mean flow time. A branchand-bound method is derived by exploiting lower bounds and a dominance property. Secondly, a problem in which jobs have non-separable and sequence dependent setup times at all machines is considered. A dynamic programming algorithm is provided for the objective of minimizing the makespan. Thirdly, for the case of cyclic production, a problem in which jobs have sequence dependent setup times only at the first machine is discussed. The objective is to minimize cycle time. Lastly, a problem which is similar to the third problem but has an additional restriction is investigated. The restriction is that for a sequence of consecutive batches of jobs, the first job of a succeeding batch can start its processing only after its preceding batch of jobs all completed. For the problem, the objective is to minimize the makespan and it is shown that the optimal solution can be found in traveling salesman problem solving approach. Numerical examples are presented for all the corresponding algorithm illustrations.