Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria
Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria
复制标题
DOI：
10.1007/s00170-007-0977-0
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
Jitti Jungwattanakit;Manop Reodecha;P. Chaovalitwongse;Frank Werner
中科院分区：
文献类型：
--
作者：
Jitti Jungwattanakit;Manop Reodecha;P. Chaovalitwongse;Frank Werner
在纺织工业中，生产设施被建立为多阶段生产流水车间设施，其中生产阶段可能由并行机器组成。这称为灵活或混合流水车间环境。本文考虑在这种环境下调度独立作业的问题。此外，我们还考虑了一般情况，即每个阶段的并行机可能不相关。每个作业在每个阶段都在机器上按顺序操作进行处理。给出了其发布日期和截止日期。不允许抢占工作岗位。我们考虑与顺序和机器相关的设置时间。问题是确定一个时间表，使完工时间和迟到作业数量的凸组合最小化。制定了该问题的 0-1 混合整数规划。由于这个问题在强意义上是 NP 困难的，因此我们开发启发式算法来近似解决它。首先，将流水车间完工调度问题的几个基本调度规则和众所周知的构造启发法推广到所考虑的问题。我们概述了如何从作业序列构建具有不相关并行机器的灵活流水车间问题的完整时间表。为了改进解决方案，应用了基于工作轮班移动的多项式启发式改进方法。然后，提出了遗传算法。我们讨论这些算法的组成部分并测试它们的参数。启发式方法的性能是在一组最多 50 个作业和 20 个阶段的测试问题上进行相互比较的。
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 schedulingnindependent 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.