Abstract
In real-world manufacturing environments, it is common to face a job-shop scheduling problem (JSP) with uncertainty.Among different sources of uncertainty, processing times uncertainty is the most common. In this paper, we investigate the use of a multiobjective genetic algorithm to address JSPs with uncertain durations. Uncertain durations in a JSP are expressed by means of triangular fuzzy numbers (TFNs). Instead of using expected values as in other work, we consider all vertices of the TFN representing the overall completion time. As a consequence, the proposed approach tries to obtain a schedule that optimizes the three component scheduling problems [corresponding to the lowest, most probable, and largest durations] all at the same time. In order to verify the quality of solutions found by the proposed approach, an experimental study was carried out across different benchmark instances. In all experiments, comparisons with previous approaches that are based on a single-objective genetic algorithm were also performed.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Completion Time
- Fuzzy Number
- Multiobjective Optimizer
- Triangular Fuzzy Number
- Multiobjective Genetic Algorithm
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bierwirth, C.: A generalized permutation approach to job shop scheduling with genetic algorithms. OR Spektrum 17(2-3), 87–92 (1995)
Bierwirth, C., Mattfeld, D.C.: Production scheduling and rescheduling with genetic algorithms. Evolutionary Computation 7(1), 1–17 (1999)
Bortolan, G., Degani, R.: A review of some methods for ranking fuzzy subsets. Fuzzy Sets and Systems 15(1), 1–19 (1985)
Cheng, R., Gen, M., Tsujimura, Y.: A tutorial survey of job-shop scheduling problems using genetic algorithms—I. representation. Computers & Industrial Engineering 30(4), 983–997 (1996)
Deb, K., Agarwal, S., Pratap, A., Meyarivan, T.: A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Schoenauer, M., Deb, K., Rudolph, G., Yao, X., Lutton, E., Merelo, J.J., Schwefel, H.-P. (eds.) PPSN 2000. LNCS, vol. 1917, pp. 849–858. Springer, Heidelberg (2000)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6(2), 182–197 (2002)
Fortemps, P.: Jobshop scheduling with imprecise durations: a fuzzy approach. IEEE Transactions on Fuzzy Systems 5(4), 557–569 (1997)
Fortemps, P., Roubens, M.: Ranking and defuzzification methods based on area compensation. Fuzzy Sets and Systems 82(3), 319–330 (1996)
Giffler, B., Thompson, G.L.: Algorithms for solving production-scheduling problems. Operations Research 8(4), 487–503 (1960)
Gonzalez-Rodriguez, I., Puente, J., Vela, C.R., Varela, R.: Semantics of schedules for the fuzzy job-shop problem. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans 38(3), 655–666 (2008)
Gonzalez-Rodriguez, I., Vela, C.R., Puente, J.: A memetic approach to fuzzy job shop based on expectation model. In: IEEE Int. Conf. on Fuzzy Systems, pp. 1–6 (2007)
González, M.A., Vela, C.R., Varela, R.: Scheduling with memetic algorithms over the spaces of semi-active and active schedules. In: Rutkowski, L., Tadeusiewicz, R., Zadeh, L.A., Żurada, J.M. (eds.) ICAISC 2006. LNCS (LNAI), vol. 4029, pp. 370–379. Springer, Heidelberg (2006)
González, M.A., Vela, C.R., Puente, J.: A genetic solution based on lexicographical goal programming for a multiobjective job shop with uncertainty. Journal of Intelligent Manufacturing 21(1), 65–73 (2010)
González, M.A., Vela, C.R., Puente, J., Hernández-Arauzo, A.: Improved local search for job shop scheduling with uncertain durations. In: Nineteenth Int. Conf. on Automated Planning and Scheduling (ICAPS 2009), pp. 154–161 (2009)
Gonalves, J.F., de Magalhes Mendes, J.J., Resende, M.G.C.: A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research 167(1), 77–95 (2005)
Jain, A.S., Meeran, S.: Deterministic job-shop scheduling: Past, present and future. European Journal of Operational Research 113(2), 390–434 (1999)
Jensen, M.T.: Improving robustness and flexibility of tardiness and total flow-time job shops using robustness measures. Applied Soft Computing 1(1), 35–52 (2001)
Lawrence, S.: Supplement to “Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques”. Tech. rep., GSIA, Carnegie Mellon University, Pittsburgh PA (1984)
Lin, F.T., Yao, J.S.: Using fuzzy numbers in knapsack problems. European Journal of Operational Research 135(1), 158–176 (2001)
Liu, B., Liu, Y.K.: Expected value of fuzzy variable and fuzzy expected value models. IEEE Transactions on Fuzzy Systems 10(4), 445–450 (2002)
Nakano, R., Yamada, T.: Conventional genetic algorithm for job shop problems. In: Proceedings of ICGA, pp. 474–479 (1991)
Park, B.J., Choi, H.R., Kim, H.S.: A hybrid genetic algorithm for the job shop scheduling problems. Computers & Industrial Engineering 45(4), 597–613 (2003)
Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems, 3rd edn. Springer (2008)
Puente, J., Vela, C.R., González-Rodríguez, I.: Fast local search for fuzzy job shop scheduling. In: Proceedings of ECAI 2010, pp. 739–744. IOS Press (2010)
Srinivas, N., Deb, K.: Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation 2(3), 221–248 (1994)
Varela, R., Serrano, D., Sierra, M.R.: New codification schemas for scheduling with genetic algorithms. In: Mira, J., Álvarez, J.R. (eds.) IWINAC 2005, Part II. LNCS, vol. 3562, pp. 11–20. Springer, Heidelberg (2005)
Vázquez, M., Whitley, D.: A comparison of genetic algorithms for the static job shop scheduling problem. In: Schoenauer, M., Deb, K., Rudolph, G., Yao, X., Lutton, E., Merelo, J.J., Schwefel, H.-P. (eds.) PPSN 2000. LNCS, vol. 1917, pp. 303–312. Springer, Heidelberg (2000)
Yager, R.R.: A procedure for ordering fuzzy subsets of the unit interval. Information Sciences 24(2), 143–161 (1981)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Tran, TD., Varela, R., González-Rodríguez, I., Talbi, EG. (2014). Solving Fuzzy Job-Shop Scheduling Problems with a Multiobjective Optimizer. In: Huynh, V., Denoeux, T., Tran, D., Le, A., Pham, S. (eds) Knowledge and Systems Engineering. Advances in Intelligent Systems and Computing, vol 245. Springer, Cham. https://doi.org/10.1007/978-3-319-02821-7_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-02821-7_19
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-02820-0
Online ISBN: 978-3-319-02821-7
eBook Packages: EngineeringEngineering (R0)