×

A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. (English) Zbl 1039.90015

Summary: In this paper we propose a two-stage multi-population genetic algorithm (MPGA) to solve parallel machine scheduling problems with multiple objectives. In the first stage, multiple objectives are combined via the multiplication of the relative measure of each objective. Solutions of the first stage are arranged into several sub-populations, which become the initial populations of the second stage. Each sub-population then evolves separately while an elitist strategy preserves the best individuals of each objective and the best individual of the combined objective. This approach is applied in parallel machine scheduling problems with two objectives: makespan and total weighted tardiness (TWT). The MPGA is compared with a benchmark method, the multi-objective genetic algorithm (MOGA), and shows better results for all of the objectives over a wide range of problems. The MPGA is extended to scheduling problems with three objectives: makespan, TWT, and total weighted completion times and also performs better than MOGA.

MSC:

90B35 Deterministic scheduling theory in operations research
90B50 Management decision making, including multiple objectives
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Pinedo, M., Scheduling: theory, algorithms, and systems (1995), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1145.90393
[2] Gross, D.; Harris, C. M., Fundamentals of queueing theory (1988), Wiley: Wiley New York
[3] Rosenthal, R. E., Concepts, theory, and techniques—principle of multiobjective optimization, Decision Science, 16, 133-152 (1985)
[4] Fry, T. D.; Armstrong, R. D.; Lewis, H., A framework for single machine multiple objective sequencing research, Omega, 17, 594-607 (1989)
[5] Lee, C.-. Y.; Vairaktarakis, G. L., Complexity of single machine hierarchical scheduling: a survey, (Pardalos, P. M., Complexity in numerical optimization (1993), World Scientific Publishing: World Scientific Publishing Singapore), 269-298 · Zbl 0968.90521
[6] Lee, S. M.; Jung, H.-. J., A multi-objective production planning model in a flexible manufacturing environment, International Journal of Production Research, 27, 1981-1992 (1989)
[7] Schaffer JD. Multiple objective optimization with vector evaluated genetic algorithms. Proceedings of the First ICGA, 1985. p. 93-100.; Schaffer JD. Multiple objective optimization with vector evaluated genetic algorithms. Proceedings of the First ICGA, 1985. p. 93-100.
[8] Murata, T.; Ishibuchi, H.; Tanaka, H., Multi-objective genetic algorithm and its application to flowshop scheduling, Computers and Industrial Engineering, 30, 957-968 (1996)
[9] Hyun, C. J.; Kim, Y.; Kin, Y. K., A genetic algorithm for multiple objective sequencing problems in mixed model assembly, Computers & Operations Research, 25, 675-690 (1998) · Zbl 1042.90553
[10] Omori, R.; Sakakibara, Y.; Suzuki, A., Applications of genetic algorithms to optimization problems in the solvent extraction process for spent nuclear fuel, Nuclear Technology, 118, 26-31 (1997)
[11] Chen, Y.; Narita, M.; Tsuji, M.; Sa, S., A genetic algorithm approach to optimization for the radiological worker allocation problem, Health Physics, 70, 180-186 (1996)
[12] Marett, R.; Wright, M., A comparison of neighborhood search techniques for multi-objective combinatorial problems, Computers and Operations Research, 23, 465-483 (1996) · Zbl 0847.90082
[13] Yim, S. J.; Lee, D. Y., Multiple objective scheduling for flexible manufacturing systems using petri nets and heuristic search, Proceedings IEEE International Conference on Systems, Man, and Cybernetics, 4, 2984-2989 (1996)
[14] Jaszkiewicz, A., A metaheuristic approach to multiple objective nurse scheduling, Foundations of Computing and Decision Sciences, 22, 169-183 (1997) · Zbl 0902.90137
[15] Cieniawski, S. E.; Eheart, J. W.; Ranjithan, S., Using genetic algorithms to solve a multiobjective groundwater monitoring problem, Water Resources Research, 31, 399-409 (1995)
[16] Fowler, J. W.; Horng, S.-. M.; Cochran, J. K., A hybridized genetic algorithm to solve parallel machine problem scheduling problem with sequence dependent setups, International Journal of Manufacturing Technology and Management, 1, 3-4 (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.