Cyclic scheduling for F.M.S.: Modelling and evolutionary solving approach. (English) Zbl 1147.90005
Summary: This paper concerns the domain of flexible manufacturing systems (FMS) and focuses on the scheduling problems encountered in these systems. We have chosen the cyclic behaviour to study this problem, to reduce its complexity. This cyclic scheduling problem, whose complexity is NP-hard in the general case, aims to minimise the work in process (WIP) to satisfy economic constraints. We first recall and discuss the best known cyclic scheduling heuristics. Then, we present a two-step resolution approach. In the first step, a performance analysis is carried out; it is based on the Petri net modelling of the production process. This analysis resolves some indeterminism due to the system’s flexibility and allows a lower bound of the WIP to be obtained. In the second step, after a formal model of the scheduling problem has been given, we describe a genetic algorithm approach to find a schedule which can reach the optimal production speed while minimizing the WIP. Finally, our genetic approach is validated and compared with known heuristics on a set of test problems.
MSC:
| 90B30 | Production models |
| 90B35 | Deterministic scheduling theory in operations research |
| 90B10 | Deterministic network models in operations research |
References:
| [1] | Campos, J.; Chiola, G.; Colom, J. M.; Silva, M., Properties and performance bounds for timed marked graphs, IEEE Transactions on circuits and systems I: Fundamental theory and applications, 39, n°5, 386-401 (1992) · Zbl 0825.68234 |
| [2] | Camus, H., Ohl, H., Korbaa, O., Gentina, J.-C., 1996. Cyclic schedules in flexible manufacturing systems with flexibilities in operating sequences. In: Proceedings of the Seventeenth International Conference on Application and Theory of Petri nets (ICATPN), Osaka, Japan, pp. 97-116, June.; Camus, H., Ohl, H., Korbaa, O., Gentina, J.-C., 1996. Cyclic schedules in flexible manufacturing systems with flexibilities in operating sequences. In: Proceedings of the Seventeenth International Conference on Application and Theory of Petri nets (ICATPN), Osaka, Japan, pp. 97-116, June. |
| [3] | Cheng, R. W.; Gen, M.; Tsujimura, Y., A tutorial survey of job-shop scheduling problems using genetic algorithms, partII: Hybrid genetic search strategies, Computers and Industrial Engineering, 36, n°2, 343-364 (1999) |
| [4] | Chrétienne, P., 1996. List schedules for cyclic scheduling, Technical report Litp 1996/34.; Chrétienne, P., 1996. List schedules for cyclic scheduling, Technical report Litp 1996/34. |
| [5] | Draper, L.D., Jonsson, A.K., Clements, D.P., Joslin, D.E., 1999. Cyclic Scheduling. In: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence IJCAI’99, Stockholm, Sweden July 31-August 6.; Draper, L.D., Jonsson, A.K., Clements, D.P., Joslin, D.E., 1999. Cyclic Scheduling. In: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence IJCAI’99, Stockholm, Sweden July 31-August 6. |
| [6] | Ershler, J., Leveque, D., Roubella, F., 1982. Periodic loading of flexible manufacturing systems, IFIP Congress, APMS, Bordeaux, France, pp.327-339.; Ershler, J., Leveque, D., Roubella, F., 1982. Periodic loading of flexible manufacturing systems, IFIP Congress, APMS, Bordeaux, France, pp.327-339. |
| [7] | Fisher, H., Thompson, G.L., 1963. Probabilistic learning combinations of local job-shop scheduling rules. In: J.F. Muth G.L. Thompson (Eds.), Industrial Scheduling, Prentice Hall, Englewood Cliffs, New Jersey, pp. 225-251.; Fisher, H., Thompson, G.L., 1963. Probabilistic learning combinations of local job-shop scheduling rules. In: J.F. Muth G.L. Thompson (Eds.), Industrial Scheduling, Prentice Hall, Englewood Cliffs, New Jersey, pp. 225-251. |
| [8] | Goldberg, D. E., Genetic Algorithms in Search, Optimisation and Machine Learning (1989), Addison-Wesley Publishing Company · Zbl 0721.68056 |
| [9] | Hanen, C. et Munier, A., 1995. Cyclic scheduling on parallel processors: An overview, scheduling theory and its applications: Chretienne P., Coffman E.G., Lenstra J.K. Liu Z. (Eds.), Chapter 7, John Wiley and Sons Ltd.; Hanen, C. et Munier, A., 1995. Cyclic scheduling on parallel processors: An overview, scheduling theory and its applications: Chretienne P., Coffman E.G., Lenstra J.K. Liu Z. (Eds.), Chapter 7, John Wiley and Sons Ltd. · Zbl 0830.68009 |
| [10] | Hillion, H.P., Proth, J.M. et Xie, X.L., 1987. A heuristic algorithm for the periodic scheduling and sequencing job-shop problem. In: Twenty-sixth IEEE Conference on Decision and Control, Los Angeles, U.S.A., pp. 612-617.; Hillion, H.P., Proth, J.M. et Xie, X.L., 1987. A heuristic algorithm for the periodic scheduling and sequencing job-shop problem. In: Twenty-sixth IEEE Conference on Decision and Control, Los Angeles, U.S.A., pp. 612-617. |
| [11] | Hillion, H.P., et Proth, J.M., 1988. Analyse de fabrications non linéaires et répétitives à l’aide des Graphes d’Evénements Temporisés, RAIRO, Vol 22, n° 2, September.; Hillion, H.P., et Proth, J.M., 1988. Analyse de fabrications non linéaires et répétitives à l’aide des Graphes d’Evénements Temporisés, RAIRO, Vol 22, n° 2, September. |
| [12] | Hillion, H. P.; Proth, J. M., Performance evaluation of job-shop systems using timed event-graphs, IEEE Transactions on Automatic Control, 34, n°1, 3-9 (1989) · Zbl 0656.90054 |
| [13] | Hsu, T., Dupas, R., Goncalves, G., 2002. A genetic algorithm to solving the problem of FMS cyclic scheduling, Session: Cyclic scheduling modelling and benchmarks, IEEE SMC02 Systems, Man and Cybernetics, Hammamet, Tunisia, 6-9 October.; Hsu, T., Dupas, R., Goncalves, G., 2002. A genetic algorithm to solving the problem of FMS cyclic scheduling, Session: Cyclic scheduling modelling and benchmarks, IEEE SMC02 Systems, Man and Cybernetics, Hammamet, Tunisia, 6-9 October. |
| [14] | Jain, A. K.; Elmaraghy, H. A., Production scheduling/rescheduling in flexible manufacturing, International Journal of Production research, 35, 281-309 (1997) · Zbl 0949.90645 |
| [15] | Korbaa, O., Camus, H., Gentina, J.-C., 1997. FMS Cyclic Scheduling with overlapping production cycles. In: Conference on Application and Theory of Petri nets (ICATPN), Toulouse (France), pp. 35-53, June.; Korbaa, O., Camus, H., Gentina, J.-C., 1997. FMS Cyclic Scheduling with overlapping production cycles. In: Conference on Application and Theory of Petri nets (ICATPN), Toulouse (France), pp. 35-53, June. |
| [16] | Korbaa, O., 1998. Commande cyclique des systèmes flexibles de production manufacturière à l’aide des réseaux de Petri: de la planification à l’ordonnancement des régimes transitoires, Thèse de doctorat, Université de Lille1.; Korbaa, O., 1998. Commande cyclique des systèmes flexibles de production manufacturière à l’aide des réseaux de Petri: de la planification à l’ordonnancement des régimes transitoires, Thèse de doctorat, Université de Lille1. |
| [17] | Korbaa, O.; Korbaa, H.; Gentina, J.-C., A new cyclic scheduling algorithm for flexible manufacturing systems, International Journal of Flexible Manufacturing Systems (IJFMS), 14, n° 2 (2002) |
| [18] | Laftit, S.; Proth, J. M.; Xie, X. L., Optimization of invariant criteria for event graphs, IEEE Transactions on Automatic Control, 37, n° 1, 547-555 (1992) · Zbl 0763.90053 |
| [19] | Laftit, S., Proth, J.M., Xie, X.L., 1993. Marking optimization in timed event graphs. Lecture Notes in Computer Science 674.; Laftit, S., Proth, J.M., Xie, X.L., 1993. Marking optimization in timed event graphs. Lecture Notes in Computer Science 674. |
| [20] | Lawrence, S., 1984. Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques, graduate school of industrial administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania.; Lawrence, S., 1984. Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques, graduate school of industrial administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania. |
| [21] | Lee, J.; Korbaa, O., Modeling and analysis of ratio-driven FMS using unfolding time Petri nets, Computers and Industrial Engineering (CIE), 46/4, 639-653 (2004) |
| [22] | Mattfeld, D.C., 1999. Production scheduling and rescheduling with genetic algorithm, Evolutionary Computation Spring, Vol. 7 n°1, pp. 1-18.; Mattfeld, D.C., 1999. Production scheduling and rescheduling with genetic algorithm, Evolutionary Computation Spring, Vol. 7 n°1, pp. 1-18. |
| [23] | Michalewicz, Z., Genetic Algorithms+Data Structures=Evolution Programs (1996), Springer Verlag: Springer Verlag Berlin/Heidel-berg/New York · Zbl 0841.68047 |
| [24] | Murata, T., 1989. Petri nets: Properties, analysis and applications. In: Proceedings of the IEEE, 77(4), pp. 541-580, April.; Murata, T., 1989. Petri nets: Properties, analysis and applications. In: Proceedings of the IEEE, 77(4), pp. 541-580, April. |
| [25] | Ohl, H., Camus, H., Castelain E. et Gentina, J.-C., 1995. Petri net modeling of ratio-driven flexible manufacturing systems and implications on the WIP for cyclic schedules. In; IEEE Conference on Systems, Man and Cybernetics, Vancouver, British Columbia, Canada, Vol. 4, n° 5, pp. 3081-3086, October.; Ohl, H., Camus, H., Castelain E. et Gentina, J.-C., 1995. Petri net modeling of ratio-driven flexible manufacturing systems and implications on the WIP for cyclic schedules. In; IEEE Conference on Systems, Man and Cybernetics, Vancouver, British Columbia, Canada, Vol. 4, n° 5, pp. 3081-3086, October. |
| [26] | Ramamoorthy, C. V.; Ho, G. S., Performance evaluation of asynchronous concurrent systems using Petri nets, IEEE Transactions on Software Engineering, SE-6, n°5, 440-449 (1980) · Zbl 0444.68044 |
| [27] | Serafini, P.; Ukovich, W., A mathematical model for periodic scheduling problems, SIAM Journal Discrete Mathematics, 2, n°4, 550-581 (1989) · Zbl 0676.90030 |
| [28] | Valentin, C., 1994. Modeling and Analysis Methods for a Class of Hybrid Dynamic Systems. In: Proceedings of ADPM ’94, Brussels, Belgium, pp. 221-226, November.; Valentin, C., 1994. Modeling and Analysis Methods for a Class of Hybrid Dynamic Systems. In: Proceedings of ADPM ’94, Brussels, Belgium, pp. 221-226, November. |
| [29] | Yamada, T.; Nakano, R., A genetic algorithm applicable to large scale job shop problems, (Männer, R.; Manderick, B., Proceedings of the Second International Conference on Parallel Problem Solving from Nature (1992), Elsevier: Elsevier North Holland) |
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.
