Timed petri net based optimal scheduling for garment flexible productions

doi:10.15406/jteft.2017.02.00055

Journal of

eISSN: 2574-8114

Textile Engineering & Fashion Technology

Research Article Volume 2 Issue 2

Timed petri net based optimal scheduling for garment flexible productions

Xiaohua Wang, Ruiqing Wang,

Verify Captcha

Regret for the inconvenience: we are taking measures to prevent fraudulent form submissions by extractors and page crawlers. Please type the correct Captcha word to see email ID.

Lei Zhang, Hongwei Zhang

College of Electrics and Information, Xi'an Polytechnic University, China

Correspondence: Ruiqing Wang, Master Degree Candidate, Xi?an Polytechnic University, Xi'an, Shaanxi Province, China, Tel 15802977982

Received: May 30, 2017 | Published: July 11, 2017

Citation: Xiaohua W, Ruiqing W, Zhang L, et al. Timed Petri net based optimal scheduling for garment flexible productions. J Textile Eng Fashion Technol. 2017;2(2):343-349. DOI: 10.15406/jteft.2017.02.00055

Download PDF

Abstract

The process sequence of universal garment hanging system is carried out according to the order of the single task process only. In this paper, Petri nets are used to realize the flexible optimal scheduling of the process in multitask garment production. By considering the competition for equipment resources among process in garment hanging system and the firing rules of transitions, analysis and obtain the process optimal scheduling policy algorithm. The optimal processing sequence and time are obtained by Petri nets simulation. According to the example analysis of the multiple sets of different clothing multitask production, verify the effectiveness of process scheduling in the garment hanging system, and improve the flexible degree of the system.

Keywords: garment hanging system, timed petri net, flexible production, process optimization

Abbreviations

S, Seconds; TPPN, Timed Place Petri Nets

Introduction

With the aggravation of market competition and the improvement of social material level, modern clothing enterprises gradually shift to small batch, multi variety and short cycle production mode.¹ The garment hanging system developed in the 70s Century gradually evolved into the modern transition system with rapid response production technology. It is the centralized application of electromechanical integration technology in garment industry. The cut pieces for processing put on special hangers in the process of production, which transferred into the workstation orderly, and the whole processes completed in hanging state. The flexibility of current garment hanging system is not high although it can quickly replace the production type. Moreover, many problems may appear in multiple clothing productions, such as equipment competitions, assembly line balance, workstation configuration and so on.

People have carried out the research on the optimization of the garment hanging system.^2,3 Yu et al. ⁴ presented the ant colony algorithm to rearrange the locations and workers of workstations without considering the production of different types of clothing. The fitting curve method was used to correct the standard hours of different batch sizes,⁵ which can concluded the man-hour quota of small batch and many varieties production. However, there is no specific control policy of various resources. Mork et al.⁶ provided the genetic algorithm to plan the allocation of job orders in complex and mixed production environment, while there is no study of specific process competition for resources. As a modeling and analysis tool for discrete event systems, Petri nets have been widely used in the control and scheduling of flexible manufacturing systems.^7-9 Su et al.¹⁰ proposed the Timed Place Petri Net model established for a manufacturing system with three processes, and searched for the transition sequence of the model by nested partition algorithm, then optimized the completion time of different batches. However, this method cannot apply in the dynamic scheduling problem. Research by Liu¹¹ and Tian et al.¹² show that the Petri net model based on ant colony optimization can realize the unity of the static modeling and dynamic optimization of the scheduling problem. However, this method is more complicated in multitask processing. Zhou et al.¹³ established the Timed Place Petri Nets model for batch chemical system, combined the model with the optimal scheduling policy, gave the valve control strategies and made the system run efficiently. Zhang et al.¹⁴ applied Petri nets theory in the balance of garment production line, while it did not give specific modeling method and production line balance algorithm.

