论文标题
在线打印商店调度问题的元尿学
Metaheuristics for the Online Printing Shop Scheduling Problem
论文作者
论文摘要
在这项工作中，考虑了在线打印商店计划问题（Lunardi等人，有关在线打印商店调度问题，计算机和操作研究）中的混合整数线性编程和约束编程模型。如今的印刷行业中出现的这个具有挑战性的实际调度问题对应于灵活的工作室调度问题，并进行了测序灵活性。它提出了几个复杂的特殊性，例如可重新操作，机器的不可用期间，依赖序列的设置时间，具有优先限制的操作之间的部分重叠以及固定的操作等。提出和评估了针对该问题的本地搜索策略和元启发式方法。基于共同的表示方案，考虑了轨迹和人口元启发术。大型实例的广泛数值实验表明，所提出的方法适合解决问题的实际实例。而且，他们的表现胜过半先进的半级别的现成的求解器。使用灵活的车间调度问题的经典实例的数值实验表明，应用于此特定情况时，引入的方法也具有竞争力。
In this work, the online printing shop scheduling problem introduced in (Lunardi et al., Mixed Integer Linear Programming and Constraint Programming Models for the Online Printing Shop Scheduling Problem, Computers & Operations Research, to appear) is considered. This challenging real scheduling problem, that emerged in the nowadays printing industry, corresponds to a flexible job shop scheduling problem with sequencing flexibility; and it presents several complicating specificities such as resumable operations, periods of unavailability of the machines, sequence-dependent setup times, partial overlapping between operations with precedence constraints, and fixed operations, among others. A local search strategy and metaheuristic approaches for the problem are proposed and evaluated. Based on a common representation scheme, trajectory and populational metaheuristics are considered. Extensive numerical experiments with large-sized instances show that the proposed methods are suitable for solving practical instances of the problem; and that they outperform a half-heuristic-half-exact off-the-shelf solver by a large extent. Numerical experiments with classical instances of the flexible job shop scheduling problem show that the introduced methods are also competitive when applied to this particular case.
