TSP based approaches to flow shop scheduling problem

Headnote

Abstract: Flow shop scheduling problem (FSP) is a NP-hard problem, which is worthy analyzed in actual producing. We studied on a cigarette factory and abstracted the reality into FSPs. A discussion was conducted on producing techniques, production categories and producing environment so that the statement of the producing process was clear. Based on Traveling Salesman Problem (TSP), we formulated several models including time-constrained, asymmetric time changing, and multi-producing lines models. Finally, with the use of genetic algorithm, we analyzed the actual data, and the speed and results reacted well. It is verified that TSP-based modeling of FSP is feasible and efficient, and can reach the demand of production.

Keywords: flow shop scheduling problem, Traveling Salesman Problem, modeling Analysis, Genetic algorithm, cigarette production

(ProQuest: ... denotes formulae omitted.)

1.Introduction

In China, the annual taxation from the tobacco industry that occupies around 10% of the total taxation is of vital importance to national treasury. After the implementation of technological reforms during the 11th and 12th "five-year" plans, some indicators in the tobacco industry including production automation level, process ability, equipment performance and capacity have reached the advanced international level. Against the background of high levels of production automation, any delay in manufacturing will cause a great loss. This poses high demands to production organization. The promotion of make-to-order and market-oriented reform in this industry require much better production planning and scheduling (Guo et al., 2015). Traditional regular production planning and scheduling were formulated manually. Even control data in planning-related information systems were based on manual input. For a handful of vendors that attempted to optimize production scheduling, rule-based methods had their preference rather than optimization approaches. A few domestic corporations actually introduced the foreign advanced planning scheduling (APS) system, but rarely succeed in its application due to management complexity (Wu et al., 2013; Liao et al., 2013; Wang et al., 2010; Xie & E, 2007).

The cut tobacco processing line is the fundamental procedure in the entire tobacco production. The production process is relatively stable, as such batches of brand are processed in sequence along one or more continuous production lines. As the processing time vary with brand types, switch between different brands costs some time. Therefore, scheduling of cut tobacco processing is regarded as a typical FSP with limited lot sizes (Chris & Mikhail, 2000). FSPs, crucial in real life production, are widely involved in the production fields for fast moving consumer goods such as daily chemicals, food and pharmacy. Due to the NP-hard feature and the complexity of practical production, they are lack of accuracy. Consequently, FSP is difficult to tackle in real engineering practice (Garey et al., 1976; Gonzalez et al., 1978).

This paper mapped FSPs and all kinds of constraint mechanisms to travelling salesman problems (TSPs), through which a large volume of achievements concerning TSP model and its algorithm is obtained (Wang, 2012; Tapan et al., 2006). With the aim of solving practical FSPs, the paper first studied on real production scheduling issues with the tobacco manufacturing as an example. Then, a TSP-based model was established to satisfy requirements of different situations. Finally, with the use of genetic algorithm, the model was tested in real cases in each situation.

2.Production environment analysis

2.1.The whole production process

The whole production process, a classic hybrid production process, is characterized by multi-stage, multi-variable and strong coupling. It is a matter of great urgency to optimize tobacco production plans. Figure 1 is a diagram of a two-phase tobacco production process, which is divided into tobacco cutting (phase 1) and cigarette packing (phase 2). Phase 2 is the downstream output of finished products, playing a "pulling" role to phase 1. They are connected to each other through multiple parallel feeding processes (numbered in A, B, C, etc.) Generally, there is one or more production lines to cut tobacco, while a parallel unit is used for the packing phase. Therefore, to ensure continuous and in-time packing production, requirements are noticeably strict for tobacco cutting.

2.2.Sections and Subsections

Cut tobacco process is a non-stop production process accompanied by physical changes and chemical changes. It plays an important role in manufacturing high-quality cigarette. Figure 2 presents its production process. There are several production lines in the cut tobacco workshop, such as the main line of leaf tobacco and the subsidiary lines of stem tobacco process and expanded tobacco process. The main line is composed of five segments: leaf feeding, leaf processing, leaf cutting, blending and perfuming, and storage. At the blending and perfuming segments, stem tobacco and expanded tobacco are blended with each other according to the given proportion of finished cut tobacco; the mixture is perfumed then; and finally the end product is outputted for storage.

