مدل سازی زمان بندی تولید کارگاهی همراه با دسته ها و زمان راه اندازی توسط شبکه های پتری زمان بندی شده

Batch and setup times are two important factors in practical job shop scheduling. This paper proposes a method to model job shop scheduling problems including batches and anticipatory sequence-dependent setup times by timed Petri nets. The general modeling method is formally presented. The free choice property of the model is proved. A case study extracted from practical scheduling is given to show the feasibility of the modeling method. Comparison with some previous work shows that our model is more compact and effective in finding the best solution.

Batch and setup times appear frequently in real-life scheduling applications. A batch represents the number of jobs that are processed at one time. A setup is a certain machine time before processing an operation. In prior research work, setup times are not considered or treated as part of the processing time. However, in many cases, setup times cannot be neglected and different setup times are required depending on the sequences [1] and [2]. It is necessary to explicitly consider setup times in scheduling. Much recent work paid attention to batch and setup times in scheduling fields. [3], [4], [5] and [6] gave a comprehensive survey of the current research work on batch and setup times. So far, there is no breakthrough in job shop scheduling which considers both batch and sequence-dependent setup times simultaneously. As a powerful and flexible modeling technique, Petri nets are well suited to model the complex constraints in real-life scheduling problems. There is some research work using Petri net-based methods to model and solve scheduling problems [7], [8], [9], [10] and [11]. However, few considered setup times and batches. [12] gave formal mapping rules from general scheduling problems to timed Petri net models, but it did not consider batch or setup times. [13] considered sequence-dependent setup times but batches have not been taken into account. In addition, its model did not permit anticipatory setups [5], where the machine setup can be started before the corresponding jobs or batches become available on the machine. [14] considered many practical situations including batches, setup times and transportation times. However, the batch term in it means the number of jobs belonging to the same family [5]. The real batch in the model is one. On the other hand, it did not consider anticipatory setups either. As non-anticipatory setup times may hinder maximal concurrency and thus adversely affect the solution quality in many occasions, we give our method to model job shop scheduling problems by timed Petri nets. Both batch and anticipatory sequence-dependent setup times are considered. The proposed model is proved to be free choice and it bears many advantages through comparing with previous work. The rest of the paper is organized as follows. Section 2 defines the scheduling problem and timed Petri net. In Section 3, the general modeling method is proposed. We prove the free choice property of the generated model in Section 4. Section 5 presents a case study and comparisons. Finally, we conclude the paper in Section 6.

In this paper, we investigated modeling job-shop scheduling problems considering both batch and anticipatory sequence-dependent setup times by timed Petri nets. The general modeling method is explained. The free choice property of the model is proved. An example shows the usability of this method. When compared with other previous research work, our modeling method has the merits that it can easily model batches and setup times in the scheduling problems; the TPN models generated are of a suitable scale; it can avoid useless cyclical set ups and re-set ups and it permits anticipatory setups which is more effective in finding the best solution.