卓雪雪 朱苍璐 郭杰 钱鹏

【摘  要】生产调度问题一直备受社会关注，尤其是制造业，因此，经典调度问题被研究学者提出，即实现一台机器加工一个工件的功能。随着社会对产品的需求量不断增加，实现一台机器同时加工多个工件的批调度问题被相继提出，其中差异工件尺寸调度问题最为复杂。论文研究的生产运输调度算法的复杂度超过了以上所有的批调度问题，涉及批调度和产品交付2个阶段，这是一个强NP难问题，深入研究具有重大意义。

【Abstract】The problem of production scheduling attracted much social attention， especially in manufacturing industry. Therefore， the classical scheduling problem is proposed by researchers， that is， realizing the function of one machine processing one workpiece. As the society's demand for products continues to increase， the batch scheduling problem to realize the simultaneous processing of multiple workpieces by one machine has been proposed one after another， among which the scheduling problem of different workpiece sizes is the most complex. The complexity of the algorithms of production and transportation scheduling studied in this paper exceeds all the above batch scheduling problems， involving two stages： batch scheduling and product delivery. This is a strong NP hard problem， and in-depth research is of great significance.

【關键词】平行批处理机;不同尺寸的工件;蚁群优化算法

【Keywords】parallel batch processing machine; workpieces of different sizes; ant colony optimization algorithm

【中图分类号】F273;TP18                                             【文献标志码】A                                                 【文章编号】1673-1069（2021）11-0124-04

1 引言

国内外研究学者首先提出了经典调度问题，即单机调度问题，如Tang[1]研究了改进的差分进化算法用以获得更好的解。但是随着社会的发展，单机调度问题不能满足社会的需要，随后平行机批调度问题被提出。Chang等[2]在研究了模拟退火算法处理平行批处理机调度问题。生产制造阶段固然重要，然而从企业利益角度出发，产品交付、最小化运输成本也非常重要。例如，Koh等[3]研究了订单的加工、包装以及交付的整个流程，最小化分销成本。Ghazvini等[4]研究了单机加工单车交付的问题。在本文中，研究了工件尺寸不同的平行机调度问题，同时，研究了加工完成的工件的交付问题。这种2个阶段结合的问题很少被研究，因此，本研究的集成调度具有重要意义。

2 研究内容

3 算法研究

3.1 下界算法

本文提出的下界算法主要是为了与启发式算法进行性能比较。……