Self evolution algorithm to minimize earliness and tardiness penalties with a common due date on a single machine
Self evolution algorithm to minimize earliness and tardiness penalties with a common due date on a single machine
复制标题
自进化算法可在单台机器上通过共同的截止日期最大限度地减少提前和迟到的处罚
DOI：
10.1002/tee.20321
复制
发表时间：
2008
影响因子：
1
通讯作者：
S. Fujimura
中科院分区：
文献类型：
--
作者：
W. Weng;S. Fujimura
提前和拖期惩罚被设计用于流行的准时制（JIT）概念被认为是非常重要的调度问题。本文提出了一种自进化（SE）算法来解决具有公共交货期的单机总提前和拖期惩罚问题。到目前为止，还没有特别关注这类问题的跨越V型调度，这可能比纯V型调度更好的提前交货期的情况下，没有具体的讨论，在一个调度的第一个工作的开始时间设置。因此，本研究致力于挖掘跨V形调度，提高调度开始时间设置的效率，减少执行时间。此外，提出了一种新的RHRM方法来创建初始解的进化，这有助于实现快速应急的算法。该算法的性能已被测试280个基准测试实例，范围从10到1000个作业从OR库，结果表明，所提出的SE算法提供了更高的效率，在寻找最优或接近最优的解决方案，既更好的结果，总惩罚和显着的执行时间减少。Copyright © 2008日本电气工程师协会。出版社：John Wiley & Sons，Inc.
Earliness and tardiness penalties are designed for such scheduling problems where the popular Just‐In‐Time (JIT) concept is considered to be of significant importance. In this paper, a self evolution (SE) algorithm is proposed to solve the problem of single‐machine total earliness and tardiness penalties with a common due date. Up to now, no specific attention has been paid to straddling V‐shaped schedules of such problems, which may be better than pure V‐shaped schedules for the early due date cases; and no specific discussions have been made on the start time setting of the first job in a schedule. Therefore, in this research, efforts have been made on digging out the straddling V‐shaped schedules, improving the efficiency of setting the start time of a schedule, and reducing the execution time. In addition, a new RHRM approach is proposed to create the initial solution for evolution, which helps in achieving the fast contingency of the algorithm. The performance of the proposed algorithm has been tested on 280 benchmark instances ranging from 10 to 1000 jobs from the OR Library, and the results show that the proposed SE algorithm delivers much higher efficiency in finding optimal or near‐optimal solutions with both better results in total penalties and significant execution time reduction. Copyright © 2008 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.