Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria |
| |
Authors: | Jitti Jungwattanakit Manop Reodecha Paveena Chaovalitwongse Frank Werner |
| |
Affiliation: | (1) Department of Industrial Engineering, Faculty of Engineering, Chulalongkorn University, Bangkok, 10330, Thailand;(2) Faculty of Mathematics, Otto-von-Guericke University Magdeburg, P.O. Box 4120, 39016 Magdeburg, Germany |
| |
Abstract: | In textile industries, production facilities are established as multi-stage production flow shop facilities, where a production
stage may be made up of parallel machines. This known as a flexible or hybrid flow shop environment. This paper considers
the problem of scheduling n independent jobs in such an environment. In addition, we also consider the general case in which parallel machines at each
stage may be unrelated. Each job is processed in ordered operations on a machine at each stage. Its release date and due date
are given. The preemption of jobs is not permitted. 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. Firstly, 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. Then, genetic algorithms are suggested. We discuss
the components of these algorithms and test their parameters. 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. |
| |
Keywords: | Flexible flow shop scheduling Mathematical programming Constructive algorithms Genetic algorithms |
本文献已被 SpringerLink 等数据库收录! |
|