×

Genetic algorithms and simulated annealing for scheduling in agile manufacturing. (English) Zbl 1151.90407

Summary: Genetic algorithms and simulated annealing are applied to scheduling in agile manufacturing. The system addressed consists of a single flexible machine followed by multiple identical assembly stations, and the scheduling objective is to minimize the makespan. Both genetic algorithms and simulated annealing are investigated based on random starting solutions and based on starting solutions obtained from existing heuristics in the literature. Overall, four new algorithms are developed and their performance is compared to the existing heuristics. A \(2^{3}\) factorial experiment, replicated twice, is used to compare the performance of the various approaches, and identify the significant factors that affect the frequency of resulting in the best solution and the average percentage deviation from a lower bound. The results show that both genetic algorithms and simulated annealing outperform the existing heuristics in many instances. In addition, simulated annealing outperforms genetic algorithms with a more robust performance. In some instances, existing heuristics provide comparable results to those of genetic algorithms and simulated annealing with the added advantage of being simpler. Significant factors and interactions affecting the performance of the various approaches are also investigated.

MSC:

90B35 Deterministic scheduling theory in operations research
90B30 Production models
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1016/0377-2217(91)90304-E · Zbl 0734.90040
[2] Boothroyd G, Assembly Automation and Product Design (1992)
[3] DOI: 10.1016/0360-8352(96)00047-2
[4] DOI: 10.1016/S0360-8352(99)00136-9
[5] DOI: 10.1080/00207549308956791
[6] Goldberg DE, Genetic Algorithms in Search, Optimization, and Machine Learning (1989)
[7] He D, Robot. Comput. Integ. Manuf. 17 pp 2461– (2001)
[8] DOI: 10.1080/00207540210136522 · Zbl 1064.90526
[9] DOI: 10.1016/S0360-8352(97)00149-6
[10] Holland JH, Adaptation in Natural and Artificial Systems (1975)
[11] DOI: 10.1016/0377-2217(93)E0235-P · Zbl 0927.90048
[12] DOI: 10.1007/s001700050018
[13] DOI: 10.1007/s001700200208
[14] DOI: 10.1016/0305-0548(95)00079-8 · Zbl 0859.90087
[15] DOI: 10.1109/70.88060
[16] Kusiak A, Computational Intelligence in Design and Manufacturing (2000)
[17] DOI: 10.1023/A:1008009621190
[18] Michalewicz Z, Genetic Algorithms+Data Structures=Evolution Programs (1992) · Zbl 0763.68054
[19] DOI: 10.1016/S0360-8352(02)00188-2
[20] Montgomery D, Design and Analysis of Experiments (2001)
[21] DOI: 10.1016/S0377-2217(99)00354-9 · Zbl 0984.90017
[22] DOI: 10.1016/0377-2217(95)00275-8 · Zbl 0943.90584
[23] DOI: 10.1016/S0925-5273(02)00104-4
[24] DOI: 10.1016/S0377-2217(97)00333-0 · Zbl 0943.90038
[25] DOI: 10.1016/0305-0548(93)E0014-K · Zbl 0815.90097
[26] Sawik T, Production Planning and Scheduling in Flexible Assembly Systems (1999)
[27] DOI: 10.1080/00207729708929359 · Zbl 0872.90050
[28] Stat-Ease, Design-Expert® software. Version 6 2001 @www.stat-ease.com
[29] DOI: 10.1016/S0377-2217(02)00245-X · Zbl 1037.90035
[30] The Mathworks, Inc. MATLAB® software. Version 6.1 2001
[31] DOI: 10.1016/S0377-2217(98)00308-7 · Zbl 0945.90051
[32] DOI: 10.1016/S0305-0548(99)00137-9 · Zbl 1017.90048
[33] DOI: 10.1007/s001700200126
[34] DOI: 10.1007/s001700300005
[35] DOI: 10.1016/S0925-5273(00)00169-9
[36] Yoon S-H, IIE Trans. 34 pp 779– (2002)
[37] DOI: 10.1016/0377-2217(94)00021-4 · Zbl 0912.90185
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.