| This research examines the problem of scheduling jobs that are processed in non-similar groups on a two stage flow line to minimize makespan. In manufacturing operations, customer orders, or jobs, are often grouped together in order to reduce machine setup or changeover, thereby improving efficiency. Much work has been done in regard to the scheduling of jobs in groups (or batches), however, this work has focused on jobs remaining in the same group throughout their entire processing. This may not be the case if at different operations jobs are grouped based on different characteristics. Examples of this occur in upholstered furniture manufacturing, cross-docking, and some assembly operations.; In the general problem examined there are parallel machines at both stages and jobs proceed individually from the first stage to the second. Jobs are required to be processed in their prespecified groups at each stage, and at either stage only one setup is allowed per group. The scheduling decision involves that of sequencing groups, sequencing jobs within groups, and assigning groups to machines at both stages.; Due to the complexity of the general problem, simplified cases involving either group or job sequencing only at the first stage are examined. Optimal results are presented for two of these special cases. For the special cases most closely related to the general problem, various heuristics are tested against lower bounds. Heuristics based on variants of Johnson's Rule are found to have the best performance.; Several heuristics are developed and analyzed for the general problem, including constructive heuristics, a bounded randomized search heuristic, local improvement procedures, and a genetic algorithm. Of the deterministic and statistical lower bounds developed to evaluate heuristic performance to optimal, none are found to be consistently tight or reliable. Finally, heuristics that allow multiple setups per group at the second stage are presented and integrated into the genetic algorithm, which was found to have the best performance of the heuristics examined for the general problem. |
