New Properties for Solving the Single-Machine Scheduling Problem with Early/Tardy Jobs

Abstract

This paper presents a mathematically enhanced genetic algorithm (MEGA) using the mathematical properties of the single-machine scheduling of multiple jobs with a common due date. The objective of the problem is to minimize the sum of earliness and tardiness penalty costs in order to encourage the completion time of each job as close as possible to the common due date. The importance of the problem is derived from its NP-hardness and its ideal modeling of just-in-time concept. This philosophy becomes very significant in modern manufacturing and service systems, where policy makers emphasize that a job should be completed as close as possible to its due date. That is to avoid inventory costs and loss of customer’s goodwill. Five mathematical properties are identified and integrated into a genetic algorithm search process to avoid premature convergence, reduce computational effort, and produce high-quality solutions. The computational results demonstrate the significant impact of the introduced properties on the efficiency and effectiveness of MEGA and its competitiveness to state-of-the-art approaches.

Keywords

• genetic algorithm
• single machine scheduling
• early/tardy jobs
• common due date
• mathematical properties