A nondominated ranked genetic algorithm for bi-objective single machine preemptive scheduling in just-in-time environment

作者：Rahmani Keyhan; Mahdavi Iraj^*; Moradi Hadi; Khorshidian Hamid; Solimanpur Maghsud

来源：International Journal of Advanced Manufacturing Technology, 2011, 55(9-12): 1135-1147.

DOI：10.1007/s00170-010-3126-0

• Scheduling
• Single machine
• Preemption
• Earliness
• Number of tardy jobs
• Nondominated ranked genetic algorithm

Motivated by just-in-time (JIT) manufacturing, we study the bi-objective scheduling problem of minimizing the total weighted earliness and the number of tardy jobs on a single machine, in which machine idle time and preemption are allowed. The problem is known to be NP-hard. In this paper, we propose a new mathematical model, with nonlinear terms and integer variables which cannot be solved efficiently for medium- and large-sized problems. A method combining the new ranked-based roulette wheel selection algorithm with Pareto-based population ranking algorithm, named nondominated ranking genetic algorithm (NRGA), has been presented to find nondominated solutions in a reasonable time. Various operators and parameters of the proposed algorithm are reviewed to calibrate the algorithm by means of the Taguchi method. A number of numerical examples are solved to demonstrate the effectiveness of the proposed approach. The solutions obtained via NRGA are compared against solutions obtained via epsilon-constraint method in small-sized problems. Experimental results show that the proposed NRGA is competitive in terms of the quality and diversity of solutions in medium- and large-sized problems.

• 出版日期2011-8