2018年8月控制工程 Aug. 2018 第25卷第8期Control Engineering of China V ol.25, No.8
文章编号：1671-7848(2018)08-1403-06 DOI: 10.14107/https://www.doczj.com/doc/275914588.html,ki.kzgc.160961
多目标双代理单机调度的变邻域搜索算法
徐建有，王丹敬
（东北大学信息科学与工程学院，沈阳 110819）
摘要：针对实际生产中存在的带有恶化效应的多目标双代理单机调度问题，提出了一
种基于Pareto最优的多目标变邻域搜索算法。为了提高算法的鲁棒性，与传统的变邻域
算法使用固定的邻域顺序不同，在算法中设计了一种邻域类型的自适应选择机制。基于
随机测试问题的实验结果表明，该算法的性能要优于当前文献中的一些典型的多目标优
化算法。
关键词：双代理单机调度；多目标自适应变邻域搜索
中图分类号：TP18 文献标识码：A
Multi-objective Two-agent Single Machine Scheduling Based on Variable
Neighborhood Search
XU Jian-you, WANG Dan-jing
（College of Information Science and Engineering, Northeastern University, Shenyang 110819, China）Abstract: To solve the multi-objective two-agent single machine scheduling problem with deterioration that exists in practical production, a multi-objective variable neighborhood search (MOVNS) is developed based on the Pareto optimal concept. Instead of a fixed sequence of neighborhoods in the traditional variable neighborhood search, an adaptive selection strategy of neighborhoods is presented so as to improve the algorithm’s robustness. Computational results based on random instances show that the MOVNS is superior to some classical multi-objective optimization algorithms in the literature.
Key words: Two-agent single machine scheduling; multi-objective self-adaptive variable neighborhood search 1 引言
在实际生产中，许多工件会出现开始加工时间越晚，其生产成本越高的情况。这种现象通常被称为工件恶化，带有工件恶化的生产调度问题已经受到了学术界的持续关注，Alidaee、Womer[1]和Cheng 等[2]。针对带有工件恶化的生产调度问题进行了较为详细的综述。从文献[1,2]的综述中可以看出，大多数研究者更关注的是一个准则的优化。但是，在实际生产中，工件也许来自不同的客户(代理)，不同客户的工件往往需要遵循不同的生产条件。文献检索也表明带有工件恶化的多代理调度问题在近年来逐渐受到了更多的关注[3-14]。但是，在这些文献中，包含与交货期相关目标函数(例如拖期工件数量、最大拖期)的研究还相对较少。而Armentano和Ronconi[15]，以及French[16]都指出在许多实际生产中，满足客户的交货期要求对于许多制造系统来说都是至关重要的。此外，以往的研究中通常都是针对单一目标进行研究，即在满足某一客户的一个指标不超出其上限的前提下，去最优化另一个客户的指标。实际生产调度问题通常是多目标优化[17,18]，使得双代理单机调度问题本质上也是一个多目标优化问题，而当前针对多目标双客户调度问题的研究还比较缺乏。因此，本文将双代理与工件恶化效应结合起来，研究带有工件恶化的多目标双代理单机调度问题，问题的优化目标是最小化2个客户各自工件的总加权拖期。针对该问题，提出了一个多目标变邻域搜索(Multi-Objective V ariable Neighborhood Search, MOVNS)算法。
2 问题描述
有n个工件需要在一个单机上进行加工，它们
万方数据