Cyclic processes scheduling

• Autorzy: Bocewicz G. , Banaszak Z.
• Języki publikacji: EN

Abstrakty

EN

In everyday practice cyclic scheduling problems, especially timetabling ones arise in different application and service domains, e.g., class, train, crew timetabling, and so on. In many cases, e.g., caused by assumed slot size, imposing integer domain results in Diophantine character of problems considered. In that context some classes of cyclic scheduling problems can be seen as non-decidable (undecidable) ones. That means, since system constraints (i.e., parameter domains) determine its behavior (e.g., the space of feasible schedules), hence both system structure configuration and desired schedule have to be considered simultaneously. So, cyclic scheduling problem solution requires that the system structure configuration must be determined for the purpose of processes scheduling, yet scheduling must be done to devise the system configuration. In that context, this contribution provides discussion of some solubility issues concerning cyclic processes dispatching problems.

Słowa kluczowe

EN

cyclic processes; cyclic scheduling; time-table; periodicity; periodic timetables; dispatching rule

• Wydawca: Polskie Towarzystwo Promocji Wiedzy ; Lublin University of Technology
• Czasopismo: Applied Computer Science
• Rocznik: 2010
• Tom: Vol. 6, no 2
• Strony: 41--70
• Opis fizyczny: Bibliogr. 33 poz., fig.

Twórcy

autor

Bocewicz G.

• Department of Computer Science and Management, Koszalin University of Technology, ul. Śniadeckich 2, 75-354 Koszalin, Poland

autor

Banaszak Z.

• Department of Business Informatics, Warsaw University of Technology, ul. Narbutta 85, 02-524 Warszawa, Poland

Bibliografia

