Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria

What is it about?

This paper considers the flexible flow shop problem in which parallel machines at each stage may be unrelated. Each job is processed in ordered operations on a machine at each stage, and its release date and due date are given. We consider both sequence- and machine-dependent setup times. The problem is to determine a schedule that minimizes a convex combination of makespan and the number of tardy jobs. A 0–1 mixed integer program of the problem is formulated. Since this problem is NP-hard in the strong sense, we develop heuristic algorithms to solve it approximately. Several basic dispatching rules and well-known constructive heuristics for flow shop makespan scheduling problems are generalized to the problem under consideration. We sketch how, from a job sequence, a complete schedule for the flexible flow shop problem with unrelated parallel machines can be constructed. To improve the solutions, polynomial heuristic improvement methods based on shift moves of jobs are applied. In addition, genetic algorithms are suggested. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages.

Featured Image