×

A genetic algorithm and the Monte Carlo method for stochastic job-shop scheduling. (English) Zbl 1108.90317

Summary: This paper proposes a method for solving stochastic job-shop scheduling problems using a hybrid of a genetic algorithm in uncertain environments and the Monte Carlo method. First, the genetic algorithm in uncertain environments is applied to stochastic job-shop scheduling problems where the processing times are treated as stochastic variables. The Roulette strategy is adopted for selecting the optimum solution having the minimum expected value for makespan. Applying crossover based on Giffler and Thompson’s algorithm results in two offspring inheriting the ancestor’s characteristics as the operation completion times averaged up to the parent’s generation. Individuals having very high frequency through all generations are selected as the good solutions. Second, the Monte Carlo method is effectively used for finding out the approximately optimum solution among these good solutions.

MSC:

90B36 Stochastic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] S. Bagchi, S. Uckun, Y. Miyabe, and K. Kawamura , 1991 . Exploring problem-specific recombination operators for job shop scheduling,Proceedings of 4th International Conference on Genetic Algorithms and their Applications, 10 -17 .
[2] Balas E., Operations Research 17 pp 941– (1969)
[3] Barker J.R., Management Science 31 pp 594– (1985)
[4] Carlier J., Management Science 35 pp 164– (1989)
[5] L. Davis , 1985 . Job shop scheduling with genetic algorithms.Proceedings of International Conference on Genetic Algorithms and their Applications, 136 -140 .
[6] DOI: 10.1016/0305-0548(93)E0015-L · Zbl 0816.90081
[7] DOI: 10.1016/0305-0548(93)E0016-M · Zbl 0815.90089
[8] Giffler B., Operations Research 8 pp 164– (1969)
[9] DOI: 10.1016/S0377-2217(98)00113-1 · Zbl 0938.90028
[10] Kise H., Management Science 29 pp 384– (1983)
[11] Kise H., Journal of the Operations Research Society of Japan 25 pp 193– (1982)
[12] Liepins G.E., Proceedings of 2nd Conference on Genetic Algorithm and their Applications pp 90– (1987)
[13] McMahon G., Operations Research 23 pp 475– (1975)
[14] Muth J.F., Industrial Scheduling (1963)
[15] R. Nakano, and T. Yamada , 1991 . Conventional genetic algorithm for job shop problems.Proceedings of International 4th Conference on Genetic Algorithms and their Applications, 474 -479 .
[16] Norman B., Engineering Design and Automation 3 pp 145– (1997)
[17] I. Ono, M. Yamamura, and S. Kobayashi , 1996 .A genetic algorithm, for job-shop scheduling problems using job-based order crossover. Proceedings of ICE’96, 547 -552 .
[18] Tamaki H., Parallel Problem Solving from, Nature 2 pp 573– (1992)
[19] Vacssens R., INFORMS Journal on Computing 8 pp 302– (1996)
[20] D. Whitley, T. Starkweather, and D. Fuquay , 1989 . Scheduling problems and traveling sales-man: The genetic edge recombination operator.Proceedings of International 3th Conference on Genetic Algorithms and their Applications, 133 -140 .
[21] Yamada T., Parallel Problem Solving from Nature 2 pp 281– (1992)
[22] Yoshitomi Y., Journal of the Operations Research Society of Japan 43 pp 266– (2000)
[23] DOI: 10.1111/1475-3995.00368 · Zbl 1008.90026
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.