The limited equipment resources of the production line of garment hanging system make the reasonable arrangement of the process in multitask production become the key problem to improve the flexibility of the system. According to the above literatures, Petri nets possess considerable superiority in the optimal scheduling of flexible manufacturing systems. By considering the correlation between the factors of process and time, this paper adopts the Timed Place Petri Nets as the modeling method on the process optimization problem of garment hanging system. According to the constraint conditions and optimization objectives of the production line, an optimal scheduling algorithm is proposed. Through the analysis of a variety of cases, this method is proved to be effective to solve multitask process optimization problems and can improve the efficiency of the system.

Materials and methods

The basic Petri net is a 4-tuple $N = (P, T, F, W)$ , where P and T is finite, nonempty, and disjoint sets. P is a set of places and T is a set of transitions, and $F \subseteq (P \times T) \cup (T \times P)$ is a set of directed arcs with arrows between transitions and places. The element $W : F \to N^{+}$ where $N^{+}$ is the set of positive integers, is a mapping that assigns a weight to each arc, and W is called the weight function of Petri net N. When a graph is used to represent a Petri net, the place is represented by a circle and transition represented by a rectangle. The marking M of a Petri net is a mapping from P to N, $(N, M_{0})$ is called the marked Petri net where is the sum of tokens in all places at initial state of a system, and it is called initial marking of N. Marked Petri net can be expressed as $N = (P, T, F, W, M_{0})$ , and the firing rules of transitions are described as follows. A transition $t \in T$ is enabled at the marking M, if and only if $\forall p \in {}^{•}t$ , $M (p) \geq W (p, t)$ . After firing the enabled transitions, the system leaps to another state and yields a new marking $M^{'}$ , and $\forall p \in P, M^{'} (p) = M (p) - W (p, t) + W (t, p)$ . The definition of TPPN (Timed Place Petri Nets) is $T P P N = (P, T, F, W, M_{0}, D)$ where D={ $d_{1}$ , $d_{2}$ ,…, $d_{n}$ } is the time delay set of places, $d_{i}$ is the time delay of $p_{i}$ , $i \in (1, n)$ . After the fire of a transition t, the corresponding number of tokens moved from input to output places. The tokens put into $p_{i}$ should hold for time $d_{i}$ before it becomes available.

TPPN method modeling garment hanging system

Assuming that n tasks $J_{1}, J_{2}, ..., J_{n}$ are taken to manufacture n kinds of clothes, the number of process involves in each task is $X_{1}, X_{2}, ..., X_{n}$ respectively. Operation of these tasks requires certain resource units, such as ironing table, cup seaming machine, double needle lockstitch sewing machine, cylindrical crimping machine and so on. Otherwise, there is one device for each kind of equipment. Take task $J_{i}$ as an example, the required cut pieces put on the circular guide rail of the hanging system by computer control, which will send the pieces to workstations according to the order of the process. Operate task $J_{i}$ requires the cooperation of certain equipments and spend some time executing process, according to its task table, and the finished garments will be send to the unloading station. Due to the concurrent process and resource competition while the system taking multitask productions, different execution sequence of the process will lead to different time to complete the n tasks. It is necessary to consider how to schedule the process to realize that the processing time minimized.

In this work, the Petri net model is completed by two steps. Firstly, establish a Petri net model for a single task. Then, get the TPPN model of the hanging system by connecting subnets via shared device resources. The operation of each process can be described as three stages, the initial, final and processing state. The initial and final state can be considered as two events represented by a set of transitions at the logic level, and the processing state can be considered as the operation state, which represented by a place with time delay. Here, a single task is taken as an example to establish a subsystem model which is shown below.

