×

zbMATH — the first resource for mathematics

Fuzzy scheduling: Modelling flexible constraints vs. coping with incomplete knowledge. (English) Zbl 1037.90028
Summary: An overview of some fuzzy set-based approaches to scheduling is proposed, emphasizing two distinct uses of fuzzy sets: representing preference profiles and modelling uncertainty distributions. The first setting leads to a valued, non-compensatory generalization of constraint-directed scheduling. The other setting yields a possibility-theoretic counterpart of PERT, where probability distributions of activity durations are changed into possibility distributions, for the purpose of modelling incomplete information. It is pointed out that a special case of the latter, interval-valued PERT, is a difficult, ill-known problem, regarding the determination of critical activities, latest starting times and floats. Lastly when flexible constraints and uncertain processing times are to be jointly considered, the use of possibilistic decision theory leads to the computation of robust schedules.

MSC:
90B35 Deterministic scheduling theory in operations research
90C70 Fuzzy and other nonstochastic uncertainty mathematical programming
Software:
FULPAL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baas, S.M.; Kwakernaak, H., Rating and ranking of multiple aspect alternatives using fuzzy sets, Automatica, 13, 47-58, (1977) · Zbl 0363.90010
[2] Bellman, R.E.; Zadeh, L.A., Decision-making in a fuzzy environment, Management science, 17, 4, B141-B164, (1970) · Zbl 0224.90032
[3] Bensana, E.; Bel, G.; Dubois, D., OPAL, a multi-knowledge-based system for industrial job-shop scheduling, International journal of production research, 26, 5, 795-816, (1988)
[4] Birge, J.R.; Dempster, M.A.H., Stochastic programming approaches to stochastic scheduling, Journal of global optimization, 9, 383-409, (1996) · Zbl 0870.90067
[5] Blazewicz, J., Cellary, W., Slowinski, R., Weglarz, J. (Eds.) 1986. Scheduling under resource constraint–Deterministic Models. Annals of Operations Research, vol. 7, J.C. Baltzer AG · Zbl 0374.90033
[6] Bortolan, G.; Degani, R., A review of some methods for comparing fuzzy subsets, Fuzzy sets and systems, 15, 1-19, (1985) · Zbl 0567.90056
[7] Buckley, J.J., Fuzzy PERT, (), 103-114
[8] Chanas, S.; Kamburowski, J., The use of fuzzy variables in PERT, Fuzzy sets and systems, 5, 11-19, (1981) · Zbl 0451.90076
[9] Chanas, S.; Kuchta, D., Discrete fuzzy optimization, (), 249-277 · Zbl 0931.90066
[10] Chanas, S.; Zielinski, P., The computational complexity of interval critical path method, European journal of operational research, 136, 3, 541-550, (2002) · Zbl 1008.90029
[11] Chanas, S., Zielinski P., 2001. Critical path analysis in the network with fuzzy activity times, to appear in Fuzzy Sets and Systems, 122 (2), 195-204 · Zbl 1015.90096
[12] Chanas, S.; Dubois, D.; Zielinski, P., Necessary criticality in the network with imprecise activity times, IEEE transactions on systems, man and cybernetics, 32, 393-407, (2002)
[13] Chen, S.-J.; Hwang, C.-L., ()
[14] Dubois, D., 1983. Modèles mathématiques de l’imprécis et de l’incertain en vue d’applications aux techniques d’aide á la décision, Thèse d’état de l’Université Scientifique et Médicale de Grenoble · Zbl 0546.94036
[15] Dubois, D., Fuzzy knowledge in an artificial intelligence system for job-shop scheduling, (), 73-89
[16] Dubois, D.; Fortemps, P., Computing improved optimal solutions to fuzzy constraint satisfaction problems, European journal of operational research, 118, 95-126, (1999) · Zbl 0945.90087
[17] Dubois, D.; Koning, J.L., A decision engine based on rational aggregation of heuristic knowledge, Decision support systems, 11, 337-361, (1994)
[18] Dubois, D.; Prade, H., Algorithmes de plus courts chemins pour traiter des donnees floues, RAIRO-recherche opérationnelle/operations research, 12, 212-227, (1978) · Zbl 0379.90046
[19] Dubois, D.; Prade, H., Fuzzy sets and systems–theory and applications, (1980), Academic Press New York · Zbl 0444.94049
[20] Dubois, D.; Prade, H., The Mean value of a fuzzy number, Fuzzy sets and systems, 24, 279-300, (1987) · Zbl 0634.94026
[21] Dubois, D.; Prade, H., Possibility theory, (1988), Plenum Press New York · Zbl 0645.68108
[22] ()
[23] Dubois, D.; Fargier, H.; Prade, H., Fuzzy constraints in job-shop scheduling, Journal of intelligent manufacturing, 6, 215-234, (1995)
[24] Dubois, D.; Fargier, H.; Prade, H., Possibility theory in constraint satisfaction problems: handling priority, preference and uncertainty, Applied intelligence, 6, 287-309, (1996) · Zbl 1028.91526
[25] Dubois, D.; Kerre, E.; Mesiar, R.; Prade, H., Fuzzy interval analysis, (), 483-581 · Zbl 0988.26020
[26] Dubois, D., Fargier, H., Galvagnon, V., 2001. On latest starting times and floats in activity networks with ill-known durations. European Journal of Operational Research 147 (2), this issue · Zbl 1037.90004
[27] Dubois, D.; Prade, H.; Sabbadin, R., Decision-theoretic foundations of qualitative possibility theory, European journal of operational research, 128, 459-478, (2002) · Zbl 0982.90028
[28] Erschler, J.; Esquirol, P., Decison-aid in job shop scheduling: A knowledge based approach, (), 1751-1756
[29] Erschler, J.; Roubellat, F.; Vernhes, J.P., Finding some essential characteristics of the feasible solutions for a scheduling problem, Operations research, 24, 774-783, (1976) · Zbl 0335.90027
[30] Esquirol, P.; Lopez, P., L’ordonnancement, (1999), Economica Paris
[31] Fargier, H., 1994. Problèmes de satisfaction de contraintes flexibles: Application à l’ordonnancement de production. Thèse de Doctorat, Université Paul Sabatier, Toulouse
[32] Fargier, H., Fuzzy scheduling: principles and experiments, (), 655-669
[33] Fargier, H.; Galvagnon, V., Le problm̀e du PERT flou dans LES graphes série-paralléle, (), 277-284
[34] Fargier, H.; Galvagnon, V.; Dubois, D., Fuzzy PERT in series – parallel graphs, (), 717-722
[35] Fodor, J.; Roubens, M., Fuzzy preference modelling and multicriteria decision support, (1994), Kluwer Academic Publishers Dordrecht, section 7.2.2 · Zbl 0827.90002
[36] Fortemps, P., Job-shop scheduling with imprecise durations: A fuzzy approach, IEEE transactions on fuzzy systems, 5, 557-569, (1997)
[37] Fortemps, P.; Hapke, M., On the disjunctive graph for project scheduling, Foundations of computing and decision sciences, 22, 195-209, (1997) · Zbl 0902.90097
[38] Fortemps, P.; Roubens, M., Ranking and defuzzification methods based on area compensation, Fuzzy sets and systems, 82, 319-330, (1996) · Zbl 0886.94025
[39] Fox, M.S., Constraint-directed search: A case study of job-shop scheduling, (1987), Pitman London · Zbl 0702.68032
[40] Gazdik, I., Fuzzy network planning FNET, IEEE transactions on reliability, 32, 303-313, (1983) · Zbl 0526.90053
[41] Grabot, B.; Geneste, L., Dispatching rules in scheduling: A fuzzy approach, International journal of production research, 32, 903-915, (1994) · Zbl 0899.90111
[42] Guiffrida, A.L.; Nagi, R., Fuzzy set theory applications in production management research: A literature survey, Journal of intelligent manufacturing, 9, 39-56, (1998)
[43] Hapke, M.; Jaszkiewicz, A.; Slowinski, R., Fuzzy project scheduling system for software development, Fuzzy sets and systems, 21, 101-117, (1994)
[44] Hintz, G.W.; Zimmermann, H.-J., A method to control flexible manufacturing systems, European journal of operational research, 41, 321-334, (1989)
[45] Ishibuchi, H.; Yamamoto, N.; Misaki, S.; Tanaka, H., Local search algorithms for flowshop scheduling with fuzzy due-dates, International journal of production economics, 33, 53-66, (1994)
[46] Ishii, H.; Tada, M.; Masuda, T., Two scheduling problems with fuzzy due-dates, Fuzzy sets and systems, 46, 339-347, (1992) · Zbl 0767.90037
[47] Kaufmann, A.; Gupta, M.M., Fuzzy mathematical models in engineering and management science, (1988), Amsterdam North Holland · Zbl 0683.90024
[48] Kerr, R.M., Walker, R.N., 1989. A job shop scheduling system based on fuzzy arithmetics. In: Proceedings of the third International Conference on Expert Systems and the Leading Edge in Production and Operation Management, Hilton Head, SC pp. 433-450
[49] Lin, K.C.; Chern, M.S., The fuzzy shortest path problem and its most vital arcs, Fuzzy sets and systems, 58, 343-353, (1993) · Zbl 0804.90138
[50] Litoiu, M.; Tadei, R., Real-time task scheduling allowing fuzzy due-dates, European journal of operational research, 100, 475-481, (1997) · Zbl 0917.90195
[51] Litoiu, M.; Tadei, R., Real-time scheduling with fuzzy deadlines and processing times, Fuzzy sets and systems, 117, 35-46, (2000) · Zbl 0965.68005
[52] Lootsma, F., Stochastic and fuzzy PERT, European journal of operational research, 43, 174-183, (1989) · Zbl 0681.90039
[53] Lootsma, F., Fuzzy logic for planning and decision-making, (1997), Kluwer Academic Publishers Dordrecht · Zbl 0904.90173
[54] MacCahon, C.S., Using PERT as an approximation of fuzzy project network analysis, IEEE trans. engineering management, 40, 146-153, (1993)
[55] MacCahon, C.S.; Lee, E.S., Project network analysis with fuzzy activity times, Computers and mathematics with applications, 15, 829-838, (1988) · Zbl 0648.90041
[56] MacCahon, C.S.; Lee, E.S., Fuzzy job sequencing for a flow shop, European journal of operational research, 62, 294-301, (1992) · Zbl 0762.90039
[57] MacCarthy, B.; Liu, J., Addressing the gap in scheduling research: A review optimization and heuristic methods in production scheduling, International journal of production research, 31, 59-79, (1993)
[58] Mares, M., Network analysis of fuzzy technologies, (), 115-125
[59] Nasution, S.H., Fuzzy critical path method, IEEE transactions on man, machine and cybernetics, 24, 1, 48-57, (1993)
[60] Özelkan, E.C.; Duckstein, L., Optimal fuzzy counterparts of priority rules, European journal of operational research, 113, 593-609, (1999) · Zbl 0947.90051
[61] Pirlot, M.; Vincke, P., Semiorders: properties, representations, applications, (1997), Kluwer Academic Publishers Dordrecht · Zbl 0897.06002
[62] Prade, H., Using fuzzy set theory in a scheduling problem: A case study, Fuzzy sets and systems, 2, 153-165, (1979) · Zbl 0403.90036
[63] Rommelfanger, H.J., FULPAL: an interactive method for solving (multiobjective) fuzzy linear programming problems, (), 321-330
[64] Rommelfanger, H.J., Network analysis and information flow in fuzzy environment, Fuzzy sets and systems, 67, 119-128, (1994)
[65] Sadeh, N.; Fox, M., Variable and value ordering heuristics for the jobshop scheduling constraint-satisfaction problem, Artificial intelligence, 86, 1-41, (1996)
[66] Slany, W., Scheduling as a fuzzy multiple criteria decision problem, Fuzzy sets and systems, 78, 197-222, (1996)
[67] ()
[68] Stanfield, P.; King, R.; Jones, J., Scheduling arrivals to a production system in a fuzzy environment, European journal of operational research, 93, 75-87, (1996) · Zbl 0912.90182
[69] Turksen, I.B.; Fazel Zarandi, M.H., Production planning and scheduling: fuzzy and crisp/approaches, (), 479-530 · Zbl 0965.90018
[70] vanLaarhoven, P.J.M.; Aarts, E.H.L.; Lenstra, J.K., Job-shop scheduling by simulated annealing, Operations research, 40, 112-125, (1992)
[71] Wang, H.F.; Fu, C.C., Fuzzy project scheduling models under inflation conditions, International journal of uncertainty, fuzziness and knowledge-based systems, 4, 514-597, (1996)
[72] Werners, B.; Weber, R., Decision and planning in research and development, (), 445-478 · Zbl 0972.90041
[73] Yager, R.R., A procedure for ordering fuzzy subsets of the unit interval, Information sciences, 24, 143-161, (1981) · Zbl 0459.04004
[74] Zadeh, L.A., Calculus of fuzzy restrictions, (), 1-39 · Zbl 0327.02018
[75] Zadeh, L.A., Fuzzy sets as a basis for a theory of possibility, Fuzzy sets and systems, 13-28, (1978) · Zbl 0377.04002
[76] Zimmermann, H.-J., Applications of fuzzy set theory to mathematical programming, Information sciences, 36, 28-58, (1985) · Zbl 0578.90095
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.