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

Authors: Saleem Z. Ramadan, Gürsel A. Süer

Abstract:

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.

Keywords: Machine scheduling, Genetic algorithms, Due dates, Number of tardy jobs, Number of early jobs, Integer programming, Dual Fitness functions.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1088088

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