×

A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines. (English) Zbl 1042.90553

Summary: Sequencing problems are important for an efficient use of mixed model assembly lines. There is a rich set of criteria on which to judge sequences of product models in terms of line utilization. We consider three practically important objectives: minimizing total utility work, keeping a constant rate of part usage and minimizing total setup cost. A considerate line manager would like to take into account all these factors. The multiple objective sequencing problem is described and its mathematical formulation is provided. A genetic algorithm is designed for finding near-Pareto or Pareto optimal solutions for the problem. A new genetic evaluation and selection mechanism, called Pareto stratum-niche cubicle, is proposed. The performance comparison of the proposed genetic algorithm with three existing genetic algorithms is made for various test-bed problems in terms of solution quality and diversity. The results reveal that the proposed genetic algorithm outperforms the existing genetic algorithms, especially for problems that are large and involve great variation in setup cost.

MSC:

90B30 Production models
90B35 Deterministic scheduling theory in operations research
90C90 Applications of mathematical programming

Software:

Genocop
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bard, J. F.; Dar-El, E. M.; Shtub, A., An analytic framework for sequencing mixed model assembly lines, Int. J. Prod. Res., 30, 35-48 (1992) · Zbl 0825.90483
[2] Okamura, K.; Yamashina, H., A heuristic algorithm for the assembly line model-mix sequencing problem to minimize the risk of stopping the conveyor, Int. J. Prod. Res., 17, 233-247 (1979)
[3] Dar-El, E. M., Mixed-model assembly line sequencing problems, Omega, 6, 313-323 (1978)
[4] Yano, C. A.; Rachamadugu, R., Sequencing to minimize work overload in assembly lines with product options, Manage. Sci., 37, 572-586 (1991)
[5] Burns, L. D.; Daganzo, C. F., Assembly line job sequencing principles, Int. J. Prod. Res., 25, 71-99 (1987)
[6] Miltenburg, J., Level schedules for mixed-model assembly lines in just-in-time production systems, Manage. Sci., 35, 192-207 (1989) · Zbl 0666.90040
[7] Monden, Y., Toyota Production System; Monden, Y., Toyota Production System
[8] Bard, J. F.; Shtub, A.; Joshi, S. B., Sequencing mixed-model assembly lines to level parts usage and minimize line length, Int. J. Prod. Res., 32, 2431-2454 (1994) · Zbl 0902.90071
[9] Tsai, L., Mixed model sequencing to minimize utility work and the risk of conveyor stoppage, Manage. Sci., 41, 485-495 (1995) · Zbl 0832.90052
[10] Bolat, A.; Savsar, M.; Al-Fawzan, M. A., Algorithms for real-time scheduling of jobs on mixed model assembly lines, Comput. Ops. Res., 21, 487-498 (1994) · Zbl 0799.90069
[11] Kim, Y. K.; Hyun, C. J.; Kim, Y., Sequencing in mixed model assembly lines: a genetic algorithm approach, Comput. Ops. Res., 23, 1131-1145 (1996) · Zbl 0876.90056
[12] Holland, J. H., Adaptation in Natural and Artificial Systems; Holland, J. H., Adaptation in Natural and Artificial Systems
[13] Michalewicz, Z., Genetic Algorithms+Data Structures=Evolution Programs; Michalewicz, Z., Genetic Algorithms+Data Structures=Evolution Programs · Zbl 0763.68054
[14] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning; Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning · Zbl 0721.68056
[15] Schaffer, J. D., Multiple objective optimization with vector evaluated genetic algorithms. Proc. 1st Int. Conf. Genetic Algorithms and Their Applications; Schaffer, J. D., Multiple objective optimization with vector evaluated genetic algorithms. Proc. 1st Int. Conf. Genetic Algorithms and Their Applications
[16] Fonseca, C. M. and Fleming, P. J., Genetic algorithms for multiobjective optimization: formulation, discussion and generalization. Proc. 5th Int. Conf. Genetic Algorithms; Fonseca, C. M. and Fleming, P. J., Genetic algorithms for multiobjective optimization: formulation, discussion and generalization. Proc. 5th Int. Conf. Genetic Algorithms
[17] Ritzel, B. J.; Eheart, J. W., Using genetic algorithms to solve a multiple objective groundwater pollution containment problem, Water Resource Res., 30, 1589-1603 (1994)
[18] Baker, J. E., Adaptive selection methods for genetic algorithms. Proc. 1st Int. Conf. Genetic Algorithms and Their Applications.; Baker, J. E., Adaptive selection methods for genetic algorithms. Proc. 1st Int. Conf. Genetic Algorithms and Their Applications.
[19] Horn, J., Nafpliotis, N. and Goldberg, D. E., A niched Pareto genetic algorithm for multiobjective optimization. Proc. of 1st IEEE-ICEC Conference; Horn, J., Nafpliotis, N. and Goldberg, D. E., A niched Pareto genetic algorithm for multiobjective optimization. Proc. of 1st IEEE-ICEC Conference
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.