Given task $J_{i}$ with $X_{i}$ processes in a garment hanging system, the TPPN model for garment production of single task is described as $N_{J_{i}} = (P^{J_{i}}, T^{J_{i}}, F^{J_{i}}, W^{J_{i}}, M_{0}^{J_{i}}, D^{J_{i}})$ . In this model, the set of places can be expressed as $P^{J_{i}} = {p_{s}^{J_{i}}, P_{i, j, k}, P_{i, j, k}^{*}, p_{f}^{J_{i}}, P_{k}^{m}}$ , where places $p_{s}^{J_{i}}$ and $p_{f}^{J_{i}}$ are initial and final of the task $J_{i}$ respectively. Operation place $p_{i, j, k} \in P_{i, j, k}$ represents the operation that the process j of the task i by the k-th equipment. The intermediate place represents a buffer, and resource place $p_{i, j, k}^{*} \in P_{i, j, k}^{*}$ represents the required equipment. The set of transitions can be expressed as $T^{J_{i}} = {T_{i, j, k}^{b}, T_{i, j, k}^{f}}$ where $t_{i, j, k}^{b} \in T_{i, j, k}^{b}$ and $t_{i, j, k}^{f} \in T_{i, j, k}^{f}$ represent the initial and final events of the operation place $p_{i, j, k}$ respectively. The elements in the set of directed arc $F^{J_{i}}$ are directed lines between places and transitions, it represent the processing flow of the task. Since each task in garment processing is carried out in a single order, all of the elements in the weight function set $W^{J_{i}}$ are equal to one. The column vector $M_{0}^{J_{i}} = {(1, 0, ..., 0)}^{T}$ denotes that the number of tokens is one in $p_{s}^{J_{i}}$ and zero in other places at time zero of the system. The element $d_{i, j, k} \in D^{J_{i}}$ denotes the time delay of the operation place or the processing time of the operation in terms of garment hanging system. The intermediate and resource place are all places that time delay is zero.

Optimal scheduling policy

The Petri net model is applied to solve the problem of completing the task with the least time. The optimal scheduling algorithm is as follows.

Step 1: Set the priority for the tasks $J_{1}, J_{2}, ..., J_{n}$ which are expressed as $L_{1}, L_{2}, ..., L_{n}$ . There are $A_{n}^{n}$ arrangement methods to the number of n priorities. Therefore, n tasks possess the number of n! priority arrangements.

Step 2: Set no priority for tasks. Select any one as the start point from $J_{1}, J_{2}, ..., J_{n}$ respectively. There are a total of n different arrangement methods.

Step 3: Operate the n!+n implementation schemes successively.

Step 4: Search the enabled transitions. If the transition $t_{i, j, k}^{b}$ possesses the priority, implement Step4.1 to the model, else implement Step4.2.

