Machine-Oriented Decomposition of Flowshop Scheduling Problems Using Lagrangian Relaxation
Machine-Oriented Decomposition of Flowshop Scheduling Problems Using Lagrangian Relaxation
复制标题
使用拉格朗日松弛的面向机器的流水作业调度问题分解
DOI：
10.5687/iscie.14.244
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
I. Hashimoto
中科院分区：
文献类型：
--
作者：
T. Nishi;S. Hasebe;I. Hashimoto
本文将拉格朗日分解与协调技术应用于最小化转换成本与拖期惩罚之和的流水车间调度问题。所提出的方法具有的特点，调度问题不是分解成单个作业级的子问题，而是分解成单个机器级的子问题。通过将问题分解为单机多操作子问题，转换成本和/或转换时间可以很容易地嵌入到目标函数中。在所提出的方法中，每个子问题的单机求解相结合的模拟退火方法和邻域搜索算法。为了避免乘子值的振荡，使用一个新的拉格朗日函数来求解每个子问题。最后，通过与模拟退火算法求解的算例结果进行比较，验证了该方法的有效性。
In this paper, the Lagrangian decomposition and coordination technique is applied to flowshop scheduling problems in which the sum of the changeover cost and the tardiness penalty is minimized. The proposed method possesses a feature that the scheduling problem is decomposed not into single job-level subproblems but into single machine-level subproblems. By decomposing the problem into one-machine multi-operation subproblems, the changeover cost and/or changeover time can easily be embedded in the objective function. In the proposed method, each subproblem for a single machine is solved by combining the simulated annealing method and the neighborhood search algorithm. In order to avoid oscillations in multiplier values, a new Lagrangian function is used to solve each subproblem. The effectiveness of the proposed method is verified by comparing the results of the example problems solved by the proposed method with those solved by the simulated annealing method in which a schedule of the entire machine is successively improved.