# Optimal Results and Numerical Simulations for Flow Shop Scheduling Problems

Authors: Tao Ren; Yuandong Diao; Xiaochuan Luo
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

This paper considers them-machine flow shop problem with two objectives: makespan with release dates and total quadratic completion time, respectively. For Fm|rj|Cmax, we prove the asymptotic optimality for any dense scheduling when the problem scale is large enough. For Fm∥ΣCj2, improvement strategy with local search is presented to promote the performance of the classical SPT heuristic. At the end of the paper, simulations show the effectiveness of the improvement strategy.


---

## Body

## 1. Introduction

Industrial production is one of the most essential parts for the economic development with regard to its important value to economy and society in a country. Meanwhile, control and optimization are playing a vital role in promoting the productivity for industrial production. Whereas, the classical optimal methods are invalid and large-size computation is necessary because of the especial characteristic of discrete variables in industrial control and optimization problems. While the appearance of advanced algorithms and methods support for conquering these problems.In this paper, two industrial optimization problems, flow shop scheduling problem to minimize makespan with release dates and the sum of quadratic completion times, are considered. In a flow shop model, there are a number of machines, and all jobs have to be processed on these machines following the constant route. A comprehensive overview about flow shop problem can be found in [1]. With the standard scheduling notation of Graham et al. [2], the flow shop scheduling problem to minimize makespan with release dates and the sum of quadratic completion times can be described by Fm|rj|Cmax and Fm||ΣCj2, respectively, where m is the number of machines.ForFm|rj|Cmax, only a few researches can be found among the references. In 1977, Lenstra et al. [3] proved that F2|rj|Cmax is strongly NP hard. The polynomial algorithm will be impossible to reach the optimal solution, if the class P of problems is not equal to the class NP. Therefore, heuristics may be effective for large size problems to obtain an approximation solution. Some polynomial time approximation algorithms are investigated by Potts [4] for two-machine case. And the best algorithm among them has a worst case ratio of 5/3. Specially, Hall [5] presented a PATS (polynomial time approximation scheme) which is the strongest result known for the general problem.Likewise, forFm||ΣCj2, there are only few researchers that consider this quadratic objective, which may optimize the makespan and the total completion time together [6]. In 2005, Koulamas and Kyparisis [7] reported that Fm||ΣCj2 is strongly NP hard which implies that its optimal solution cannot be obtained in polynomial time. Therefore, they utilized the shortest processing time (SPT) heuristic to deal with large size problems and proved the asymptotic optimality and the worst case for the heuristic, respectively. Although the objective value of SPT heuristic equals the optimal solution as the number of jobs large enough, for some special case, the gap between them is the square of the number of machines.For convenience of research, it is supposed that the jobs have bounded random (interval) processing times in flow shop problems typically. With the bounded uncertain processing times, [8] presented some dominant schedules for two-machine flow shop problem to minimize makespan and [9] obtained the necessary and sufficient conditions in a minimal set of dominant schedules for flow shop minimum-length scheduling problem with two machines. Under the hypothesis that the jobs have bounded independently and identically distributed (i.i.d.) processing times, [10] provided two lower bounds for m-machine flow shop problems, and [11] designed two heuristics for m-machine flow shop problems to minimize makespan.In our work, we first study dense schedule for the flow shop makespan problem with release dates. Dense schedule was dealt with open shop makespan problem by Bárány and Fiala [12] first. In a dense schedule, any machine is idle if and only if there is no job that can be processed at that time on that machine. For problem Fm||Cmax, Chen and Yu [13] proved that the worst case performance ratio of any dense schedule is m, and the bound is tight. We show that any dense permutation schedule is asymptotically optimal for Fm|rj|Cmax as the number of jobs trends to infinity. Next, for Fm||ΣCj2, we try to present an improvement strategy based on local search to promote the performance of classical heuristic algorithm SPT. At the end of the paper, simulations show the effectiveness of the improvement strategy.The remainder of the paper is organized as follows. The problem is formulated in Section2, and the asymptotic optimality of dense schedule for Fm|rj|Cmax is in Section 3. In Sections 4 and 5, the improvement strategy and numerical simulations for Fm||ΣCj2 are given, respectively. And in Section 6, this paper is closed by the conclusions.


## 2. Problem Statement and Preliminaries

In a flow shop problem a set ofn jobs has to be sequentially processed on m different machines. Each job j, j=1,2,…,n, passes through the m machines in that order and requires processing time p(i,j) on machine i, i=1,2,…,m, and a release date rj. The processing times are i.i.d. bounded random variables. It is not permitted to process any job before its release date. At any given time each machine can handle at most one job and each job can be processed on at most one machine. Preemption is forbidden, that is, any commenced operation has to be completed without interruptions. And each machine processes the jobs in a first come first served manner. Here we consider the permutation schedule, that is, all jobs are processed on all machines in the same order. Also, the jobs can wait between two successive machines and the intermediate storage is unlimited. The completion time of job j, j=1,2,…,n, on machine i, i=1,2,…,m, is denoted by C(i,j). First, for Fm|rj|Cmax, let the makespan, the maximal completion time of the job on the final machine, of a dense schedule S be Cmax(S). And Assume the optimal makespan be Cmax(S*), where S* denotes the optimal schedule. Next, for Fm||ΣCj2, the objective value of an algorithm H is denoted by ZH, and the optimal solution is denoted by Z*. The objective is to find a sequence of jobs, with the given processing times on each machine, to minimize the total quadratic completion times on the final machine, that is, min∑j=1nC2(m,j).


