Solving the FMS scheduling problem by critical ratio-based heuristics and the genetic algorithm

This paper addresses the FMS scheduling problem. The objective concerned here is maximizing the meet-due-date rate. The authors propose two rules for job sequencing and job dispatching, two common subtasks in solving this problem. These two rules are designed based on the critical ratio values of jobs. We also propose a mechanism to obtain better performance than the stand-alone scheduling process via genetic algorithms. With the nature of design of the proposed job sequencing rule, the genetic algorithm is designed not only to improve the schedule quality but also to save computation time. All the proposed rules and idea are carefully examined through several different scenarios.