Corporations at different producing scales may build up one or more leaf tobacco lines, and each of them operates independently.

2.3.Product characteristics

In light of the demand for homogenized products, one type of product corresponds to one fixed proportion of raw materials that needs to be fed and processed strictly. The parallel unit production in phase two causes it hard for the batches with the same grade of cut tobacco to produce continuously. Switch between batches of the same grade costs the minimum time span, whilst switch between batches of different grades costs much time. In real producing practice, switch between batches of the same grade can be divided into two categories: high-to-low-end switch, which costs less time without regard of production line cleaning, and low-to-high-end switch, which costs the maximum time because the production line should be cleaned at each switch.

2.4.Scheduling requirements

First and foremost, tobacco cutting as an upstream process is expected to be scheduled in the way that satisfying the downstream requirements of non-stop feeding of materials. In addition, considering switch costs, a second significant matter is how to schedule feeding orders (Xia and Wei, 2009).

The cut tobacco processing resembles flow shop processing in that all inputs are manufactured along duplicate production lines. Once the feeding sequence is determined, all the production tasks in the main production line are accordingly acquired by calculation. Stem tobacco and expanded tobacco will be mixed in given proportion, and production schedule is controlled by the main line and organized according to semi-product storage.

3.Problem modeling

Based on the semiotic principle described by Graham, the production mode in tobacco processing workshops can be represented in the form of α\β\γ, where á or F^sub m^ indicates the number of production stages in the flow shop, ... is the quantity of machines at each of the production stages, k^sub i^ =1 in default of represents the objective of FSP optimization; if y = C^sub max^, then C^sub max^ is the optimal principle, i.e. the objective becomes minimum production time (Chris and Mikhail, 2000; Allahverdi et al., 2008).The problem for research in this paper is F^sub m^FS\C^sub max^, for which tasks are sequenced in a flow shop with m parallel production lines in order to minimize the completion time or to gain the most economical batch switch in another sense. Tobacco production FSPs can be modeled in the following several situations: disregard of time constraints, in consideration of time constraints, asymmetric time changing, and multi-producing lines. They will be expounded in section 3.1-3.4. All but section 3.4 are an analysis of a flow shop with a single production line, i.e. m = 1.

The entire production task is divided into n batches, whose completion and switches each have time cost. In this model, these batches are seen as n vertices in the image G. When batch i switches to batch j, an are from i to is constructed, and the unit cost for the switch is recorded as the unit distance cost ctjj ; for a production model with time requirements, the maximum delayed processing time for batch i is equal to the latest time allowed to reach the vertex i. Meanwhile, the time cost for batch i dtt is seen as the dwell time at the vertex i. Therefore, a weighed graph is drawn out as (G,ct) = ((Prod, link), ct), where the point set Prod = {1,2,-,n}, the line set link = {l^sub ij^ | i, j e Prod}, the cost set ct = {ct^sub ij^ | l^sub ij^ e link} ,the time-constraint set ProdT = {L^sub i^ | i e Prod}, and the dwell time set ProdD = {dt^sub i^ | i e Prod}. Supposing that the variable z^sub ij^ = i,i, j e Prod represents batch i to j switch, or the journey of a salesman from city i to j in G ; the variable z^sub ij^ = 0, i, j e Prod denotes that i does not switch to j, i.e. there is no journey from city i to j in G . In this way, FSPs is transformed into a solution for TSP in a weighted graph G .

3.1. A symmetric FSP model disregard of Batch Time Requirements

Under the circumstance that storage for finished cut tobacco is large enough or that the cut tobacco production lead time is abundant enough, time requirements for batches can be ignored. Meanwhile, assuming that switch time demanded for tobacco batches of different grades is the same, then the mere requirement for scheduling is that all vertices in the diagram G^sub 1^ = ((Prod, link), ct) are traversed. A variable u^sub i^ e {1,2,-,n-1}, i = 2,3,-,n is introduced in this model, representing the number of vertices to pass on the way to vertex i

Obj

...

s.t.

