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

摘要

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 ε-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.