) 华东理工大学 化工过程先进控制和优化技术教育部重点实验室，上海 200237
收稿日期:2019-11-11出版日期:2020-12-01发布日期:2020-12-31通讯作者:顾幸生E-mail:xsgu@ecust.edu.cn作者简介:赵芮(1994-)，女，重庆市人，硕士生，研究方向为生产调度．基金资助:国家自然科学基金(61973120)A Discrete Sine Optimization Algorithm for No-Idle Flow-Shop Scheduling Problem
ZHAO Rui, GU Xingsheng() Key Laboratory of Advanced Control and Optimization for Chemical Process of the Ministry of Education, East China University of Science and Technology, Shanghai 200237, China
Received:2019-11-11Online:2020-12-01Published:2020-12-31Contact:GU Xingsheng E-mail:xsgu@ecust.edu.cn摘要/Abstract
摘要： 针对以最小化最大完工时间(makespan)为目标的零空闲流水车间调度问题(NIFSP)，提出一种离散正弦优化算法(DSOA)进行求解．受正弦波形的启发，原始的正弦优化算法(SOA)是一种利用正弦函数对个体位置进行更新的全局优化算法．首先，重新定义了适应组合优化问题的位置更新策略，采用一种去除工件数大小可变的迭代贪婪算法来对个体位置进行更新，以提高算法的探索能力．其次，采用了交叉操作和保留精英解的选择策略，避免算法陷入局部最优．最后，为了提高局部搜索的开发能力和算法精度，引入了一种基于插入的局部搜索方法，以便于在当前最优解的周围寻找更好的解．此外，基于Taillard基准，给出了算法性能比较的仿真结果，实验结果验证了所提出的DSOA算法求解NIFSP的有效性．
关键词: 生产调度, 正弦优化算法, 零空闲流水车间调度问题, 迭代贪婪算法, 最大完工时间, 智能优化算法, 局部搜索
Abstract: Aimed at the no-idle flow-shop scheduling problem (NIFSP) with minimized makespan, a discrete sine optimization algorithm (DSOA) is proposed. Inspired by sine waveforms, the original sine optimization algorithm (SOA) is a global optimization algorithm, which uses the sine function to update the position of search agents. First, the update position strategy to adapt to the combinatorial optimization problem is redefined. An iterated greedy algorithm with a variable removing size is employed to update the position to enhance the exploration ability. Then, a crossover strategy and a selection strategy are applied to avoid the algorithm falling into local optimum. Next, to improve the exploitation ability of local search and the accuracy of the algorithm, an insertion-based local search scheme is applied in DSOA to search for a better solution around the current optimal solution. Finally, based on the Taillard benchmark, the simulation results of performance comparisons are presented. The experimental results demonstrate the effectiveness of the proposed DSOA algorithm for solving NIFSP.
Key words: production scheduling, sine optimization algorithm, no-idle flow-shop scheduling problem (NIFSP), iterated greedy algorithm, makespan, intelligent optimization algorithm, local search
PDF全文下载地址:
点我下载PDF