• [1] ALCAIDE D., CHU CH., KATS V., LEVNER E, SIERKSMA G.: Cyclic multiple-robot scheduling with time-window constraints using a critical path approach. In: European Journal of Operational Research, Vol. 177, 2007, pp. 147–162.
• [2] BACH I., BOCEWICZ G., BANASZAK Z.: Constraint programming approach to time-window and multiresource-constrained projects portfolio prototyping. In: Industrial, Engineering and Other Applications of Applied Intelligent Systems, Lecture Notes in Artificial Intelligence LNAI, Vol. 5027, Springer-Verlag, Berlin-Heidelberg, 2008, pp. 767-776.
• [3] BIRGER R., EL-HOUSSAINE A., WOUT D.: Cyclic scheduling of multiple tours with multiple frequencies for a single vehicle. In: International Journal of Logistics Systems and Management 2009, Vol. 5, No.3/4, 2009, pp. 214 – 227.
• [4] BOCEWICZ G., WÓJCIK R., BANASZAK Z., On Undecidability of Cyclic Scheduling Problems, In: Mapping Relational Databases to the Semantic Web with Original Meaning, Lecture Notes in Computer Science LNAI, Vol. 5914, Springer-Verlag, Berlin-Heidelberg 2009, pp. 310-321.
• [5] BOCEWICZ G., WÓJCIK R., BANASZAK Z., AGVs distributed control subject to imprecise operation times. In: Agent and Multi-Agent Systems: Technologies and Applications, Lecture Notes in Artificial Intelligence LNAI, Vol. 4953, Springer-Verlag, Berlin-Heidelberg 2008, pp. 421-430. 69
• [6] BOCEWICZ G., BANASZAK Z., WÓJCIK R.: Design of admissible schedules for AGV systems with constraints: a logic-algebraic approach. In: Agent and Multi-Agent Systems: Technologies and Applications, Nguyen N.T., Grzech A., et al. (Eds.), Lecture Notes in Artificial Intelligence 4496, Springer-Verlag, Berlin-Heidelberg 2008, pp. 578-587.
• [7] CAI X., LI K.N.: A genetic algorithm for scheduling staff of mixed skills under multi-criteria. In: European Journal of Operational research, 125, 2000, pp. 359-369.
• [8] CAMUS, H., OHL, H., KORBAA, O., GENTINA, J.-C.: Cyclic Schedules in Flexible Manufacturing Systems with Flexibilities in operating sequences. In: Proceedings of the 17th International Conference on Application and Theory of Petri Nets (ICATPN), 1996, pp. 97-116.
• [9] CHE A., CHU CH.: Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots. In: European Journal of Operational Research, Vol. 199, 2009, pp. 77–88.
• [10] DAVIS M., (1973). Hilbert's Tenth Problem is Unsolvable. In: Amer. Math. Monthly 80,233-269.
• [11] ERNST A.T., JIANG H., KRISHNAMOORTHY M., OWENS B., SIER D.:. An annotated bibliography of personnel scheduling and rostering. In: Annals of Operations Research, 127, 2009, pp. 21-144.
• [12] FOURNIER, O., LOPEZ, P., LAN SUN LUK, J.-D.: Cyclic scheduling following the social behavior of ant colonies. In. Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, 2002, pp. 450-454.
• [13] GAUJAL B., JAFARI M., BAYKAL-GURSOY M., ALPAN G.: Allocation sequences of two processes sharing a resource. IEEE. In: Trans. on Robotics and Automation, Vol.11, No. 5, 1995, pp. 748-353.
• [14] GULTEKIN H., SELIM AKTURK M., KARASAN O. E.: Cyclic scheduling of a 2-machine robotic cell with tooling constraints. In: European Journal of Operational Research, Vol. 174, 2006, pp. 777–796.
• [15] GUY, R. K.: Diophantine Equations. Ch. D in Unsolved Problems in Number Theory, 2nd ed. In: Springer-Verlag, New York, 1994, pp. 139-198.
• [16] HANEN C.: Theory and Methodology Study of a NP-hard cyclic scheduling problem: The recurrent job-shop. In: European Journal of Operational Research, Vol. 72, 1994, pp. 82-101.
• [17] HANEN, C., KORDON M.: A. Periodic schedules for linear precedence constraints. In.: Discrete Applied Mathematics, Vol. 157 (2), 2009, pp. 280-291.
• [18] HSU T., KORBAA O., DUPAS R., GONCALVES G.: Cyclic scheduling for F.M.S.: Modelling and evolutionary solving approach. In: European Journal of Operational Research, Vol. 191, 2008, pp. 464–484.
• [19] KATS V., LEI L., LEVNER E.: Minimizing the cycle time of multiple-product processing networks with a fixed operation sequence, setups, and time-window constraints. In: European Journal of Operational Research, Vol. 187, 2008, pp. 1196–1211.
• [20] KORBAA, O., CAMUS, H., GENTINA, J.-C.: A new cyclic scheduling algorithm for flexible manufacturing systems. In: International Journal of Flexible Manufacturing Systems, Vol. 14 (2), 2002, pp. 177-191.
• [21] LIEBCHEN, C., MÖHRING, R.H.: A case study in periodic timetabling. In: Electronic Notes in Theoretical Computer Science, Vol. 66 (6), 2002, pp. 21-34.
• [22] LEVNER E., KATS V., ALCAIDE D., PABLO L:, CHENG T.C.E.: Complexity of cyclic scheduling problems: A state-of-the-art survey,. In: Computers & Industrial Engineering , (In print)
• [23] MCCORMICK S. T., RAO U. S.: Some Complexity Results in Cyclic Scheduling. In: Mathl. Comput. Modelling, Vol. 20, No. 2, pp. 107-122.
• [24] ODIJK, M.A.: A constraint generation algorithm for the construction of periodic railway timetables. In: Transportation Research Part B: Methodological, Vol. 30 (6), 1996, pp. 455-464.
• [25] PINEDO M. L.: Planning and scheduling in manufacturing and services. In: Springer-Verlag, New York, 2005.
• [26] POLAK M., MAJDZIK P., BANASZAK Z., WÓJCIK R.: The performance evaluation tool for automated prototyping of concurrent cyclic processes. Fundamenta Informatice. In: ISO Press, Editor-in-Chief, A. Skowron, Vol. 60, No.1-4, 2004, pp.269-289.
• [27] SMART NIGIEL P.: The Algorithmic Resolution of Diophantine Equations. In: London Mathematical Society Student Text, 41. Cambridge University Press, Cambridge, 1998
• [28] SPRINDZUK, VLADIMIR G.: Classical Diophantine equations. In: Lecture Notes in Mathematics, Vol. 1559. Springer-Verlag, Berlin 1993, 228 pp.
• [29] SONG J.-S., LEE T.-E.: Petri net modeling and scheduling for cyclic job shops with blocking. In: Computers & Industrial Engineering,Vol.34, No.2, 1998, pp. 281–295
• [30] SOON-KI HEO, KYU-HWANG LEE, HO-KYUNG LEE, IN-BEUM LEE, AND JIN HYUN PARK: A New Algorithm for Cyclic Scheduling and Design of Multipurpose Batch Plants. In: Ind. Eng. Chem. Res., 42 (4), 2003, pp. 836–846
• [31] TROUILLET B., KORBAA O, GENTINA J.-C.: Formal Approach for FMS Cyclic Scheduling. In: IEEE SMC Transactions, Part C, 37, Issue 1, 2007, pp. 126-137
• [32] WANG, B., YANG, H., ZHANG, Z.-H.: Research on the train operation plan of the Beijing-Tianjin inter-city railway based on periodic train diagrams. In: Tiedao Xuebao/Journal of the China Railway Society, Vol. 29 (2), 2007, pp. 8-13
• [33] VON KAMPMEYER T.: Cyclic scheduling problems, Ph.D. Dissertation, Fachbereich Mathematik/Informatik, Universität Osnabrück, 2006