×

Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms. (English) Zbl 0954.90071

Summary: By considering the imprecise or fuzzy nature of the data in real-world problems, job shop scheduling with fuzzy processing time and fuzzy duedate is introduced. On the basis of the agreement index of fuzzy duedate and fuzzy completion time, multiobjective fuzzy job shop scheduling problems are formulated as three-objective ones which not only maximize the minimum agreement index but also maximize the average agreement index and minimize the maximum fuzzy completion time. Having elicited the linear membership functions for the fuzzy goals of the decision maker, we adopt the fuzzy decision of Bellman and Zadeh. By incorporating the concept of similarity among individuals into the genetic algorithms using the Gannt chart, a genetic algorithm which is suitable for solving the formulated problems are proposed. As illustrative numerical examples, both \(6\times 6\) and \(10\times 10\) three-objective job shop scheduling problems with fuzzy duedate and fuzzy processing time are considered, and the feasibility and effectiveness of the proposed method are demonstrated by comparing with the simulated annealing method.

MSC:

90C70 Fuzzy and other nonstochastic uncertainty mathematical programming
90B35 Deterministic scheduling theory in operations research
92B20 Neural networks for/in biological studies, artificial life and related topics

Software:

JOBSHOP; Genocop
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] E. Aarts, J. Korst, Simulated Annealing and Boltzmann Machine, Wiley, Chichester, 1989 · Zbl 0674.90059
[2] Applegate, D.; Cook, W., A computational study of the job-shop scheduling problem, ORSA journal on computing, 3, 2, 149-156, (1991) · Zbl 0755.90039
[3] S. Bagchi, S. Uckun, Y. Miyabe, K. Kawamura, Exploring problem-specific recombination operator for job shop, in: Proceedings of the Fourth International Conference on Genetic Algorithms, 1991, pp. 10-17
[4] Bellman, R.E.; Zadeh, L.A., Decision making in a fuzzy environment, Management science, 17, 141-164, (1970) · Zbl 0224.90032
[5] G. Bortolan, R. Degani, A review of some methods for ranking fuzzy subsets, in: D. Dubois, H. Prade, R. Yager (eds.), Readings in Fuzzy Sets for Intelligent Systems, Morgan Kaufmann, San Francisco, CA, 1993, pp. 149-158 · Zbl 0567.90056
[6] K. Baker, Introduction to Sequencing and Scheduling, Wiley, New York, 1974
[7] R.W. Conway, W.L. Maxwell, L.W. Miller, Theory of Scheduling, Addison-Wesley, Reading, MA, 1967 · Zbl 1058.90500
[8] L. Davis (Ed.), Genetic Algorithms and Simulated Annealing, Morgan Kaufmann, Los Altos, CA, 1987 · Zbl 0684.68013
[9] S. French, Sequencing and Scheduling: An Introduction to the Mathematics of Job-Shop, Wiley, New York, 1982 · Zbl 0479.90037
[10] M. Gen, R. Cheng, Genetic Algorithms and Engineering Design, Wiley, New York, 1997
[11] L. Davis, Job shop scheduling with genetic algorithms, in: Proceedings of the First International Conference on Genetic Algorithms, 1985, pp. 136-140
[12] D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989 · Zbl 0721.68056
[13] Ishii, H.; Tada, M., Single machine scheduling problem with fuzzy precedence relation, European journal of operational research, 87, 284-288, (1995) · Zbl 0914.90163
[14] A. Kaufmann, M. Gupta, Fuzzy Mathematical Models in Engineering and Management Science, North-Holland, Amsterdam, 1988 · Zbl 0683.90024
[15] A. Kaufmann, M. Gupta, Introduction to Fuzzy Arithmetic, Van Nostrand Reinhold, New York, 1991 · Zbl 0754.26012
[16] Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[17] S. Kobayashi, I. Ono, M. Yamamura, An efficient genetic algorithm for job shop scheduling problems, in: Proceedings of the Sixth International Conference on Genetic Algorithms, 1995, pp. 506-511
[18] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer, Berlin, 1992 (2nd revised ed., 1994; 3rd revised and extended ed., 1996) · Zbl 0763.68054
[19] R. Nakano, Conventional genetic algorithm for job shop problems, in: Proceedings of the Fourth International Conference on Genetic Algorithms, 1991, pp. 474-479
[20] M. Sakawa, Fuzzy Sets and Interactive Multiobjective Optimization, Plenum Press, New York, 1993 · Zbl 0842.90070
[21] M. Sakawa, H. Ishii, I. Nishizaki, Soft Optimization, Asakura Shoten, Tokyo, 1995 (in Japanese)
[22] M. Sakawa, M. Tanaka, Genetic Algorithms, Asakura Shoten, Tokyo, 1995 (in Japanese)
[23] Sakawa, M.; Mori, T., Job shop scheduling through genetic algorithms incorporating similarity concepts (in Japanese), The transactions of the institute of electronics, information and communication engineers A, J80-A, 6, 960-968, (1997)
[24] Sakawa, M.; Mori, T., Job shop scheduling with fuzzy duedate and fuzzy processing time through genetic algorithms (in Japanese), Journal of Japan society for fuzzy theory and systems, 9, 2, 231-238, (1997)
[25] T. Starkweather, S. McDaniel, K. Mathias, D. Whitley, C. Whitley, Comparison of genetic sequencing operators, in: Proceedings of the Fourth International Conference on Genetic Algorithms, 1991, pp. 69-76
[26] Tamaki, H.; Nishikawa, Y., A parallel genetic algorithm based on a neighborhood model and its application to the jobshop scheduling, Parallel problem solving from nature, 2, 573-582, (1992)
[27] Tsujimura, Y.; Gen, M.; Kubota, E., Solving job-shop scheduling problem with fuzzy processing time using genetic algorithm, Journal of Japan society for fuzzy theory and systems, 7, 5, 1073-1083, (1995)
[28] Yamada, T.; Nakano, R., A genetic algorithm applicable to large-scale job shop problems, Parallel problem solving from nature, 2, 281-290, (1992)
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.