Scheduling problems with due date-related measures for hybrid flowshops

Abstract

This dissertation focuses on scheduling problems in hybrid flowshops with the objective of minimizing total tardiness. A hybrid flowshop is a generalized form of flowshops in which each stage consists of multiple parallel machines. We consider three different problems for hybrid flowshop scheduling, and develop algorithms for the problems. First, we consider a two-stage hybrid flowshop scheduling problem with the objective of minimizing total tardiness of jobs. In the hybrid flowshop, there is one machine at the first stage and there are multiple identical parallel machines at the second stage. We develop dominance properties and lower bounds on the total tardiness of a given set of jobs, and suggest a branch and bound algorithm that is developed using these properties and bounds. Secondly, we consider a scheduling problem in a hybrid flowshop in which there are multiple serial stages, each with identical parallel machines. The objective of the problem is to minimize total tardiness of a given set of jobs. We suggest a new type of heuristic method, called bottleneck-focused algorithm, for the problem. In the algorithm, a schedule for a bottleneck stage is constructed first and then schedules for other stages are constructed based on the schedule for the bottleneck. Since the bottleneck stage may not be the first stage in the hybrid flowshop, ready times of operations at the bottleneck stage depend on the schedule at its upstream stages. At each iteration of the algorithm, the ready times are iteratively updated using information of a schedule obtained at the previous iteration. Finally, we consider a production scheduling problem in a printed circuit board (PCB) manufacturing system, which has the form of hybrid flowshop. The system produces multiple product types with different due dates and different manufacturing processes. Also, setup operations are required at certain stages or machines, and some product types have reentrant flows. In the production sch...