Multi-objective genetic algorithm for single machine scheduling problem under fuzziness. (English) Zbl 1140.90398
Summary: This paper presents a new multi-objective approach to a single machine scheduling problem in the presence of uncertainty. The uncertain parameters under consideration are due dates of jobs. They are modelled by fuzzy sets where membership degrees represent decision maker’s satisfaction grade with respect to the jobs’ completion times. The two objectives defined are to minimise the maximum and the average tardiness of the jobs. Due to fuzziness in the due dates, the two objectives become fuzzy too. In order to find a job schedule that maximises the aggregated satisfaction grade of the objectives, a hybrid algorithm that combines a multi-objective genetic algorithm with local search is developed. The algorithm is applied to solve a real-life problem of a manufacturing pottery company.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C29 | Multi-objective and goal programming |
| 90C70 | Fuzzy and other nonstochastic uncertainty mathematical programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
Single machine scheduling; Fuzzy sets; Multi-objective optimisation; Genetic algorithms; Local searchReferences:
| [1] | Adamopoulos G.I., Pappis C.P. (1996). A fuzzy-linguistic approach to a multi-criteria sequencing problem. European Journal of Operational Research 92(3): 628–636 · Zbl 0914.90154 · doi:10.1016/0377-2217(95)00091-7 |
| [2] | Chen C.-L., Bulfin R.L. (1990). Scheduling unit processing time jobs on a single machine with multiple criteria. Computers and Operations Research 17(1): 1–7 · Zbl 0681.90049 · doi:10.1016/0305-0548(90)90022-Y |
| [3] | Dyckhoff H., Pedrycz W. (1984). Generalized means as a model of compensative connectives. Fuzzy Sets and Systems 14(2): 143–154 · Zbl 0551.03035 · doi:10.1016/0165-0114(84)90097-6 |
| [4] | Goldberg, D. E. (1989). Genetic algorithms in search, optimisation and machine learning. Addison-Wesley. · Zbl 0721.68056 |
| [5] | Hong T., Chuang T. (1999). New triangular fuzzy Johnson algorithm. Computers and Industrial Engineering 36(1): 179–200 · doi:10.1016/S0360-8352(99)00008-X |
| [6] | Ishibuchi H., Murata T. (1998). A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Transactions on Systems, Man and Cybernetics–Part C: Applications and Reviews 28(3): 392–403 · doi:10.1109/5326.704576 |
| [7] | Ishibuchi, H., & Murata, T. (2000). Flowshop scheduling with fuzzy duedate and fuzzy processing time. In R. Slowiński & M. Hapke (Eds.), Scheduling under fuzziness. Heidelberg: Physica-Verlag. · Zbl 0960.90035 |
| [8] | Ishibuchi H., Yoshida T., Murata T. (2003). Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transaction on Evolutionary Computation 7(2): 204–223 · doi:10.1109/TEVC.2003.810752 |
| [9] | Ishii H., Tada M. (1995). Single machine scheduling problem with fuzzy precedence relation. European Journal of Operational Research 87(2): 284–288 · Zbl 0914.90163 · doi:10.1016/0377-2217(94)00162-6 |
| [10] | Kuroda M., Wang Z. (1996). Fuzzy job shop scheduling. International Journal of Production Economics 44(1–2): 45–51 · doi:10.1016/0925-5273(95)00091-7 |
| [11] | Lee H.T., Chen S.H., Kang H.Y. (2002). Multicriteria scheduling using fuzzy theory and tabu search. International Journal of Production Research 40(5): 1221–1234 · Zbl 1027.90038 · doi:10.1080/00207540110098832 |
| [12] | Pedrycz W., Gomide F. (1998). An introduction to fuzzy sets: Analysis and design. Bradford Book, MIT Press · Zbl 0938.03078 |
| [13] | Petrovic R., Petrovic D. (2001). Multicriteria ranking of inventory replenishment policies in the presence of uncertainty in customer demand. International Journal of Production Economics 71(1–3): 439–446 · Zbl 0995.05065 · doi:10.1016/S0925-5273(00)00139-0 |
| [14] | Pinedo, M., & Chao, X. (1999). Operation scheduling with applications in manufacturing and services. McGraw-Hill International Editions, Computer Science Series. |
| [15] | Ruspini E., Bonissone P., Pedrycz W. (eds). (1998). Handbook of fuzzy computation. Bristol and Philadelphia, Institute of Physics Publishing · Zbl 0902.68068 |
| [16] | Slowiński R., Hapke M. (2000). Scheduling under fuzziness. Heidelberg, Physica-Verlag · Zbl 0934.00015 |
| [17] | Syswerda, G. (1989). Uniform crossover in genetic algorithms. In J. D. Schaffer (Ed.), Proceedings of the 3rd International Conference on Genetic Algorithms and Their Applications. San Mateo, CA: Morgan Kaufmann Publishers. |
| [18] | T’kindt V., Billaut J.-C. (2002). Multicriteria scheduling: Theory, models and algorithms. Berlin Heidelberg, Springer-Verlag |
| [19] | Yager R. (1988). On ordered weighted averaging aggregation operations in multicriteria decision making. IEEE Transactions on Systems, Man and Cybernetics 18(1): 183–190 · Zbl 0637.90057 · doi:10.1109/21.87068 |
| [20] | Zimmermann H.-J. (2001). Fuzzy set theory and its applications. Massachusetts, Kluwer Academic Publishers |
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.
