Open Collections

A Petri net formulation for the general scheduling problem

University of British Columbia

This thesis introduces a new Petri net formulation for the general scheduling problem. The first part of this thesis concerns the development of the Petri net formulation. The Petri net formulation is a synthesis of concepts from three classes of Petri nets, marked graphs, timed Petri nets and coloured Petri nets. The general approach to the scheduling problem begins with the construction of a Petri net which models the structure of the general scheduling problem. The scheduling strategy is modeled by modifying the algorithm for the analysis of Petri nets. A schedule is generated by the execution of the Petri net model under the modified analysis. In the second part of this thesis, The Petri net formulation is used for the analysis of a particular scheduling problem. The problem addressed is the scheduling of a task system on a set of processors of different speeds. The scheduling strategy to be analyzed is list scheduling. A new heuristic is proposed for the ordering of the tasks into a list. The proposed heuristic combines notions from the highest levels first heuristic and the longest processing time heuristic. The performance of the proposed heuristic is evaluated by a comparision with other list ordering heuristics. The schedules which are generated by the proposed heuristic are compared to the schedules which are generated by the highest levels first heuristic, the Coffman and Graham Algorithm A and a random list for fifteen precedence constraints. The proposed heuristic generated a better schedule in 98 of 160 cases tested for the 15 precedence constraints. The proposed heuristic generated a schedule as good as the schedule which is generated by any other list in a further 39 cases.

Text

2010-03-26

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/22797

Electrical and Computer Engineering

University of British Columbia

Graduate