Step 4.1: If multiple different tasks require the same resource place $p_{k}^{m}$ at the same time, the firing sequence of $t_{i, j, k}^{b}$ is ranked by the priority of the transitions. Record the enabled time ${d^{'}}_{i, j, k}$ and firing time ${d^{″}}_{i, j, k}$ for each transition, the waiting time of the transition $t_{i, j, k}^{b}$ is expressed as ${d^{'}}_{i, j} = {d^{″}}_{i, j, k} - {d^{'}}_{i, j, k}$ .

Step 4.2: If different tasks require the same resource place $p_{k}^{m}$ at the same time, the firing sequence of $t_{i, j, k}^{b}$ is ranked by the sequence of the enabled time ${d^{'}}_{i, j, k}$ . Record the value of ${d^{'}}_{i, j, k}$ and ${d^{″}}_{i, j, k}$ , then figures out the ${d^{'}}_{i, j}$ according to the time difference.

Step 5: Go to Step 4 until all the transitions have fired.

Step 6: The task completion time $d_{r} = \sum_{j = 1}^{X_{m}} (d_{i, j, k} + {d^{'}}_{i, j})$ where $r \in (1, n! + n)$ represents the r-th kind of implementation scheme, and $X_{m}$ is the number of the process of the task, which corresponds to the last firing transition.

Step 7: Go to Step 3 until n!+n kinds of implementation schemes are completed.

Step 8: The least time to complete n tasks is expressed as $d = \min (d_{1}, d_{2}, ..., d_{r}, ..., d_{n! + n})$ . According to the implementation scheme from d, get the sequence and time of the fired transitions in set $T^{J_{i}}$ .

In order to solve the problem of process scheduling, it is necessary to figure out the sequence and firing time of the start transition $t_{i, j, k}^{b}$ of each process. Map each transition to the event associated with the process in the system, and get the sequence and firing time of the process of n tasks from the mapping. Then the optimal scheduling policy is obtained. Figure 1 shows the flow chart of optimal process scheduling policy based on TPPN.

Figure 1 Flow chart of optimal scheduling policy of garment hanging system based on TPPN.

Results and discussion

Suppose that there are two processing tasks $J_{1}$ and $J_{2}$ for the garment hanging system. $J_{1}$ Contains 13 processes $J_{1, 1}, J_{1, 2}, ..., J_{1, 13}$ , $J_{2}$ contains 15 processes $J_{2, 1}, J_{2, 2}, ..., J_{2, 15}$ . A total of four equipments are needed,¹⁴ including ironing table, button sewing machine, cup seaming machine and lockstitch sewing machine which are represented as A, B, C and D, respectively. The specific implementation processes of two tasks are shown in Table 1. For the task $J_{1}$ in Table 1, the Petri net model of the task can be described as $N_{J_{1}} = (P^{J_{1}}, T^{J_{1}}, F^{J_{1}}, W^{J_{1}}, M_{0}^{J_{1}}, D^{J_{1}})$ . Transitions $t_{1, j, k}^{b}$ and $t_{i, j, k}^{f}$ represent the initial and final events respectively for each production stage $J_{1, 1}, J_{1, 2}, ..., J_{1, 13}$ , places $p_{s}^{J_{1}}$ and $p_{f}^{J_{1}}$ denote the initial and final state of $J_{1}$ , place $p_{i, j, k}$ represents the processing status of the production stages $J_{1, 1}, J_{1, 2}, ..., J_{1, 13}$ , and place $p_{i, j, k}^{*}$ is the subsequent buffer place of the $p_{i, j, k}$ (where j = 1, 2 ... 13, k=1, 2, 3, 4). The analogy can be used to reach the meaning of the places and transitions in the task $J_{2}$ (where j = 1, 2 ... 15, k = 1, 2, 3, 4). For the task $J_{2}$ in Table 1, the Petri net model of $J_{2}$ can be described as $N_{J_{2}}$ =( $P^{J_{2}}$ , $T^{J_{2}}$ , $F^{J_{2}}$ , $W^{J_{2}}$ , $M_{0}^{J_{2}}$ , $D^{J_{2}}$ ). The transitions $t_{2, j, k}^{b}$ and $t_{2, j, k}^{f}$ represent the initial and final events respectively for each production stage $J_{2, 1}, J_{2, 2}, ..., J_{2, 13}$ places $p_{s}^{J_{2}}$ and $p_{f}^{J_{2}}$ denote the initial and final state of $J_{2}$ , place $p_{2, j, k}$ represents the processing status of the production stages $J_{2, 1}, J_{2, 2}, ..., J_{2, 13}$ , and place $p_{2, j, k}^{*}$ is the subsequent buffer place of the $p_{2, j, k}$ . The Petri net model of $J_{1}$ is shown in Figure 2.

Figure 2 The Petri net model of production task $J_{1}$ .

In the same way, the Petri net model of $J_{2}$ can be obtained by the description of the task $J_{2}$ . Connect the subnet models of task $J_{1}$ and $J_{2}$ via shared resource places $p_{1}^{m}, p_{2}^{m}, p_{3}^{m}, p_{4}^{m}$ . The Petri net model of the garment hanging system of two tasks is shown in Figure 3. Set the value of n as 2 in the optimal process scheduling policy. There are four possible implementation schemes for the production. Run the programs of the optimal scheduling policy algorithm in MATLAB environment, the processing time and transitions firing sequence of each scheme can be obtained. Table 2 shows the completion time of the four schemes.

Table 2 shows the implementation scheme, which possesses no priority and $J_{1}$ start first should be selected. Firing time and sequence of all transitions at the condition of the shortest completion time are shown in Table 3.

In consideration of the correspondence between transitions $t_{i, j, k}^{b} (t_{i, j, k}^{f})$ and the initial (final) event of the production stages in garment hanging system, and the information in Table 3, the optimal process scheduling policy can be obtained from the schedules of production stages. The result is shown in Table 4.

In order to verify the practicability of the method, this paper selects the cases of garment production optimization from Tao¹⁵ and Liu¹⁶, and set multitask processing in Table 5.

Production Stage	Equipment	Time(S)	Production Stage	Equipment	Time(S)
$J_{1, 1}$	A	61	$J_{1, 8}$	D	30
$J_{1, 2}$	D	41	$J_{1, 9}$	A	33
$J_{1, 3}$	A	13	$J_{1, 10}$	D	105
$J_{1, 4}$	D	36	$J_{1, 11}$	A	47
$J_{1, 5}$	B	25	$J_{1, 12}$	D	94
$J_{1, 6}$	D	32	$J_{1, 13}$	C	127
$J_{1, 7}$	A	22
$J_{2, 1}$	A	61	$J_{2, 9}$	A	22
$J_{2, 2}$	C	24	$J_{2, 10}$	D	30
$J_{2, 3}$	A	13	$J_{2, 11}$	A	33
$J_{2, 4}$	D	36	$J_{2, 12}$	D	105
$J_{2, 5}$	A	10	$J_{2, 13}$	A	47
$J_{2, 6}$	C	7	$J_{2, 14}$	D	94
$J_{2, 7}$	B	25	$J_{2, 15}$	C	127
$J_{2, 8}$	D	32

Table 1 Task table of garment hanging system

Four Kinds of Implementation Schemes	Completion Time(S)
$J_{1}$ possesses the priority	1029
$J_{2}$ possesses the priority	1097
No priority, $J_{1}$ start first	902
No priority, $J_{2}$ start first	980

Table 2 The completion time of four schemes

Set the value of n as 2, 3, 4, 5, 6 respectively and input process, time and equipment data to the program, the completion time optimized by the algorithm are 902, 1638, 1167, 1543, 1268 seconds respectively. The comparison of consumed time before and after optimization is shown in Figure 4.

The contrast diagram shows that the algorithm presented in this paper is suitable for different styles and multitask process optimization in garment hanging system. Applying the optimal scheduling policy to the garment hanging system can distribute the processing time of each process reasonably, reduce the completion time and improve the efficiency of garment hanging system for small batch and multi variety production.

Figure 3 The Petri net model of two tasks.

Moment(S)	Transition	Moment(S)	Transition	Moment(S)	Transition
0	$t_{1, 1, 1}^{b}$	217	$t_{2, 5, 1}^{f}, t_{2, 6, 3}^{b}$	377	$t_{2, 11, 1}^{f}$
61	$t_{1, 1, 1}^{f}, t_{1, 2, 4}^{b}, t_{2, 1, 1}^{b}$	224	$t_{2, 6, 3}^{f}, t_{2, 7, 2}^{b}$	449	$t_{1, 10, 4}^{f}, t_{1, 11, 1}^{b}, t_{2, 12, 4}^{b}$
102	$t_{1, 2, 4}^{f}$	239	$t_{1, 6, 4}^{f}, t_{1, 7, 1}^{b}$	496	$t_{1, 11, 1}^{f}$
122	$t_{2, 1, 1}^{f}, t_{1, 3, 1}^{b}, t_{2, 2, 3}^{b}$	249	$t_{2, 7, 2}^{f}, t_{2, 8, 4}^{b}$	554	$t_{2, 12, 4}^{f}, t_{2, 13, 1}^{b}, t_{1, 12, 4}^{b}$
135	$t_{1, 3, 1}^{f}, t_{1, 4, 4}^{b}$	261	$t_{1, 7, 1}^{f}$	601	$t_{2, 13, 1}^{f}$
146	$t_{2, 2, 3}^{f}, t_{2, 3, 1}^{b}$	281	$t_{2, 8, 4}^{f}, t_{1, 8, 4}^{b}, t_{2, 9, 1}^{b}$	648	$t_{1, 12, 4}^{f}, t_{1, 13, 2}^{b}, t_{2, 14, 4}^{b}$
159	$t_{2, 3, 1}^{f}$	303	$t_{2, 9, 1}^{f}$	742	$t_{2, 14, 4}^{f}$
171	$t_{1, 4, 4}^{f}, t_{1, 5, 2}^{b}, t_{2, 4, 4}^{b}$	311	$t_{1, 8, 4}^{f}, t_{1, 9, 1}^{b}, t_{2, 10, 4}^{b}$	775	$t_{1, 13, 2}^{f}, t_{2, 15, 3}^{b}$
196	$t_{1, 5, 2}^{f}$	341	$t_{2, 10, 4}^{f}$	902	$t_{2, 15, 3}^{f}$
207	$t_{2, 4, 4}^{f}, t_{1, 6, 4}^{b}, t_{2, 5, 1}^{b}$	344	$t_{1, 9, 1}^{f}, t_{1, 10, 4}^{b}, t_{2, 11, 1}^{b}$

Table 3 Optimal transition sequence

Moment(S)	Production Stage	Moment(S)	Production Stage	Moment(S)	Production Stage
0	$J_{1, 1}$	207	$J_{1, 6}, J_{2, 5}$	311	$J_{1, 9}, J_{2, 10}$
61	$J_{1, 2}, J_{2, 1}$	217	$J_{2, 6}$	344	$J_{1, 10}, J_{2, 11}$
122	$J_{1, 3}, J_{2, 2}$	224	$J_{2, 7}$	449	$J_{1, 11}, J_{2, 12}$
135	$J_{1, 4}$	239	$J_{1, 7}$	554	$J_{2, 13}, J_{1, 12}$
146	$J_{2, 3}$	249	$J_{2, 8}$	648	$J_{1, 13}, J_{2, 14}$
171	$J_{1, 5}, J_{2, 4}$	281	$J_{1, 8}, J_{2, 9}$	775	$J_{2, 15}$

Table 4 Optimal scheduling policy of the process

Clothing Type	Task Quantity	Process Quantity	Equipment Quantity	Time Before Optimization(S)
Shirt	2	28	4	1332
Tailored suit	3	36	3	2934
Jeans	4	64	9	2108
Three-quarter trousers	5	75	3	5700
Polo shirt	6	48	4	2268

Table 5 Multitask processing related data of variety clothing

Figure 4 Time comparison of multiple tasks processing.

Conclusion

In this paper, the TPPN is applied to establish the model of the garment hanging system. According to the firing rules of transitions in Petri nets and the processing characteristics of the production line, propose the optimal scheduling algorithm for multitask processing. Simulation experiment shows that the optimal scheduling algorithm, achieves the purpose of high efficiency of garment hanging system in the mode of small batch and multi variety processing. In this study, only the process optimization of multitasks production is considered. Hence, optimizing the personnel allocation at all stages of production according to the operator proficiency in the garment processing will be the next research objective.

Acknowledgement

The scientific research program is funded by Shaanxi Provincial Education Department under Grant No.16JK1342 and Shaanxi Province under Grant No.2016-GY136, also supported by Xi’an Polytechnic University under Grant No.107090811.