Premium
Self evolution algorithm to minimize earliness and tardiness penalties with a common due date on a single machine
Author(s) -
Weng Wei,
Fujimura Shigeru
Publication year - 2008
Publication title -
ieej transactions on electrical and electronic engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.254
H-Index - 30
eISSN - 1931-4981
pISSN - 1931-4973
DOI - 10.1002/tee.20321
Subject(s) - tardiness , computer science , schedule , benchmark (surveying) , scheduling (production processes) , reduction (mathematics) , mathematical optimization , due date , contingency , algorithm , job shop scheduling , operations research , engineering , mathematics , operating system , linguistics , philosophy , geometry , geodesy , geography
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.