...

...

...

...

...

...

Variables:

ct^sub ij^ : Switch cost from i to j

Z^sub ij^ : A binary variable that decides whether to switch from i to j or not

U^sub i^ : The number of vertices to pass on the way to i

n : The number of vertices

LOTN : The total volume of batches

3.2. Asymmetric Flow Shop Scheduling Model Not Considering Batch Time Requirement

In practical production, the cost of switching from the high-end brand to the low-end brand is usually lower than that of switching from the low-end brand to high-end brand. Therefore, the switching time from batch i to batch j is equal to the switching time from batch j to batch i ( i * j ). That is to say, ctj = ctji, then G is symmetric graph; or else, G is asymmetric graph. That is to say, ctj ^ ctj{. The model expression of symmetric or asymmetric graph G is the same, but the solution to the problem is different.

3.3. Flow Shop Scheduling Model Considering Batch Time Requirement

To improve the intensive level, the lead time of cut tobacco production is only eight hours in many cases. Therefore, to guarantee the 24-hour production and the supply of materials in the phase two, specific time requirements are posed for the finishing of every cut tobacco batch. To solve the batch scheduling problem of the latest production time, set the actual production time of batch i as lotT{, namely the time needed to reach the vertex i is lotTi . The objective function is:

...

The first item ... represents the total time of all vertexes in the ergodic Prod . The second item ... represents the time constraint. If arriving at the city i at (or before) the latest arrival time, which is the lotT{ < L{, then fetch zero for the second item; or else, max [...] > o, and we will acquire a very large positive number multiplying by the large number M . When the objective function achieves best optimization, max[lotT^sub i^ -L^sub i^,o] = o, which ensures reaching the vertex i before the latest required time. Introduce variable y^sub i^ = max [lotT^sub i^ -L^sub i^,o to transform the objective function into linear function (Wu et al., 2011). Therefore, the following model can be built:

Obj

...

s.t.

...

...

...

...

...

...

...

...

Explanation of new variables:

lotri : Actual production time of batch i

L : The latest require production time of batch i

M : A big number

3.4.FI0W Shop Scheduling Model of Multiple Production Lines without Time Constraint

In the first two sections, we discuss the flow shop scheduling model of F^sub 1^|JS | C^sub max^ . For the flow shop scheduling problem in the form of F^sub m^|Js|C^sub k^, m ≠ 1, k = 1,2,-, m, which means there are m parallel assembly lines in the cut tobacco workshop, we have two modeling approaches. The first is to divide each batch into m equal divisions and then produce on each assembly line, which is to transform into the model discussed in section 3.1. the second is to add a fictitious starting point s and s can reach any vertex. Moreover, set ct^sub sj^ = 0, j e Prod and construct Multiple Travelling Salesmen Problem (m-TSP) on the graph G = ({s}u Prod,link). Divide graph G into m subgraphs (spanning trees), corresponding to the production sequence of m production lines and seek the optimal path to minimize the switching cost (Gornuejols et al., 1985).

m-TSP is to provide given travelling cost cuv among finite point set V , salesmans and each counter point u, v e V and find out m tours to minimize the access cost while ensuring every point in the V is visited by a salesman. Figure 3 gives the two examples of 2-TSP of five vertexes when adding a new source s . The access sequence shown in (a) is 2, 1 and 5, 4, 3 and the corresponding production sequence is that the production scheduling order is 2, 1 for assembly line 1 and the production scheduling order is 5, 4, 3 for assembly line 2. Similarly, the access sequence shown in (b) is 2,3,1 and 5,4, corresponding to the production scheduling order of 2, 3, 1 for assembly line 1 and the production scheduling order of 5, 4 for assembly line 2.

For every subgraph ..., k = 1,2,-,m, set the objective function ... and the y^sub i^ = max [lotT^sub i^ - L^sub i^ ,0}, i e Prod^sub k^ is time constraint. Then the objective function of TSP in graph G can be expressed as:

...

Then we can seek the earliest time needed to complete the process of each assembly line. Meanwhile, two constraints are added:

...

...

These two constraints represent dividing graph G into m disjoint subgraph and every production line is responsible for the production of a series of products.

The following model can be obtained:

...

s.t.

... (1)

... (2)

... (3)

... (4)

... (5)

... (6)

... (7)

... (8)

Explanation of new variables:

lotT:. Cost of each sub tour

Prodk : Subset of vertex set Prod , representing the product sets of the k production line

Constraint (1) indicates that all m travelling salesmen start from source s , and the manifestation in actual production is that m assembly lines start working at the same time. Constraint (2) and Constraint (3) indicates that every vertex is visited by certain travelling salesman only once. In actual production, if given batch starts production on certain i,i e Prod production line, it will not be produced by other production lines. Constraint (4) indicates that no sub tour exists in the result. The whole graph can be divided into m spanning trees, ensuring the maximum utilization of all m production lines and not to produce certain batch of products repeatedly. Constraint (5) indicates the value range of decision variable x;j. If x;j =1, then the production line producing the cut tobacco of brand i will switch to brand j; if Xj =0, then the production line producing the cut tobacco of brand i will not switch to brand j. Constraint (6) is time constraint. For flow shop scheduling problem without time constraint, constraint (6) can be deleted. For flow shop scheduling problem with time constraint, we need to produce certain quantity of products before given time. We can add the time constraint yi > lotT - Li, i e Prod and y^sub i^ > 0 and modify the objective function as ... Constraint (7) and constraint (8) guarantee that m sub tours are mutually disjoint and each vertex is strictly visited only once.

4.Solution Algorithm

The flow shop scheduling problems in this paper can all be transformed into TSP problems, and thus the intelligent optimization algorithms which can effectively solve TSP problems can be applied here, including simulated annealing algorithm, tabu search algorithm, ant colony algorithm, genetic algorithm and particle swarm optimization algorithm (Buthaninah & Hamza, 2008; Oliveira et al., 2014). This paper adopts the genetic algorithm to solve TSP problems based on MATLAB software platform, Windows10 operating system and PC environment.

Population initialization. Real number coding method is adopted, which is the random permutation of real number 1 to n. n is the batch number of cut tobacco and each batch appears once only. This process starts from a given brand batch and the subsequent batches needed to be produced are generated randomly. Considering the batches of cut tobacco every day in actual production environment do not exceed 30, which is the TSP problem of small scale. Therefore, the initialization parameter setting is that the number of population M=200, crossover probability Pc=0.9 and mutation probability Pm=0.05.

Fitness function. The objective function of TSP is to calculate the minimum value of the target and thus the fitness function can be directly selected as the objective function.

Stopping criterion. Because of the strong randomness of genetic algorithm, we set several stopping criteria: (1) if iteration is conducted for 500 times, then terminate the algorithm; (2) if the quotient of the average fitness of chromosome in certain generation of population and the current best chromosome fitness is larger than 0.9, then terminate the algorithm; (3) if the best chromosome is maintained for ten generations, then terminate the algorithm.

5.Analysis of Examples

There are two main lines in the workshop of certain enterprise and the production capability is 6000KG/H. there is one stem tobacco line but no expanded tobacco line. There are four brands of finished cut tobacco and these four brands are marked with A, B, C and D in the sequence from high-end to low-end. The feeding quantity of every batch of each brand is 6000Kg/batch. The switching time matrix of each brand is shown in Table 1 (I represents symmetry constraint, II represents asymmetrical constraint).

Take the data from 0 o'clock to 24 o'clock on March 9th, 2015. The feeding quantity of each brand and the latest feeding time are shown in Table 2.

According to the need of model solution, the TSP problems containing 9 pieces of finished cut tobacco batches are built and the solution can be acquired without considering time constraint (Table 3)

Analysis: each brand is produced in a continuous manner, conforming to the requirement of minimum switching cost.

After considering the time constraint and the processing time on the first segment of each brand (residence time 60 minutes), the following optimization results can be obtained (lead time of cut tobacco production is 480 minutes) (Table 4).

Analysis: under the condition of satisfying time constraint, each brand is produced in a continuous manner and switching cost is the lowest.

Considering two main lines of leaf tobacco (line 1 and line 2), the following optimization results are obtained when the lead time is 240 minutes (Table 5).

Analysis: under the condition of satisfying time constraint, each brand is produced in equilibrium state. Moreover, each brand is produced in a continuous manner and the switching cost is the lowest.

6.Conclusion

The flow shop scheduling problem is a sort of key problems that have wide application prospect in production operations. In order to conduct research on the flow shop scheduling problem taking advantage of the maturity models and solution methods in TSP, this paper takes the cut tobacco production as the research object and maps several kinds of typical scenes in the flow shop scheduling to travelling salesmen problem. The feasibility of this method is verified through the example verification of small scale. The subsequent researches should concentrate on two aspects: the first is the research on the algorithm with mutual adaptation and rapid convergence for model of multiple scenes; the second is the model analysis under the condition of emergency replenishment or special requirements of the technics in the production process. Under this condition, the scale of the problem is enlarging, present multidimensional characteristics.

Acknowledgment

Thank all participants in Beihang University. Their support is gratefully acknowledged. This research is partially supported by Chinese National Foundation of Natural Science (No.71172016; No. 71332003).

References

References

Allahverdi A., Ng C.T., Cheng T.C.E., Kovalyov M.Y. (2008). A survey of scheduling problems with setup times or costs [J]. European Journal of Operational Research, 187, 985-1032.

Bagchi T., Gupta J., Sriskandarajah C. (2006). A review of TSP based approaches for flowshop scheduling [J]. European Journal of Operational Research, 169, 816-854.

Buthainah F.A., Hamza A.A. (2008). Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA) [C]. World Academy of Science, Engineering and Technology, 38.

Chris N.P., Mikhail Y.K. (2000). Scheduling with batching: a review [J]. European Journal of Operational Research, 120. 228-249.

Cornuejols G., Naddef D., Pulleyblank W. (1985). The Traveling Salesman Problem in Graphs with 3-Edge Cutsets [J]. Journal of the Association for Computing Machinery, 32(2), 383-410.

Garey M.R., Johnson D.S., Sethi R. (1976). The Complexity of Flowshop and Jobshop Scheduling [J]. Mathematics of Operations Research, 1(1), 117-129.

Gonzalez T., Sahni S. 1978. Flowshop and Jobshop Schedules: Complexity and Approximation [J]. Operations Research, 26(26), 36-52.

GUO X.K., LI J., GUO J., ZHANG H. (2015). Research on the policy of market-oriented cigarette marketing reform [J], Acta Tabacaria Sinica, 21(4): 94-98.

LIAO C.H., LUO W.C., LU Z.K. (2013). Research and Application of Batch Management Pattern of Flexible Tobacco Primary Processing Line [J]. Tobacco Science Technology, 7: 30-33.

Oliveira J. A., Ferreira J., Figueiredo M., Dias L., & Pereira G. (2014). Sistema de Apoio à Decisao para o Transporte Nao Urgente de Doentes em Veículo Partilhado [J]. RISTI - Revista Ibérica de Sistemas e Tecnologias de Informaçdo, 13, pp. 17-33. Doi: 10.4304/risti.13.17-33.

Wang A.M., Ding L., Ning R.X., Li J.S. (2010). Tobacco packaging Job-Shop dynamic scheduling technology [J]. Computer integrated manufacturing system, 16(3):603-610,627.

Wang H. (2012). Comparison of several intelligent algorithms for solving TSP problem in industrial engineering [J]. System Engineering Procedia, 4, 226-235.

WU S.L., LIU M., WEI J., OUYANG Q. (2012). On the application of planning and scheduling in cigarette production [J]. Technological development of enterprise, 31(19): 17-20.

Wu Y.F., Li H.L., Wang D.W. (2011). Research on the Optimization Problem of Production Process Based on Time Constraint [J], Operations Research Management Science, 20(6), 205-209.

Xie W.F., E M.C. (2007). The research of the sub system of the package schedule based on the SIEMENS platform [J]. China Manufacturing Information, 1, 6-9.

Xia X.F., Wei P. (2009). Production process modeling and schedule simulation for the tobacco strips product line [J]. Machinery Design &Manufacture, 41(5), 231-232.