| In this thesis, we study a scheduling model that is frequently encountered in practice---the flexible flow shops. In our flexible flow shop model, there are s stages in series and at each stage a number of identical machines in parallel. There are n jobs to be processed by each one of the stages with the same routing. Each job has a release date, a due date, a weight, and processing times. The objective is to minimize the total weighted tardiness of the n jobs, where tardiness of a job is defined as the positive difference between its completion time at the last stage and its due date. Within the alpha|beta|gamma framework in the scheduling literature, this problem can be referred to as FFsrjSw jTj .; We first develop three heuristics for solving this problem to near-optimality. The decomposition heuristic decomposes the entire flexible flow shop into simpler and correlated subproblems based on stages. The procedure consists of four basic steps, namely, bottleneck detection, subproblem formulation, solution of the subproblem, and reoptimization. The focal search heuristic is an iterative two-phase approach. In the first phase of an iteration we search for a good assignment of jobs to machines at every stage. The second phase schedules all the machines at each stage. The neighborhood structure is based on the critical arcs in a correspondent graph. The third heuristic is a hybrid algorithm that combines the decomposition heuristic and the local search heuristic. The comparative study and the average case performance analysis indicate the effectiveness of these heuristics.; We also develop a branch-and-bound algorithm for solving smaller size instances to optimality. The branching is carried out by generating active schedules for each one of the stages. Effective rules are established for branching in the presence of identical parallel machines at each stage. The lower bound is computed by first relaxing the disjunctive constraints of unscheduled operations and then solving the linear relaxation of an integer formulation of the correspondent problem. The lowerbound is made effective by a set-partitioning formulation and the use of column generation technique. The algorithm is able to solve instances with five stages and ten jobs in reasonable time.; Lastly, we extend the flexible flow shop model to a one with the machine eligibility constraints, i.e., each job can only be processed by a certain subset of the machines at each stage. We develop a decomposition algorithm framework for this model and we analyze the machine flexibility and job flexibility issues for telescopic machine subsets. |
