Back to search

University of British Columbia

A Petri net formulation for the general scheduling problem

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Applied Science - MASc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor dc:publisher
University of British Columbia
Year dc:date
1981

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Imai, Michael Kenji

Rights

dc:rights
Statement dc:rights
  • 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.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/22797

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Imai, Michael Kenji. A Petri net formulation for the general scheduling problem. master's thesis, University of British Columbia, 1981. http://hdl.handle.net/2429/22797