PETRI-NET BASED PROCESS SCHEDULING - A MODEL OF THE CONTROL-SYSTEM OFFLEXIBLE MANUFACTURING SYSTEMS

In this paper, we propose a class of algorithms for the sub-optimal so lution of a particular class of problems of process scheduling, partic ularly focusing on a case study in the area of flexible manufacturing systems (FMSs). The general class of problems we face in our approach is characterized as follows: there is a set of concurrent processes, e ach formed by a number of temporally related tasks (segments). Tasks a re executable by alternate resource sets, different both in performanc e and costs. Processes and tasks are characterized by release times, d ue dates, and deadlines. Time constraints are also present in the avai lability of each resource in resource sets. It has been proven that su ch a problem does not admit an algorithm for an optimal solution in po lynomial time. Our proposed algorithm finds a sub-optimal schedule acc ording to a set of optimization criteria, based on task and process ti mes (earliness, tardiness), and/or time independent costs of resources . Our approach to process scheduling is based on Timed Coloured Petri Nets. We describe the structure of the coordination and scheduling alg orithms, concentrating on (i) the general-purpose component, and (ii) the application-dependent component. In particular, the paper focuses on the following issues: (i) the automatic synthesis of Petri net mode ls of the coordination subsystem, starting from the problem knowledge base; (ii) the dynamic behavior of the coordination subsystem, whose k ernel is a High Level Petri net executor, a coordination process based on an original, general purpose algorithm; (iii) the structure of the real-time scheduling subsystem, based on particular heuristic sub-opt imal multi-criteria algorithms. Furthermore, the paper defines the int eraction mechanisms between the coordination and scheduling subsystems . Our approach clearly distinguishes the mechanism of the net executio n from the decision support system. Two conceptually distinct levels, which correspond to two different, interacting implementation modules in the prototype CASE tool, have been defined: the executor and the sc heduler levels. One of the outstanding differences between these level s is that the executor is conceived as a fast, efficient coordination process, without special-purpose problem-solving capabilities in case of conflicts. The scheduler, on the other hand, is the adaptive, distr ibuted component, whose behavior may heavily depend on the problem cla ss. If the scheduler fails, the executor is, in any case, able to proc eed with a general-purpose conflict resolution strategy. Experimental results on the real-time performance of the kernel of the implemented system are finally shown in the paper. The approach described in this paper is at the basis of a joint project with industrial partners for the development of a CASE tool for the simulation of blast furnaces.