Abstract
In this work we consider a multiobjective job shop problem with uncertain durations and crisp due dates. Ill-known durations are modelled as fuzzy numbers. We take a fuzzy goal programming approach to propose a generic multiobjective model based on lexicographical minimisation of expected values. To solve the resulting problem, we propose a genetic algorithm searching in the space of possibly active schedules. Experimental results are presented for several problem instances, solved by the GA according to the proposed model, considering three objectives: makespan, tardiness and idleness. The results illustrate the potential of the proposed multiobjective model and genetic algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bierwirth C. (1995) A generalized permutation approach to jobshop scheduling with genetic algorithms. OR Spectrum 17: 87–92
Brucker P., Knust S. (2006) Complex scheduling. Springer, NY
Dubois D., Fargier H., Fortemps P. (2003) Fuzzy scheduling: Modelling flexible constraints vs. coping with incomplete knowledge. European Journal of Operational Research 147: 231–252
Dubois D., Fargier H., Galvagnon V. (2003) On latest starting times and floats in activity networks with ill-known durations. European Journal of Operational Research 147: 266–280
Dubois D., Fargier H., Prade H. (1996) Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty. Applied Intelligence 6: 287–309
Dubois D., Prade H. (1988) Possibility theory: An approach to computerized processing of uncertainty. Plenum Press, New York
Fayad, C., & Petrovic, S. (2005). A fuzzy genetic algorithm for real-world job-shop scheduling. Innovations in applied artificial intelligence. Lecture Notes in Computer Science (Vol. 3533, pp. 524–533). Bari: Springer.
Fortemps P. (1997) Jobshop scheduling with imprecise durations: A fuzzy approach. IEEE Transactions of Fuzzy Systems 7: 557–569
Fortemps P., Roubens M. (1996) Ranking and defuzzification methods based on area compensation. Fuzzy Sets and Systems 82: 319–330
Giffler B., Thomson G.L. (1960) Algorithms for solving production scheduling problems. Operations Research 8: 487–503
González Rodríguez I., Puente J., Vela C.R., Varela R. (2008) Semantics of schedules for the fuzzy job shop problem. IEEE Transactions on Systems, Man and Cybernetics, Part A 38(3): 655–666
González Rodríguez, I., Vela, C. R., & Puente, J. (2006). Study of objective functions in fuzzy job-shop problem. ICAISC 2006. Lecture Notes in Artificial Intelligence (vol. 4029, pp.360–369). Zakopane: Springer.
González Rodríguez I., Vela C.R., Puente J. (2007) A genetic solution for multiobjective fuzzy job shop based on lexicographical goal programming. In: Salido M.A., Fdez-Olivares J.(eds) Proceedings of the Workshop on Planning, Scheduling and Constraint Satisfaction. Salamanca, Spain, pp 93–104
González Rodríguez, I., Vela, C. R., & Puente, J. (2007b). A memetic approach to fuzzy job shop based on expectation model. In Proceedings of IEEE International Conference on Fuzzy Systems, FUZZ-IEEE2007 (pp. 692–697). London.
Liu B. (2006) A survey of credibility theory. Fuzzy Optimization and Decision Making 5: 387–408
Liu B., Liu Y.K. (2002) Expected value of fuzzy variable and fuzzy expected value models. IEEE Transactions on Fuzzy Systems 10: 445–450
Mattfeld D.C. (1995) Evolutionary search and the job shop investigations on genetic algorithms for production scheduling. Springer-Verlag, NY
Peng J., Liu B. (2004) Parallel machine scheduling models with fuzzy processing times. Information Sciences 166: 49–66
Sakawa M., Kubota R. (2000) Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms. European Journal of Operational Research 120: 393–407
Słowiński, R., Hapke, M. (eds) (2000) Scheduling under fuzziness (vol. 37 of Studies in Fuzziness and Soft Computing. Physica-Verlag, Heidelberg
Varela, R., Serrano, D., & Sierra, M. (2005). New codification schemas for scheduling with genetic algorithms. Artificial intelligence and knowledge engineering applications: A bioinspiried approach. Lecture Notes in Computer Science (Vol. 3562, pp. 11–20). Las Palmas: Springer.
Varela R., Vela C.R., Puente J., Gómez A. (2003) A knowledge-based evolutionary strategy for scheduling problems with bottlenecks. European Journal of Operational Research 145: 57–71
Yager R.R. (1981) A procedure for ordering fuzzy subsets of the unit interval. Information Sciences 24: 143–161
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this work was presented at the Workshop on Planning, Scheduling and Constraint Satisfaction held in conjunction with CAEPIA 2007 (González Rodríguez et al. 2007a).
Rights and permissions
About this article
Cite this article
González-Rodríguez, I., Vela, C.R. & Puente, J. A genetic solution based on lexicographical goal programming for a multiobjective job shop with uncertainty. J Intell Manuf 21, 65–73 (2010). https://doi.org/10.1007/s10845-008-0161-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10845-008-0161-x