This Article Full Text (OnlineFirst PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Scopus Google Scholar Articles by Li, L. Articles by Hadjicostis, C. N Social Bookmarking                         What's this?

Least-cost planning sequence estimation in labelled Petri nets

¹ Department of Electrical and Computer Engineering, Indiana University-Purdue University Indianapolis, Indianapolis, IN, USA
² Department of Electrical and Computer Engineering, University of Cyprus, Nicosia, Cyprus and University of Illinois at Urbana-Champaign, Urbana, IL, USA

^* To whom correspondence should be addressed. E-mail: chadjic{at}illinois.edu.

	Abstract

This paper develops a recursive algorithm for estimating the least-cost planning sequence in a manufacturing system that is modelled by a labelled Petri net. We consider a setting where we are given a sequence of labels that represents a sequence of tasks that need to be executed during a manufacturing process, and we assume that each label (task) can potentially be accomplished by a number of different transitions, which represent alternative ways of accomplishing a specific task. The processes via which individual tasks can be accomplished and the interactions among these processes in the given manufacturing system are captured by the structure of the labelled Petri net. Moreover, each transition in this net is associated with a non-negative cost that captures its execution cost (eg, in terms of the amount of workload or power required to execute the transition). Given the sequence of labels (ie, the sequence of tasks that has to be accomplished), we need to identify the transition firing sequence(s) (ie, the sequence(s) of activities) that has (have) the least total cost and accomplishes (accomplish) the desired sequence of tasks while, of course, obeying the constraints imposed by the manufacturing system (ie, the dynamics and structure of the Petri net). We develop a recursive algorithm that finds the least-cost transition firing sequence(s) with complexity that is polynomial in the length of the given sequence of labels (tasks). An example of two parallel working machines is also provided to illustrate how the algorithm can be used to estimate least-cost planning sequences.

First published on September 7, 2009
Transactions of the Institute of Measurement and Control 2009, doi:10.1177/0142331208100106


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?