A reverse constraint satisfying method for earliness/tardiness scheduling problem based on improved genetic algorithm

Abstract

Earliness/tardiness scheduling is a new scheduling mode based on the concept of JIT (Just-In-Time). When compared with the traditional job-shop scheduling, earliness/tardiness scheduling involves more complex constraints and thus is a more complicated combinatorial optimization problem. This paper proposes a strategy based on reverse constraints satisfying to improve the genetic algorithm (GA) so that the earliness/tardiness scheduling problem could be solved. The main contents include three parts: (1) the mathematical modeling of earliness/tardiness scheduling is constructed, which is more complex than the common job shop model; (2) the reverse scheduling tactics based on GA are proposed, which includes the GA coding design based on work-piece unit, reversing decoding methods, and the GA fitness evaluation method based on reverse constraints satisfaction; (3) the comparative experiments have been done to show the advantages of reverse scheduling tactic compared with the forward scheduling. The comparative experiment results show the reverse scheduling tactic has practicability and feasibility to solve the job-shop earliness/tardiness scheduling problem.