## 3. Performance Analysis for Dense Schedule

To evaluate the performance of a heuristic algorithm, a classical way is to analyze its worst case performance ratio. But in an industrial scheduling environment, it is usual that thousands of jobs would be processed on one or more machines. As the appearance of worst case performance ratio is special for some small size problem, it is more suitable to introduce asymptotical performance ratio to describe the effect of a heuristic in practice when the problem size is large enough. In this section, the asymptotic optimality of dense schedule is shown by series of deductions.AsFm|rj|Cmax is strongly NP hard, the usual way to estimate the optimal makespan is to calculate its lower bound. The classical lower bound (LB1), valid for this problem, is the bound equal to the maximum of machine loads on the first machine. The value of LB1 is(3.1)CLB1=max⁡1≤j′≤n⁡{rj′+∑k=j′np(k,1)}.With the above preparation, it is easy to obtain the following theorem.Theorem 3.1.
Let the processing timesp(i,j), j=1,2,…,n, i=1,2,…,m, be independent random variables having the same continuous distribution with bounded density ϕ(·). For every j, j=1,2,…,n, with probability one, one has that
(3.2)lim⁡n→∞Cmax⁡(S)n=lim⁡n→∞Cmax⁡(S*)n.Proof.
For a dense schedule and its associated LB1, we have(3.3)Cmax⁡(S)-CLB1=max⁡1≤j≤l1≤⋯≤lm≤n{rj+∑k=jl1p(k,1)+∑k=l1l2p(k,2)+⋯+∑k=lmnp(k,m)}-max⁡1≤j′≤n{rj′+∑k=j′np(k,1)}≤max⁡1≤j≤l1≤⋯≤lm≤n{rj+∑k=jl1p(k,1)+∑k=l1l2p(k,2)+⋯+∑k=lmnp(k,m)-rj-∑k=jnp(k,1)}≤max⁡1≤j≤l1≤⋯≤lm-1≤n{(∑k=jl1p(k,1)+⋯+∑k=lm-1np(k,m))-∑k=jnp(k,1)}.
The second inequality of (3.3) holds because of the following reasons. For a given schedule, it is obvious there is no extra idle time on the first machine except waiting for the arrivals. Therefore, in LB1 the release date rj′ is the last one to generate the idle on that machine, and we have rj+p(j,1)+⋯+p(j′-1,1)≤rj′.
For the last inequality of (3.3), the following cases are considered.
Case 1 (|n-j|~O(m)).
Letn-j=αm, where α is a constant and limn→∞α/n=0. Noting n-l1=(α+1)m-1, therefore, we have
(3.4)lim⁡n→∞1nmax⁡1≤j≤l1≤⋯≤lm-1≤n{(∑k=jl1p(k,1)+⋯+∑k=lm-1np(k,m))-∑k=jnp(k,1)}=lim⁡n→∞1nmax⁡1≤l1≤⋯≤lm-1≤n{∑k=jl1p(k,1)+⋯+∑k=lm-1np(k,m)}-lim⁡n→∞1nmax⁡1≤j≤n{∑k=jnp(k,1)}≤lim⁡n→∞(α+1)m-1npmax⁡-lim⁡n→∞αmnpmin⁡=0,
where pmax and pmin denote the maximum and the minimum processing time among all the processing times, respectively.Case 2 (|n-j|~O(n)).
Letn-j=βn, where 0<β<1 is a constant and limn→∞β/n=0. Noting n-l1=βn+m-1, therefore, we have
(3.5)lim⁡n→∞1nmax⁡1≤j≤l1≤⋯≤lm-1≤n{(∑k=jl1p(k,1)+⋯+∑k=lm-1np(k,m))-∑k=jnp(k,1)}≤lim⁡n→∞1nmax⁡1≤l1≤⋯≤lm-1≤n{∑k=jl1-1p(k,1)+∑k=l1l2-1p(k,2)⋯+∑k=lm-1n-1p(k,m)}+lim⁡n→∞m-1npmax⁡-lim⁡n→∞1nmax⁡1≤j≤n{∑k=jnp(k,1)}=lim⁡n→∞βE(p)-lim⁡n→∞βE(p)+lim⁡n→∞m-1npmax⁡=0,
where E(p) is the expected processing time of all the n jobs. The last equality of (3.5) holds because that all processing times are i.i.d. random variables and satisfy the law of large numbers when the number of jobs trends to infinity.
With inequalities (3.4) and (3.5), and noting that(3.6)Cmax⁡(S)-Cmax⁡(S*)≤Cmax⁡(S)-CLB1,
we have
(3.7)0≤lim⁡n→∞Cmax⁡(S)-Cmax⁡(S*)n≤lim⁡n→∞Cmax⁡(S)-CLB1n=0.
Rearranging inequality (3.7), we can get the result of the theorem.The above Theorem means that any dense permutation schedule forFm|rj|Cmax approaches the optimal schedule when the scale of the problem is large enough.


