International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 7, No. 1, 8 Dec. 2014
Cover page and Table of Contents: PDF (size: 503KB)
Modeling the Scheduling Problem of Identical Parallel Machines with Load Balancing by Time Petri Nets
Full Text (PDF, 503KB), PP.42-48
Views: 0 Downloads: 0
Author(s)
Sekhri Larbi
1,*
Slimane Mohamed
1
Index Terms
Scheduling Problem, Load Balancing, Time Petri Net, Identical Parallel Machines
Abstract
The optimal resources allocation to tasks was the primary objective of the research dealing with scheduling problems. These problems are characterized by their complexity, known as NP-hard in most cases. Currently with the evolution of technology, classical methods are inadequate because they degrade system performance (inflexibility, inefficient resources using policy, etc.). In the context of parallel and distributed systems, several computing units process multitasking applications in concurrent way. Main goal of such process is to schedule tasks and map them on the appropriate machines to achieve the optimal overall system performance (Minimize the Make-span and balance the load among the machines). In this paper we present a Time Petri Net (TPN) based approach to solve the scheduling problem by mapping each entity (tasks, resources and constraints) to correspondent one in the TPN. In this case, the scheduling problem can be reduced to finding an optimal sequence of transitions leading from an initial marking to a final one. Our approach improves the classical mapping algorithms by introducing a control over resources allocation and by taking into consideration the resource balancing aspect leading to an acceptable state of the system. The approach is applied to a specific class of problems where the machines are parallel and identical. This class is analyzed by using the TiNA (Time Net Analyzer) tool software developed in the LAAS laboratory (Toulouse, France).
Cite This Paper
Sekhri Larbi, Slimane Mohamed, "Modeling the Scheduling Problem of Identical Parallel Machines with Load Balancing by Time Petri Nets", International Journal of Intelligent Systems and Applications(IJISA), vol.7, no.1, pp.42-28, 2015. DOI:10.5815/ijisa.2015.01.04
Reference
[1]R.W. Conway, W.L. Maxwell and L.W. Miller. Theory of Scheduling. Addison Wesley, Reading, Mass. USA, 1967.
[2]R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan. Optimization and Approximation in Deterministic Sequencing and Scheduling Theory: a survey, Discrete Math. 5, 1979, 287-326.
[3]E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys. Sequencing and Scheduling: Algorithms and Complexity, vol. 4, Handbook in OR and Management Science. North-Holland, Amsterdam, 1993.
[4]Y. Slimani, A. Imine and L. Sekhri, Modelling Parallel Programs: A Formal Approach. International Eurosim Conference. HPCN Challenges in Telecomputing and Telecommunication: Parallel Simulation of Complex Systems and Large Scale Applications, 10-12 June 1996, Delft, the Netherlands.
[5]L. Sekhri, A.K.A Toguyeni and E. Craye. Diagnosability of Automated Production Systems Using Petri Net Based Models, IEEE SMC' 2004, International Conference on Systems, Man and Cybernetics. October 10-13, 2004, Hague, Netherlands.
[6]B. Kechar, L. Sekhri and M. K. Rahmouni, CL-MAC: Energy Efficient and Low Latency Cross-Layer MAC Protocol for Delay Sensitive Wireless Sensor Network Applications. The Mediterranean Journal of Computers and Networks, ISSN:1744-2397,vol.6, No.1, 2010.
[7]K. Hsing-Pei, B. Hsieh and Y. Yingchieh. A Petri Net Based Approach for Scheduling Resource Constrained Multiple Project, JCIIE, vol. 23, No. 6, pp. 468-477, 2006.
[8]C V. Ramamoorthy and M. J. Gonzalez, A Survey of Techniques for Recognizing Parallel Processable Streams in Computer Programs, AFIPS Conf. Proceedings, 1980, pp. 1-15.
[9]J. Carlier and P. Chretienne. Timed Petri Net Schedules, Advances in Petri Nets. Springer, vol. 62/84. 1989.
[10]W.M.P. Van Der Aalst. Petri Net Based Scheduling, Operation Research Spectrum, vol.18, No 4, 1995.
[11]O. Korbaa, A. Benasser and P. Yim. Two FMS Scheduling Methods Based on Petri Net: A Global and a Local Approach, IJPR, vol.41, No.7, pp1349-1371, 2002.
[12]J. K. Hyun, L. Jun-Ho and L.Tae-Eog, A Petri Net-based Modeling and Scheduling with a Branch and Bound Algorithm, IEEE International Conference on Systems, Man and Cybernetics, (SMC’02), October 6-9, 2002, Hammamet, Tunisia.
[13]D. J. Sampathi, Scheduling FMS Using Petri-nets and Genetic Algorithms, IISST, July 2012.
[14]I. S. Pashazadeh and N.E. Abdolrahimi, Modeling Entreprise Architecture Using Timed Colored Petri Nets, Single Processor Scheduling, vol. l5, No.1, 2014.
[15]A. E. Keshk, A. B. El-Sissi and M. A. Tewfeek, Cloud Task Scheduling for Load Balancing based on Intelligent Strategy, International Journal of Intelligent Systems and Applications (IJISA), 2014, 05, 25-36.
[16]R. E. De Grande, M. Almulla and A. Boukerche, Autonomous Configuration Scheme in a Distributed Load Balancing System for HLA-based Simulations, 17th IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications, Delft, The Netherlands, 30 October-1 November, pp. 169-176, 2013.
[17]B. Berthomieu. and M. Menasche. An Enumerative Approach for Analyzing Time Petri Nets. IFIP Congress Series, vol. 9, 1983, pp. 41-46, North Holland.
[18]P. M. Merlin, A Study of the Recoverability Systems of Computing. Irvine Univ. California, PhD thesis, 1974.
[19]T. Murata, Petri Nets: Properties, Analysis and Applications, Proc. of IEEE, vol.77, No. 4, pp. 541-580, 1989.
[20]M. Slimane and L. Sekhri, Modeling the Scheduling Problem of Identical Parallel Machines with Load Balancing by Time Petri Nets. International Symposium on Modeling and Implementation of Complex Systems, (MISC 2010), Constantine, Algeria, May 30-31, 2010.
[21]F. Abdiche, K. Mesghouni and L. Sekhri, Meta-Heuristic Optimization Based on P-Time Petri Nets Model for Deadlock Avoidance in Flexible Manufacturing Systems. 21th International Conference on Production Research. (ICPR 21), July 31-August 4, 2011, Stuttgart, Germany.
[22]Y. Huang. T. Bourdeaud, P. A. Yvars and A. Toguyeni, A Constraint Programming Model for Solving Reachability Problem in Timed Petri nets. ICMOS, 2012 Bordeaux,France.