A variable neighbourhood search algorithm for the flexible job-shop scheduling problem
A variable neighbourhood search algorithm for the flexible job-shop scheduling problem
复制标题
DOI：
10.1080/00207540903055743
复制
发表时间：
2010-10
影响因子：
9.2
通讯作者：
M. Amiri;Mostafa Zandieh;M. Yazdani;A. Bagheri
中科院分区：
文献类型：
--
作者：
M. Amiri;Mostafa Zandieh;M. Yazdani;A. Bagheri
柔性作业车间调度问题（FJSP）是经典作业车间调度问题的推广，它允许每个作业的操作由一组可用机器中的任意机器执行。FJSP由两个子问题组成，将每个操作分配给一组有能力的机器中的一台机器（路由子问题）和对机器上分配的操作进行排序（排序子问题）。本文提出了一种可变邻域搜索（VNS）算法，解决FJSP最小化的完工时间。在算法的过程中，各种相关的分配和排序问题的邻域结构用于产生相邻的解决方案。为了将我们的算法与以前的算法进行比较，对181个基准问题进行了广泛的计算研究。从所提出的算法获得的结果是相当的FJSP的最知名的算法所获得的。
The flexible job-shop scheduling problem (FJSP) is a generalisation of the classical job-shop scheduling problem which allows an operation of each job to be executed by any machine out of a set of available machines. FJSP consists of two sub-problems which are assigning each operation to a machine out of a set of capable machines (routing sub-problem) and sequencing the assigned operations on the machines (sequencing sub-problem). This paper proposes a variable neighbourhood search (VNS) algorithm that solves the FJSP to minimise makespan. In the process of the presented algorithm, various neighbourhood structures related to assignment and sequencing problems are used for generating neighbouring solutions. To compare our algorithm with previous ones, an extensive computational study on 181 benchmark problems has been conducted. The results obtained from the presented algorithm are quite comparable to those obtained by the best-known algorithms for FJSP.