A discrete particle swarm optimization for lot-streaming flowshop scheduling problem
A discrete particle swarm optimization for lot-streaming flowshop scheduling problem
复制标题
DOI：
10.1016/j.ejor.2007.08.030
复制
发表时间：
2008-12
期刊：
影响因子：
--
通讯作者：
C. Tseng;C. Liao
中科院分区：
文献类型：
--
作者：
C. Tseng;C. Liao
我们考虑了一个n作业、m台机器的流水作业问题，该问题的目标是最小化总的加权提前和拖期。为了解决这个问题，我们首先提出了一种所谓的移动净收益(NBM)算法，该算法比现有的线性规划模型更有效地获得给定作业序列中子节点的最优开始时间和完成时间。提出了一种新的结合NBM算法的离散粒子群优化算法(DPSO)来搜索最优序列。新的DPSO算法通过在粒子构造中引入遗传算法来改进现有的DPSO算法。为了验证DPSO算法的有效性，将其与现有的DPSO算法和混合遗传算法进行了比较。计算结果表明，采用两点继承机制的DPSO算法在解决批量流水作业调度问题时具有很强的竞争力。
We consider an n-job, m-machine lot-streaming problem in a flowshop with equal-size sublots where the objective is to minimize the total weighted earliness and tardiness. To solve this problem, we first propose a so-called net benefit of movement (NBM) algorithm, which is much more efficient than the existing linear programming model for obtaining the optimal starting and completion times of sublots for a given job sequence. A new discrete particle swarm optimization (DPSO) algorithm incorporating the NBM algorithm is then developed to search for the best sequence. The new DPSO improves the existing DPSO by introducing an inheritance scheme, inspired by a genetic algorithm, into particles construction. To verify the proposed DPSO algorithm, comparisons with the existing DPSO algorithm and a hybrid genetic algorithm (HGA) are made. Computational results show that the proposed DPSO algorithm with a two-point inheritance scheme is very competitive for the lot-streaming flowshop scheduling problem.