A Dual Fitness Function Genetic Algorithm: Application on Deterministic Identical Machine Scheduling

In this paper a genetic algorithm (GA) with dual-fitness function is proposed and applied to solve the deterministic identical machine scheduling problem. The mating fitness function value was used to determine the mating for chromosomes, while the selection fitness function value was used to determine their survivals. The performance of this algorithm was tested on deterministic identical machine scheduling using simulated data. The results obtained from the proposed GA were compared with classical GA and integer programming (IP). Results showed that dual-fitness function GA outperformed the classical single-fitness function GA with statistical significance for large problems and was competitive to IP, particularly when large size problems were used.





References:
[1] Cheng, T. and Sin, C. 1990. A State-of-the-Art Review of Parallel-
Machine Scheduling Research. European Journal of Operation Research,
47: 271-292.
[2] Bedworth, D. and Bailey, J., Integrated Production Control Systems,
John Wiley, 1987.
[3] Suer, G., Baez, E. and Czajkiewicz, Z. (1993). Minimizing the number
of tardy jobs in identical machine scheduling. Computers and Industrial
Engineering. 25(4): 243–246.
[4] Chen, Z and Powell, W. 1999. A column generation based
decomposition algorithm for a parallel machine just-in-time scheduling
problem. European Journal of Operation Research, 116 (1): 220-232.
[5] Cheng, R. and Gen, M. (1996). Parallel machine scheduling problems
using memetic algorithms. IEEE International Conference on Systems,
Man, and Cybernetics. 4: 2665-2670.
[6] Liu, M. and Wu, C. (2003). Scheduling algorithm based on evolutionary
computing in identical parallel machine production line. Robotics and
Computer Integrated Manufacturing. 19: 401–407.
[7] Luu, D.T., Bohez E. L. J., and Techanitisawad A. (2002). A hybrid
genetic algorithm for the batch sequencing problem on identical parallel
machines. Production Planning and Control. 13(3):43-252.
[8] Min L. and Cheng W. (1999). A genetic algorithm for minimizing the
makespan in the case of scheduling identical parallel machines. Artificial
Intelligence in Engineering. 13(4): 399-403.
[9] Suer, G., Pico, F., and Santiago, A. (1997). Identical machine scheduling
to minimize the number of tardy jobs when lot-splitting is allowed.
Computers and Industrial Engineering. Vol. 33, Nos 1-2, pp. 277-280.
[10] Fariborz J., Rabbani M., Amalnick S., Dabaghi S., Dehghan M., and
Yazadn M. 2007. Genetic algorithm for bi-criteria single machine
scheduling problem of minimizing maximum earliness and number of
tardy jobs. Applied Mathematics and Computation, 194: 552–560.
[11] Johnny C., and Yih-Long H. (1995). Minimizing the number of tardy
jobs for m parallel machines. European Journal of Operational Research
84: 343-355
[12] Hui-Yuan F. Guang X., and Shang-Jin W (2000). A dual fitness function
genetic algorithm and application in aerodynamic inverse design.
Inverse Problems in Engineering 8, 4, pp. 325-344