A very fast scheduling system is proposed and experimentally investigated. The system consists of a job shop manager and dynamic models of machines. A schedule is created in the course of a close cooperation with models of the machines that generate driving events for the scheduler. The system is implemented with a new class of extended Petri nets and runs in the environment of the Petri-net tool WINSIM. The scheduler creates a schedule sequentially, without any form of enumerative search. To investigate the scheduler performance, a large number of experiments were conducted with the use of few strategies. Due to a unique mechanism of monitoring of triggering events in the Petri net, the developed scheduler runs at least hundreds of times faster than any known single-processor job shop scheduler.
Top1. Introduction
Job shop scheduling is one of the most complex combinatorial problems. Being important from both theoretical and practical points of view, it a subject of intensive research starting in 60s of the previous century (Fisher and Thompson, 1963). Due to the difficulty in finding the exact solution of sufficiently large job shop scheduling problems, almost all of them apply heuristic methods that are in common use in the field of artificial intelligence (Yahyaoui and Fnaiech, 2006), (Sun et al., 2009), (Uslu and Bulkan, 2015), (Zang et al., 2019). The word “heuristic” means here any technique that might find a solution of the underlying problem, but does not guarantee to achieve its optimal solution (Grosan and Abraham, 2011). Nevertheless, in many cases heuristic methods allow to obtain a good approximation of the exact solution within acceptable computer time.
More and more often job shop schedulers are represented and investigated in terms of Petri nets in combination with artificial intelligence approaches. One of the first attempts to merge Petri nets with artificial intelligence is undertaken in (Martinez, 1989). In subsequent years, more researches were published in this area (Javor, 1995), (Bulitko and Wilkins, 1999), (Moro, 2000), (Huang and Liao, 2006). In general, Petri nets, being an efficient mathematical and graphical tool for modeling of information systems, allow to express the scheduler as a discrete system, investigate it formally and achieve better results than with traditional heuristic methods.
The goal of this chapter is the development and experimental investigation of a novel heuristic job shop scheduling scheme with the use of a new class of extended Petri nets. The proposed scheme is a system that includes not only the scheduler itself but also machines for which a schedule is created and which apply the schedule immediately in the course of its creation. As will be shown later, the design of a scheduler together with the machines allows to obtain a feedback information from the machines and to considerably speed up the creation of the scheduler for given input data.
In its deterministic form, the job scheduling problem can be stated formally as follows. Consider two finite sets of jobs and machinesJ = {J1, J2, …, Jn }, M = {M1, M2, …, Mm },(1) where n and m are the numbers of jobs and machines, respectively. Each job Ji consists of an ordered sequence of tasks or operationsSi = [
], i = 1, 2, …, n,(2) where 
is the irth task of job i to be processed by machine kr, kr ϵ {1, 2, …, m}, with ir ϵ {1, 2, …, m}. It is assumed that the number of tasks of each job is equal to the number of machines. Each task of each job should be processed on one and only one pre-assigned machine. It is assumed further that, for each job task, there is an associated time to process the task on the corresponding machine.
In the following text, there is a clear distinction between terms “task” and “scheduling problem”. The former is an operation or a step of a job, but the latter means the complete set of jobs and related machines, for which a schedule is created.
The sequence of tasks (2) is in general different for different jobs. It is assumed also that a new task of each job can be started on a free machine only after finishing its previous task. In addition, any machine can be used by job tasks only in a mutually exclusive way.