## 4. Improvement Strategy for SPT Heuristic

In this section, the performance of classical SPT heuristic is modified by a local search scheme in which each job in the seed sequence is sequentially inserted in each possible different position of a generated sequence. However, as the asymptotic optimality of SPT sequence, the insertion movement of a job for objective descent may not be too far from its initial position, otherwise, it will enlarge the objective function value. Therefore, the searching and comparing for a seed sequence from front to back in the scheme will cost much redundant computation time. To save calculation time and produce high-quality solutions, two selected jobs are shifted from their current position, both ends of an initial sequence, and inserted in a different position forward and backward one by one, respectively. To guarantee the asymptotic optimality of the final solution, the initial sequence is generated by SPT heuristic. If the objective value is not improved after several insertions, we terminate the searching process for this seed sequence and then, choose the best sequence out of those sequences as the new seed sequence for the next two jobs to be inserted. Repeat the process of search, until all the jobs are tested.Let [x: (s)] denote the two jobs found in the xth and n-x+1th position of sequence π(s), and [y: (s′)] denote the two jobs found in the yth and n-y+1th position of sequence π(s′). A formal description of the improvement strategy can be presented as follows.Improvement Strategy for SPT Heuristic
Step 1.
Generate the initial sequenceπ(s) with SPT heuristic.Step 2.
Setx=1 and π(s)=π(s′).Step 3.
Sety=1.Step 4.
If [x: (s)] ≠ [y: (s′)], then generate a sequence π(y), which differs from π(s′) only by inserting two jobs [x: (s)] to the yth and n-y+1th position, and compute the quadratic completion time C(y) of sequence π(y); otherwise, set y′=y.Step 5.
Sety:=y+1. Return to Step 4 if y≤n; otherwise, go to Step 6.Step 6.
Determine the sequenceπ(j) such that C(j)=min{C(y)∣y=1,2,…,n, and y′≠y}. If C(j)<C(s′), set π(s′)=π(j).Step 7.
Setx:=x+1. return to Step 3 if x≤n; otherwise, go to Step 8.Step 8.
π(s′) is the final sequence. Stop.To see the practical effectiveness of the improvement strategy, numerical simulations are conducted in the next section.


## 5. Computational Results

In this section, we designed a series of computational experiments to reveal the performances of the improvement strategy in different size problems. First, we compare the effectiveness of the improvement strategy with that of SPT heuristic; then, we report the ratios of the improvement strategy to the lower bound ofFm||ΣCj2, LB2 (given by Koulamas and Kyparisis [7]):(5.1)LB2=1m2∑j=1n(∑k=1j∑i=1mp(k,i))2,
to show its performance variation when parameters vary. The ratios showed in Table 1 are the objective values of improvement strategy to that of SPT heuristic and its associated LB2 values, respectively. Three, five, and ten machines, and 100, 200, 500, and 1000 jobs are tested, respectively. The processing times were randomly generated from a discrete uniform distribution on [1, 10]. Five different random tests for each combination of the parameters mentioned above were performed, respectively, and the averages are shown in Table 1, where IS denote the improvement strategy.Table 1
The experiment results.
MachinesIS/LB2IS/SPT35103510100 jobs1.39561.52892.11350.90510.91210.9275200 jobs1.19491.32351.57700.92050.93820.9564500 jobs1.16101.25711.32240.94210.96560.97921000 jobs1.09411.16091.21860.97950.98310.9850From the data showed in Table1, we can see that the ratios of IS/LB2 approach one as the number of jobs increases from 100 to 1000 with the fixed number of machines. For example, with five machines, the ratio of IS/LB2 drops from 1.5289 to 1.1609 when the number of jobs increases from 100 to 1000 (see Figure 1). This phenomenon indicates the asymptotic optimality of the improvement strategy. Contrarily, for the fixed number of jobs, ratios of IS/LB2 enlarges as the number of machines increases from 3 to 10. The cause may be that the larger the number of machines is the larger the quantity of idle times is, which enlarges the gap between the value of objective and its lower bound.Figure 1
Ratios of IS/LB2 withm=5.From Table1, we also find that the objective values of SPT heuristic and improvement strategy tend to be equal when the number of jobs is larger enough. An example can be see in Figure 2, with three machines, the ratio of IS/SPT enlarges from 0.9051 to 0.9795 when the number of jobs increases from 100 to 1000. A reasonable explanation is that the idle times between two adjacent jobs can be ignored and the associated objectives become nondifferentiated when the problem scale tends to infinity.Figure 2
Ratios of IS/SPT withm=3.


## 6. Conclusions

In this paper, we first showed that any dense permutation schedule is equal to the optimal schedule as the problem size tends to infinity for flow shop makespan problem with release dates. And then, an improvement strategy based on local search is presented to boost the performance of SPT heuristic for flow shop total quadratic completion time problem. Computational results show that the improvement strategy works well with the moderate scale problems.



---

*Source: 395947-2012-03-11.xml*