Minimizing Makespan in A Two-Machine Flowshop Problem with Processing Time Linearly Dependent on Job Waiting Time

Abstract

This paper is aimed at studying a two-machine flowshop scheduling where the processing times are linearly dependent on the waiting times of the jobs prior to processing on the second machine. That is, when a job is processed completely on the first machine, a certain delay time is required before its processing on the second machine. If we would like to reduce the actual waiting time, the processing time of the job on the second machine increases. The objective is to minimize the makespan. When the processing time is reduced, it implies that the consumption of energy is reduced. It is beneficial to environmental sustainability. We show that the proposed problem is NP-hard in the strong sense. A 0-1 mixed integer programming and a heuristic algorithm with computational experiment are proposed. Some cases solved in polynomial time are also provided.

1. Introduction

In this paper, we consider a two-machine flowshop scheduling problem where the processing times are linearly dependent on the waiting times of the jobs prior to processing on the second machine. The objective is to minimize the makespan. In this problem, when a job is processed completely on the first machine, a certain delay time is required before its processing on the second machine. If we can find a way to reduce the certain delay time at the cost of extra processing time added to the processing time of the job on the second machine, the whole processing time of all jobs may be reduced. When the whole processing time is reduced, the consumption of energy is reduced. This contributes to environmental sustainability. In addition, the managerial implication of this approach is that a production scheduler has more leeway to arrange a job sequence to reach the goal. One realistic example of this kind of scheduling exists in a painting process. Generally, there are at least two layer-painting stages in a painting engineering. After the first stage, the product has to wait for some time until it is dry naturally. Then, the product goes to the second stage. If we want to reduce the waiting time, we can use a dryer to accelerate the drying process. This implies that the cost of extra processing time is added to the processing time of the job on the second machine. Another practical scheduling problem arises at the cooking–chilling stage in a food plant [1]. The chilling process must start within 30 min of the completion of cooking. Otherwise, the food has to be discarded as unfit for human consumption. If there is an advantage in terms of the makespan minimization, we can reduce the waiting time after the completion of cooking at the cost of an extra processing time of the chilling process. In such a situation, it is good for the sustainability of the earth because it involves less food waste. Also, the objective of the makespan is minimized. The processing time of all jobs is reduced. The consumption of the energy is reduced. It is beneficial for environmental sustainability. For some other scheduling problems related to sustainability, the reader is referred to the works of [2,3,4,5,6,7,8].

The two-machine, minimum makespan, flowshop scheduling problem was first solved by Johnson [9]. Mitten [10] extended this problem with time lags. Sule and Huang [11] permitted the setup and removal times to be independent of the processing time. Maggu et al. [12] considered the problem with time lags and transportation time between machines. These problems proposed above are solved by a polynomial time algorithm, which is similar to Johnson’s rule [9]. There are also many studies considering scheduling problems with sequence dependent setup time. For example, Ruiz [13] proposed an iterated greedy heuristic to solve the flowshop scheduling problem with sequence dependent setup time. Nishi and Hiranaka [14] applied the Lagrangian relaxation and cut generation method to minimize the total weighted tardiness in flowshop scheduling problems with sequence dependent setup time. Wang et al. [15] presented a hybrid local search algorithm to solve the sequence setup times flowshop scheduling problem with a makespan criterion.

For the two-machine flowshop scheduling problem with waiting time constraints (or intermediate delays), Reddi and Ramamoorthy [16] proposed a polynomial time algorithm for the problem with no-wait in process. Dell’Amico [17] showed that the two-machine flowshop scheduling problem with intermediate delays is NP-hard in the strong sense if the solution space is not restricted to permutation schedules. In addition, Yu et al. [18] showed that the two-machine flowshop machine problem with intermediate delays is NP-hard in the strong sense, even if all processing times are 1. Fiszmann and Mosheiov [19] studied the scheduling problem of minimizing total load on a proportionate flowshop. They considered position-dependent job processing times in the most general way. They showed that this problem is solved in O($n^4$) time, where n is the number of jobs. Yang and Chern [20] considered a two-machine flowshop sequencing problem with limited waiting time constraints; they showed that the permutation scheduling problem is NP-hard and proposed a branch-and-bound algorithm. Su [21] extended the problem studied by Yang and Chern [20] and considered a two-stage flowshop with a batch processor in stage 1 and a single processor in stage 2. Each batch processor can process a batch (limited number) of jobs simultaneously. A heuristic algorithm and a mixed integer program are proposed. Sriskandarajah and Goyal [22] considered a problem in which the processing times are linearly dependent on the waiting times; they showed that the problem is NP-hard and proposed a heuristic algorithm. Yang and Chern [23] further extended the problem studied by Sriskandarajah and Goyal [22] and considered a problem in which the processing time of a job on the second machine is linearly dependent on the waiting time if the waiting time is beyond a certain range. They proposed an integer program and a heuristic algorithm to solve the problem.

Chung et al. [24] considered a two-stage hybrid flowshop scheduling problem with a waiting time constraint. They provided two algorithms to solve the makespan minimization problem. Wang et al. [25] investigated a permutation flowshop scheduling problem with a time lag between two consecutive machines. They presented a two-stage constructive heuristic to minimize the makespan.

The proposed problem is different from those studied by Sriskandarajah and Goyal [22] and Yang and Chern [23]. In the problem of Sriskandarajah and Goyal [22], when a job is processed completely on the first machine, the job can be processed immediately on the second machine. No delay time is required. If there is a delay time before a job to be processed on the second machine, the processing time of the job on the second machine increases. In the problem of Yang and Chern [23], when a job is processed completely on the first machine, there is a waiting time before its processing on the second machine. If the waiting time is beyond a certain range, the processing time of a job on the second machine increases. This problem is similar to the following problem. When a job is processed completely on the first machine, a certain delay time (i.e., a certain waiting time) is required before its processing on the second machine. However, the actual waiting time can be either decreased or increased. The cost of the actual waiting time change is the increase of the processing time of a job on the second machine. In the proposed problem, we only consider the case in which the actual waiting time is allowed to be decreased at the cost of extra processing time added to the processing time of a job on the second machine.

The organization of the remainder of this paper is as follows. In Section 2, there is a description of the problem and its complexity. A 0-1 mixed integer programming formulation is given in Section 3 and the heuristic algorithm is presented in Section 4. Thereafter, computational experiments are reported in Section 5. Finally, in Section 6, we give the conclusions.

2. Problem Description and Complexity

The proposed two-machine makespan flowshop scheduling problem denoted T with processing time linearly dependent on job waiting time is described as follows.

First, some notations are introduced in the following and additional notations will be given when needed throughout the paper.

• J_i: the ith job in the original sequence, i = 1, 2, 3,…, n
• J_[i]: the ith job in the actual sequence, i = 1, 2, 3,…, n
• M₁: the first machine on the flowshop
• M₂: the second machine on the flowshop
• a_i: the regular processing time of J_i on the first machine M₁
• b_i: the regular processing time of J_i on the second machine M₂
• d_i: the delay time of J_i before its processing on machine M₂
• w_i: the actual waiting time of J_i before its processing on machine M₂
• α_i: the cost index, α_i > 0
• C_i,1: the completion time of J_i on machine M₁
• C_i,2: the completion time of J_i on machine M₂

For a given set of jobs J = {J₁, J₂, …, J_n}, let a_i and b_i be the regular processing times of job J_i on the first machine M₁ and the second machine M₂, respectively. We assume that for each job J_i, when J_i is processed completely on machine M₁, a delay time d_i is required before its processing on machine M₂. However, in some situations, the actual waiting time w_i is allowed to be smaller than the delay time d_i at the cost of extra processing time added to the processing time b_i of job J_i on M₂. That is, if the actual waiting time w_i of J_i is smaller than d_i, then the processing time of J_i on machine M₂ is given by b_i + α_i(d_i − w_i), where α_i > 0. However, if w_i ≥ d_i, then the processing time on machine M₂ is b_i. The objective is to find the optimal schedule minimizing the makespan.

First, in the proposed problem, if ${\alpha }_i>1$, there is no benefit to reduce the actual time w_i, and then the proposed problem is reduced to the problem studied in Yu et al. [18]. Hence, if ${\alpha }_i>1$, the proposed problem is also NP-hard in the strong sense. Next, we will show that the partition problem [26] reduces to the proposed problem if $0<{\alpha }_i=\alpha \le 1$, i = 1, …, n. Consider the following well-known NP-complete problem:

Partition: Given positive integers s₁, s₂, …, s_k, does there exist a subset

$$E\subseteq N=\{1,\dots ,k\} \mathrm{such} \mathrm{that}{\displaystyle \sum _{i\in E}{s}_i}={\displaystyle \sum _{i\in N-E}{s}_i}=({\displaystyle \sum _{i\in N}{s}_i})/2?$$

For a given instance of partition, s₁, s₂, …, s_k, an instance of the proposed problem is constructed as follows:

n = k + 2;               
a_i = 2Ss_i, b_i = s_i, d_i = 0 for i ∈ N = {1, …, k};
a_k+1 = 1, b_k+1 = 2 + 2S², d_k+1 = 0;    
a_k+2 = 2, b_k+2 = 2S² − S, d_k+2 = 2S² + S;  
α_i = α for i∈{1, 2, …, k + 2},      

where ${\displaystyle \sum _{i\in N}{s}_i}$ = 2S.

We will show that Partition has a solution if and only if the above instance has an optimal schedule with the minimum makespan C_max = 4S² + S + 3.

Lemma 1.

For the above instance, it is sufficient to consider the schedules that have the same job processing sequence on both machines for the job J_i, i ∈ {1, …, k + 1}.

Proof. 

If a schedule Π does not have the same job processing sequence on both machines for the job J_i, i∈{1, …, k + 1}, then there are two cases:

(1)

There is a job J_i, which directly precedes J_j on machine M₁ and follows J_j on machine M₂, i, j ∈ {1, …, k + 1}, perhaps with intervening jobs (Figure 1a). We may interchange the order of J_i and J_j on machine M₁ without increasing the makespan, because d_i = d_j = 0.

(2)

There is a sequence (A₁, J_i, J_k+2, J_j, A₂) on machine M₁, where A₁ and A₂ are subsequences, and J_i follows J_j on machine M₂, perhaps with intervening jobs (Figure 1b). We may interchange the processing order of J_i and J_j in (A₁, J_i, J_k+2, J_j, A₂) as the following sequence (A₁, J_k+2, J_j, J_i, A₂) on machine M₁ without increasing the makespan (Figure 1c), because d_i = d_j = 0.

This process of interchanging jobs may be repeated until a schedule Π’ is obtained with the same order on machine M₁ as that on machine M₂ for the job J_i, i ∈ {1, …, k + 1}. Π’ is clearly not worse than Π. Therefore, Lemma 1 holds. □

Lemma 2.

If J_k+1 is not processed first, then the makespan of any schedule is greater than 4S² + S + 3.

Proof. 

For any given schedule, if J_i (i ∈ N) is processed first, then

$$\begin{array}{ll}{C}_{\mathit{max}}& \ge a_i+{\displaystyle \sum _{i\in N}{b}_i}+b_{k+1}+b_{k+2}\\ & =2S_{\mathit{Si}}+2S+2+2S^2+2S^2-S\\ & >4S^2+S+3.\end{array}$$

Similarly, if J_k+2 is processed first, then

$$\begin{array}{ll}{C}_{\mathit{max}}& \ge a_{k+2}+{\displaystyle \sum _{i\in N}{b}_i}+b_{k+1}+b_{k+2}\\ & =2+2S+2+2S^2+2S^2-S\\ & >4S^2+S+3.\end{array}$$

Thus, we only consider the schedules whose J_k+1 is processed first on both machines. □

Lemma 3.

If J_k+2 is not processed second on machine M₁, then the makespan of any schedule is greater than 4S² + S + 3.

Proof. 

Let U = {i|J_i is processed between J_k+1 and J_k+2 on machine M₁}. If there are jobs J_i, i∈U, then the following two cases are considered:

(1)

If any job J_i, i∈N, does not create any idle-time slot on machine M₂, that is, the processing of these jobs on machine M₂ is continuous, then there are two subcases:

(i)

If 2S² + 2S − 2S${\displaystyle \sum _{i\in U}{s}_j}\ge 0$ (Figure 2),

then

$$\begin{array}{ll}{C}_{\mathit{max}}& \ge a_1+b_{k+1}+{\displaystyle \sum _{i\in N}{b}_i}+l+b_{k+2}+\mathsf{\alpha }\mathit{max}\{0,d_{k+2}-w_{k+2}\},\\ & =1+2+2S^2+2S+l+2S^2-S+\mathsf{\alpha }\mathit{max}\{0,2S^2+S-2S^2-2S+2S{\displaystyle \sum _{i\in U}{s}_j}-l\}\\ & =4S^2+S+3+l+\mathsf{\alpha }\mathit{max}\{0,(2{\displaystyle \sum _{i\in U}{s}_j}-1)S-l\}>4S^2+S+3,\end{array}$$

where w_k+2 = b_k+1 + ${\displaystyle \sum _{i\in N}{b}_i}$ + l − ${\displaystyle \sum _{i\in U}{a}_j}$ − a_k+2 = 2S² + 2S − 2S${\displaystyle \sum _{i\in U}{s}_j}$ + l and l ≥ 0.

(ii)

If 2S²+ 2S − 2S${\displaystyle \sum _{i\in U}{s}_j}$ < 0, then J_k+2 creates an idle-time slot l_k+2 = 2S${\displaystyle \sum _{i\in U}{s}_j}$ − 2S² − 2S > 0 on machine M₂. From Lemma 2, if J_k+1 is scheduled first and there is no idle time on machine M₂, except during operation 1 of J_k+1, there is a lower bound of the C_max, which is 4S² + S + 3_. In this case, J_k+2 creates an idle-time slot l_k+2 > 0; therefore, C_max > 4S² + S + 3.

(2)

Similarly, if a job J_r, r∈N, creates an idle-time slot l_r > 0, then C_max > 4S² + S + 3.

Thus, we only consider the schedules whose J_k+2 is processed second on machine M₁. □

Theorem 1.

For any given positive number α > 0, α_i = α, i = 1, …, n, the two-machine makespan flowshop scheduling problem T is NP-hard.

Proof. 

If partition has a solution, then there is an optimal schedule with the makespan C_max = 4S² + S + 3 (Figure 3a). We note that, in this case, the waiting time w_i ≥ d_i for each i.

If partition has no solution, we will show that the makespan of any schedule for the above instance is greater than 4S² + S + 3. For given schedule in which J_k+1 is processed first on two machines and J_k+2 is processed second on machine M₁, we let E = {i|J_i is processed between J_k+1 and J_k+2 on machine M₂}. By the assumption that partition has no solution and ${\displaystyle \sum _{i\in E}{s}_i}$ − S = c ≠ 0, we consider the following two cases:

(1)

If c < 0 and l > 0 (Figure 3b), we have

$$\begin{array}{ll}{C}_{\mathit{max}}& \ge a_{k+1}+b_{k+1}+{\displaystyle \sum _{i\in E}{b}_i}+l+b_{k+2}+\mathsf{\alpha }\mathit{max}\{0,d_{k+2}-w_{k+2}\}+{\displaystyle \sum _{i\in N-E}{b}_i}\\ & =1+2+2S^2+2S+l+2S^2-S+\mathsf{\alpha }\mathit{max}\{0,d_{k+2}-w_{k+2}\}\\ & =4S^2+S+3+l+\mathsf{\alpha }\mathit{max}\{0,2S^2+S-(2S^2+{\displaystyle \sum _{i\in E}{s}_i}+l)\}\\ & =4S^2+S+3+l+\mathsf{\alpha }\mathit{max}\{0,-c-l\}>4S^2+S+3,\end{array}$$

where w_k+2 = b_k+1 + ${\displaystyle \sum _{i\in E}{b}_i}$ + l − a_k+2 = 2S² + ${\displaystyle \sum _{i\in E}{s}_i}$ + l.

(2)

If c > 0 (c ≥ 1/2, because s₁, s₂, …, s_k are positive integers), without loss of generality, we let J_j, j ∈ E, be the last processed job in E (Figure 3c), then there are two cases:

(i)

If any job J_i, i ∈ E-{j}, does not create any idle-time slot, then we will show that job J_j creates an idle-time slot l_j > 0 on machine M₂ (Figure 3c). The idle-time slot is

$$\begin{array}{ll}{l}_j& =\mathit{max}\{0,a_{k+2}+{\displaystyle \sum _{i\in E}{a}_i}-b_{k+1}-{\displaystyle \sum _{i\in E-\{j\}}{b}_i}\}\\ & =\mathit{max}\{0,2+2S{\displaystyle \sum _{i\in E}{s}_i}-2-2S^2-{\displaystyle \sum _{i\in E}{s}_i}+s_j\}\\ & =\mathit{max}\{0,2S(S+c)-2S^2-S-c+s_j\}\\ & =\mathit{max}\{0,2Sc-S-c+s_j\}=\mathit{max}\{0,2(S-1/2)(c-1/2)-1/2+s_j\}\\ & =2(S-1/2)(c-1/2)-1/2+s_j>0, \mathrm{since} S\ge 1, c\ge 1/2 \mathrm{and} s_j\ge 1.\end{array}$$

Hence, C_max > 4S² + S + 3.

(ii)

If a job J_r, r ∈ E-{j}, creates an idle-time slot l_r > 0, then C_max > 4S² + S + 3.

Thus, the makespan is greater than 4S² + S + 3 if partition has no solution. It follows that partition has a solution if and only if the optimal schedule of the above instance has the minimum makespan C_max = 4S² + S + 3. □

3. A 0-1 Mixed Integer Programming Formulation

According to the similar analysis in Yang and Chern [23], a 0-1 mixed integer programming of the problem is developed as follows. First, we denote that

• A_i = the starting time of job i on machine M₁;
• B_i = the starting time of job i on machine M₂;
• w_i = the actual waiting time of job i before its processing on machine M₂ = B_i − A_i − a_i;
• W_i = max{d_i − w_i, 0}= max{d_i − B_i + A_i + a_i, 0};
• y_ijk = 1, if job i precedes job j on machine M_k;
• y_ijk = 0, otherwise;
• C_max = the makespan.

For each job i, it is clear to have

B_i ≥ A_i + a_i, 1 ≤ i ≤ n.

(1)

In addition, it is necessary to assure that no two operations can be processed simultaneously by the same machine. Suppose, for example, that job j precedes job i on machine 1, then it is necessary to have

A_i ≥ A_j + a_j.

On the other hand, if job i precedes job j on machine 1, then it is necessary to have

A_j ≥ A_i + a_i.

These inequalities are called disjunctive constraints, because one and only one of these inequalities must hold. In order to accommodate these constraints in the formulation, these disjunctive constraints can be rewritten as follows:

A_i + My_ij1 ≥ A_j + a_j, 1 ≤ i < j ≤ n,

(2)

A_j + M(1 − y_ij1) ≥ A_i + a_i, 1 ≤ i < j ≤ n,

(3)

where M represents a sufficiently large positive number.

By the same way, these disjunctive constraints of job i and job j processed on machine 2 can be expressed as follows:

B_i + My_ij2 ≥ B_j + b_j + α_jW_j, 1 ≤ i < j ≤ n,

(4)

B_j + M(1 − y_ij2) ≥ B_i + b_i + α_iW_i, 1 ≤ i < j ≤ n.

(5)

We note that

W_i = max {d_i − B_i + A_i + a_i, 0},

then it is necessary to have W_i ≥ 0 and

W_i ≥ d_i − B_i + A_i + a_i, 1 ≤ i ≤ n.

(6)

For the makespan problem, it is necessary to have

C_max ≥ B_i + b_i + α_iW_i, 1 ≤ i ≤ n.

(7)

Then, a disjunctive integer programming formulation of the proposed problem can be given by

minimize	Cmax
subject to	Cmax ≥ Bi + bi + αiWi	1 ≤ i ≤ n,
	Bi ≥ Ai+ ai	1 ≤ i ≤ n,
	Ai + Myij1 ≥ Aj + aj	1 ≤ i < j ≤ n,
	Aj + M(1 − yij1) ≥ Ai + ai	1 ≤ i < j ≤ n,
	Bi + Myij2 ≥ Bj + bj + αjWj	1 ≤ i < j ≤ n,
	Bj + M(1 − yij2) ≥ Bi + bi + αiWi	1 ≤ i < j ≤ n,
	Wi ≥ di − Bi + Ai + ai	1 ≤ i ≤ n,
	Cmax, Ai, Bi, Wi ≥ 0, 1 ≤ i ≤ n, yijk = 0 or 1,	1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 2.

The total number of type (1), (6), and (7) constraints is equal to 3n. The total number of type (2) and (3) constraints is equal to n(n − 1). The total number of type (4) and (5) constraints is equal to n(n − 1). Hence, the total number of constraints is n(2n + 1). There are 3n + 1 nonnegative variables of C_max, A_i, B_i, and W_i. We note that if y_ijk is in the formulation, then y_jik needs to be defined. Hence, there are n(n − 1)/2 0 − 1 integer variables of y_ij1 and the same number of y_ij2. The total number of variables is thus n(n + 2) + 1.

4. Heuristic Algorithm and Its Worst-Case Performance

As a reducible waiting time is considered in the proposed problem, somehow, the proposed problem is similar to the two-machine flowshop scheduling problem with start and stop lags. Therefore, we first use the Maggu and Das’s algorithm [27] to determine a sequence A (Algorithm 1).

Algorithm 1. Maggu and Das’s algorithm

Step 1. Let J = {J1, J2, …, Jn}. Step 2. Determine the job processing order in the following way:   2.1 Decompose set J into the following two sets: U = {Ji│ai ≤ bi} and V = {Ji│ai > bi}.   2.2. Arrange the members of set U in nondecreasing order of ai + di, and arrange the members of set V in nonincreasing order of bi + di.   2.3. A sequence A is the ordered set U followed by the ordered set V.

Some solvable cases are described in the following.

First, if $\underset{1\le i\le n}{\mathit{min}}${α_i}≥1, the proposed problem is the same as that in Dell’Amico [17]. Therefore, if $\underset{1\le i\le n}{\mathit{max}}${d_i} ≤ $\underset{1\le i\le n}{\mathit{min}}${b_i + d_i} or $\underset{1\le i\le n}{\mathit{max}}${d_i} ≤ $\underset{1\le i\le n}{\mathit{min}}${a_i + d_i}, an optimal schedule is given by Maggu and Das’s Algorithm.

Theorem 2

([23]). In the problem, the case considered here is with $\underset{1\le i\le n}{\mathit{max}}${α_i}≤1, $\underset{1\le i\le n}{\mathit{max}}${a_i + d_i} ≤ $\underset{1\le i\le n}{\mathit{min}}${b_i + d_i}, and a_i* +α_i*d_i* = $\underset{1\le i\le n}{\mathit{min}}${a_i +α_id_i}. If there is a job J_j, such that a_j + d_j ≤ b_i* +α_i*d_i*, then (J_i*, J_j, B) is an optimal schedule, where B is an arbitrary subsequence of the jobs without J_i*, J_j.

Proof. 

Please see the proof in Appendix A. □

Theorem 3

([23]). If $\underset{1\le i\le n}{\mathit{max}}${α_i} ≤ 1, $\underset{1\le i\le n}{\mathit{min}}${a_i} ≥ $\underset{1\le i\le n}{\mathit{max}}${b_i + α_id_i} and b_i* + α_i*d_i* = $\underset{1\le i\le n}{\mathit{min}}${b_i + α_id_i}, then (B, J_i*) is an optimal schedule, where B is an arbitrary subsequence of the jobs without J_i*, and we schedule the jobs with no-wait manner as shown in Figure 4.

Proof .

It is clear that a lower bound on the makespan is ${\displaystyle \sum _{i=1}^n{a}_i}$ + $\underset{1\le i\le n}{\mathit{min}}${b_i + α_id_i}. If $\underset{1\le i\le n}{\mathit{max}}${α_i} ≤ 1, $\underset{1\le i\le n}{\mathit{min}}${a_i} ≥ $\underset{1\le i\le n}{\mathit{max}}${b_i + α_id_i}, then the makespan of (B, J_i*) with no-wait manner, as shown in Figure 4, is equal to the lower bound ${\displaystyle \sum _{i=1}^n{a}_i}$+ b_i* + α_i*d_i*. Hence, (B, J_i*) is an optimal schedule. □

In the following, we propose a heuristic algorithm for the problem. The heuristic algorithm is presented for the problem with a_i ≥ 0, b_i ≥ 0, α_i > 0, and d_i > 0 for all of the jobs. In this problem, if α_i ≥ 1, then it is useless to reduce the waiting time. However, if 0 < α_i < 1, then it is useful to reduce the waiting time as much as possible. A stepwise description of the algorithm is given as follows (Algorithm 2):

Algorithm 2. Heuristic algorithm

Step 0. (Initialization) Check those conditions stated in Theorem 2 and Theorem 3. If any one of conditions holds, the optimal schedule is obtained. Otherwise, generate a heuristic solution in the following steps. Determine a sequence π by using Maggu and Das’s algorithm. Set k = 1 and C[0],1 = C[0],2 = 0. Step 1. (Determining the reduced period of waiting time and the additional time on machine M2 for each job) Set C[k],1 = C[k−1],1 + a[k]. If C[k−1],2 − C[k−1],1 < a[k] (Figure 5a), then go to Step 1.1. If a[k] ≤ C[k−1],2 − C[k−1],1 ≤ a[k] + d[k] (Figure 5b), then go to Step 1.2. If a[k] + d[k] < C[k−1],2 − C[k−1],1 (Figure 5c), then go to Step 1.3. 1.1 If 0 < α[k] < 1, then C[k],2= C[k],1 + b[k] + α[k] ⋅ d[k]. If 1 ≤ α[k], then C [k],2 = C[k],1 + d[k] + b[k]. Go to Step 2. 1.2 If 0 < α[k] < 1, then C [k],2 = C [k−1],2 + b[k] + α[k] ⋅( C[k],1 + d[k] − C [k−1],2). If 1 ≤ α[k], then C [k],2 = C[k],1 + d[k] + b[k]. Go to Step 2. 1.3 C[k],2 = C [k−1],2 + b[k]. Go to Step 2. Step 2. Set k = k + 1 If k ≤ n, go to Step 1. Otherwise, stop.

In the heuristic algorithm, Step 0 first determines a sequence A by using Maggu and Das’s algorithm. Step 1 adjusts the reduced period of waiting time and the additional time on machine 2 for each job. In Step 1.1 and Step 1.2, if α_[k] ≥ 1, then it is useless to reduce the waiting time. However, if 1 > α_[k] > 0, then it is useful to reduce the waiting time as much as possible and the calculation of the completion times on both machines is given. Step 1.3 depicts that if a_[k],1 + d_[k] < C _[k−1],2 − C _[k−1],1, then it is useless to reduce the waiting time either α_[k] ≥ 1 or 1 > α_[k] > 0.

In the following, an example of five jobs is given to illustrate the heuristic algorithm.

Example 1.

There are five jobs; that is, J₁, J₂, J₃, J₄, and J₅, to be processed on machine M₁ and machine M₂. The processing times of these jobs on machine M₁ are a₁ = 1, a₂ = 3, a₃ = 2, a₄ = 3, and a₅ = 2, respectively. The processing times on machine M₂ are b₁ = 5, b₂ = 4, b₃ = 1, b₄ = 2, and b₅ = 3, respectively. The delay times required before its processing on machine M₂ are d₁ = 2, d₂ = 3, d₃ = 1, d₄ = 2, and d₅ = 5, respectively. The cost indices are α₁ = 0.2, α₂ = 0.3, α₃ = 0.1, α₄ = 0.5, and α₅ = 1.2, respectively.

According to the above heuristic algorithm, we obtain that the makespan of these five jobs is 16.6. Please see the details in Appendix B.

Lower bound

First, we assume that processing on each machine may be continuous, D₁ = {i?α_i ≥ 1 for iN} and D₂ = N–D₁. We can see that, if α_i ≥ 1, then it is useless to reduce the waiting time. However, if 1 > α_i > 0, then it is useful to reduce the waiting time as much as possible. Because all the jobs have to be processed on machine M₁ and M₂, if the delay time is short relative to the corresponding processing time, we have an immediate lower bound LB1 = max {${\displaystyle \sum _{i=1}^n{a}_i}$ + min {$\underset{i\in D_1}{\mathit{min}}${d_i + b_i}, $\underset{i\in D_2}{\mathit{min}}${α_id_i + b_i}}, min {$\underset{i\in D_1}{\mathit{min}}${a_i + d_i}, $\underset{i\in D_2}{\mathit{min}}${a_i + α_id_i}}+${\displaystyle \sum _{i=1}^n{b}_i}$}. On the other hand, if one of the delay times is long enough relative to the corresponding processing time, we have the second lower bound LB2 = max {$\underset{i\in D_1}{max}${a_i + d_i + b_i}, $\underset{i\in D_2}{max}${a_i + α_id_i + b_i}}. Hence, a lower bound is calculated as follows:

$$\begin{gathered} C_{low}=\mathit{max}\{{\displaystyle \sum _{i=1}^n{a}_i}+\mathit{min}\{\underset{i\in D_1}{\mathit{min}}\{d+b_i\},\underset{i\in D_2}{\mathit{min}}\{{\mathsf{\alpha }}_i{d_i}_{}+b_i\}\}, \\ \mathit{min}\{\underset{i\in D_1}{\mathit{min}}\{a+{d_i}_{}\},\underset{i\in D_2}{\mathit{min}}\{a+{\mathsf{\alpha }}_i{d}_i\}\}+{\displaystyle \sum _{i=1}^n{b}_i}, \\ \underset{i\in D_1}{max}\{i_{}+d+b_i\},\underset{i\in D_2}{max}\{i_{}+{\mathsf{\alpha }}_i{d_i}_{}+b_i\}\}. \end{gathered}$$

In the following, we will find the worst case of the heuristic algorithm. First, some notations are defined. Given a solution of the proposed problem, we define the critical job $J_{[c]}$ as the job with maximum starting time on machine M₂, such that $C_{[c],1}+w_{[c]}=B_{[c]}$, where $0\le w_{[c]}\le d_{[c]}$ and $C_{[c],1}$, $d_{[c]}$, $w_{[c]}$, and $B_{[c]}$ are the completion time of $J_{[c]}$ on machine M₁, the delay time of $J_{[c]}$, the actual waiting time of $J_{[c]}$, and the starting time of $J_{[c]}$ on machine M₂, respectively. We also define JP as the set of jobs proceeding $J_{[c]}$ on machine M₁, and JF as the set of jobs following $J_{[c]}$ on machine M₂. Then, considering the schedule in which the jobs are arranged by Maggu and Das’s algorithm, there are three cases of the makespan, as follows.

Case 1.

$0<{\alpha }_{[c]}<1$ and $C_{[c],1}\ge C_{[c-1],2}$ (See Figure 6a)

$$C_{\mathit{max}}(\pi )={\displaystyle \sum _{i\in JP}{a}_i}+a_{[c]}+{\alpha }_{[c]}{d}_{[c]}+b_{[c]}+{\displaystyle \sum _{i\in JF}{b}_i}$$

Case 2.

$0<{\alpha }_{[c]}<1$ and $C_{[c],1}<C_{[c-1],2}$ (See Figure 6b)

$$\begin{gathered} C_{\mathit{max}}(\pi )={\displaystyle \sum _{i\in JP}{a}_i}+a_{[c]}+w_{[c]}+{\alpha }_{[c]}{l}_{[c]}+b_{[c]}+{\displaystyle \sum _{i\in JF}{b}_i} \\ ={\displaystyle \sum _{i\in JP}{a}_i}+a_{[c]}+d_{[c]}-(1-{\alpha }_{[c]})l_{[c]}+b_{[c]}+{\displaystyle \sum _{i\in JF}{b}_i},where{l}_{[c]}=d_{[c]}-w_{[c]} \end{gathered}$$

Case 3.

${\alpha }_{[c]}\ge 1$ (See Figure 6c)

$$C_{\mathit{max}}(\pi )={\displaystyle \sum _{i\in JP}{a}_i}+a_{[c]}+d_{[c]}+b_{[c]}+{\displaystyle \sum _{i\in JF}{b}_i}$$

Theorem 4.

Let π* be an optimal schedule and π be the Maggu and Das’s schedule for the heuristic algorithm. If$0<{\alpha }_{[c]}<1$and$C_{[c],1}\ge C_{[c-1],2}$, then$\rho =C_{\mathit{max}}(\pi )/C_{\mathit{max}}(\pi *)\le 2$and the bound is tight.

Proof. 

Considering the schedule in which the jobs are arranged by Maggu and Das’s algorithm, if $0<{\alpha }_{[c]}<1$ and $C_{[c],1}\ge C_{[c-1],2}$, then the makespan is as follows:

$$C_{\mathit{max}}(\pi )={\displaystyle \sum _{i\in JP}{a}_i}+a_{[c]}+{\alpha }_{[c]}{d}_{[c]}+b_{[c]}+{\displaystyle \sum _{i\in JF}{b}_i}$$

Therefore, if $a_{[c]}\le b_{[c]}$, the jobs $J_i$ $\in$ JP have the property of $a_i\le b_i$. Then, we have the following results:

$$\begin{gathered} C_{\mathit{max}}(\pi )\le ({\alpha }_{[c]}{d}_{[c]}+b_{[c]})+{\displaystyle \sum _{i=1}^n{b}_i}\le \underset{i\in D_2}{max}\{a+{\mathsf{\alpha }}_i{d_i}_{}+b_i\}+\{\underset{i\in D_1}{\mathit{min}}\{a+{d_i}_{}\}, \\ \underset{i\in D_2}{\mathit{min}}\{a+{\mathsf{\alpha }}_i{d}_i\}\}+{\displaystyle \sum _{i=1}^n{b}_i}\le LB1+LB2\le 2C_{low}. \end{gathered}$$

Similarly, if $a_{[c]}>b_{[c]}$, the jobs $J_i$ $\in$ JF have the property of $a_i>b_i$. Thus,

$$\begin{gathered} C_{\mathit{max}}(\pi )\le (a_{[c]}+{\alpha }_{[c]}{d}_{[c]})+{\displaystyle \sum _{i=1}^n{a}_i}\le \underset{i\in D_2}{max}\{a+{\mathsf{\alpha }}_i{d_i}_{}+b_i\}+{\displaystyle \sum _{i=1}^n{a}_i}+\mathit{min}\{\underset{i\in D_1}{\mathit{min}}\{d_i \\ +b_i\},\underset{i\in D_2}{\mathit{min}}\{{\mathsf{\alpha }}_i{d_i}_{}+b_i\}\}\le LB2+LB1\le 2C_{low}. \end{gathered}$$

Hence, $\rho =C_{\mathit{max}}(\pi )/C_{\mathit{max}}(\pi *)\le C_{\mathit{max}}(\pi )/C_{low}\le 2$.

To prove the tightness of the bound, consider $J_1$ with $a_1=1$, $b_1=1$, $d_1=n$, and $0<{\alpha }_1<1$, and $J_i$ ($i=2,3,\dots ,n$) with $a_i=1$, $b_i=1$, $d_i=0$, and ${\alpha }_i=0.5$. By applying Maggu and Das’s algorithm, the job sequence is $J_2,J_3,\dots ,J_n,J_1$ on both machine M₁ and M₂. Then, $C_{\mathit{max}}(\pi )=n+{\alpha }_{1}n+1=(1+{\alpha }_1)n+1<2n+1$.

On the other hand, an optimal schedule can be obtained by arranging the job sequence $J_1,J_2,J_3,\dots ,J_n$ on machine M₁ and the job sequence $J_2,J_3,\dots ,J_n,J_1$ on machine M₂. Then, $C_{\mathit{max}}(\pi *)=n+2$. Hence, $\rho =C_{\mathit{max}}(\pi )/C_{\mathit{max}}(\pi *)=(2n+1)/(n+2)$, which tends to 2 as n → ∞. □

Theorem 5.

Let π* be an optimal schedule and π be the Maggu and Das’s schedule for the heuristic algorithm. If${\alpha }_{[c]}\ge 1$, then$\rho =C_{\mathit{max}}(\pi )/C_{\mathit{max}}(\pi *)\le 2$and the bound is tight.

Proof. 

The proof is the similar to that of Theorem 4. Thus, we omit it here. □

5. Computational Experiments

Although we find the worst case of the heuristic algorithm under some certain situations (case 1 and case 3), the upper bound of case 2 is still unknown. Therefore, in order to evaluate the overall efficiency of the heuristic algorithm, we generate several groups of random problems as follows:

(1)

n is equal to 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200.

(2)

a_i is uniformly distributed over [1,100].

(3)

b_i is uniformly distributed over [1,100].

(4)

α_i is uniformly distributed over [1,2].

(5)

d_i is uniformly distributed over [0,50], [50,100], or [100,200] depending on the group.

In the computational experiment, a total of 720 test problems are generated. The computation times of algorithms for all the test problems are within one second. For each of these random problems, the percentage of the error e = (C_h − C_low) ∗ 100/C_low is computed, where C_h is the makespan of the heuristic solution and C_low is the lower bound on the makespan.

The result is given in

Table 1. Computational results for Algorithm 1.

n	di	Observed in 20 Test Problems
		Minimum Percentage Error (%)	Average Percentage Error (%)	Maximum Percentage Error (%)
10	[0,50]	0	3.8172	10.6325
	[50,100]	0	5.9864	11.8965
	[100,200]	0	8.1236	19.3263
20	[0,50]	0	2.7115	5.3269
	[50,100]	0	2.9658	10.1268
	[100,200]	1.2547	5.1579	9.8852
30	[0,50]	0	1.2363	3.9986
	[50,100]	0	2.6636	6.2355
	[100,200]	3.6278	5.6986	12.3023
40	[0,50]	0.1321	2.1506	5.3330
	[50,100]	0.1036	1.5367	3.7795
	[100,200]	1.2233	3.9968	7.4862
50	[0,50]	0	0.9865	1.2296
	[50,100]	0.1007	1.2233	3.0125
	[100,200]	1.0023	3.0559	6.7756
60	[0,50]	0.0553	1.0021	2.9140
	[50,100]	0.3054	0.9953	1.2235
	[100,200]	0.9562	2.0013	3.9240
70	[0,50]	0.0345	1.0782	2.6835
	[50,100]	0.1602	0.9866	2.2012
	[100,200]	0.6058	2.6158	3.9671
80	[0,50]	0	0.2212	1.2369
	[50,100]	0.2365	0.9968	2.0123
	[100,200]	0.5523	1.2633	2.1825
90	[0,50]	0.0327	0.3223	1.0023
	[50,100]	0.2305	0.6696	1.2354
	[100,200]	0.6813	2.0362	3.7182
100	[0,50]	0.0173	0.1211	1.2310
	[50,100]	0.0235	0.9071	2.3261
	[100,200]	0.2103	1.5981	3.6682
150	[0,50]	0	0.4355	0.8908
	[50,100]	0.0636	0.3693	1.0032
	[100,200]	0.1015	1.1036	1.9936
200	[0,50]	0	0.1036	0.3679
	[50,100]	0.3012	0.4250	0.5587
	[100,200]	0.2963	0.3972	0.8572

. There are 20 test problems for each problem type. To evaluate the overall performance of the heuristic algorithm, we compute the mean of all the average percentage errors reported in Table 1. The mean value is 1.97%, which suggests that the heuristic algorithm, on average, finds schedules that are within 1.97% of optimality. From Theorem 4 and 5, we can see that the upper bound of the heuristic algorithm is $2\ast C_{low}$; therefore, the performance of the heuristic algorithm is quite satisfactory. From Figure 7, the larger the value of d_i, the greater the percentage of the error. Because the proposed heuristic algorithm is restricted to searching a near-optimal permutation schedule, it may imply that the optimal schedule is likely to be a non-permutation schedule when the values of delay times of jobs are larger. Therefore, the performance of the heuristic algorithm is better when d_i is smaller. We can also see that the average percentage of errors decreases as the job number n increases for different values of d_i. Especially, when the job number n is more than 100, the mean value of the average percentage of errors is less than 1%. In view of the NP-hardness of the problem, this result is quite encouraging as it provides efficient procedures for solving large-sized problems.

6. Conclusions

In this paper, we investigate a two-machine flowshop scheduling problem in which the processing times of the second operations are linearly dependent on the waiting times of the jobs. This problem is shown to be NP-hard. A 0-1 integer programming and an efficient heuristic algorithm with computational experiment are also proposed. In addition, the worst case of the heuristic algorithm under some situations is provided. From the computational experiments, the overall performance of the proposed algorithm is quite satisfactory, especially when the job number is large. Some cases solved in polynomial time are also provided.

There are some limitations in this study. For example, the proposed heuristic algorithm only searches a near-optimal permutation schedule. In the future research, to develop a heuristic algorithm to find both permutation and non-permutation schedules may improve this scheduling performance (makespan). In addition, another performance measure, such as total tardiness or maximum lateness, may be considered for the proposed problem. Actually, in real situations, the cost of the reduction of the waiting time may be non-linear or the compression of the waiting time may be limited. Therefore, future research may focus on these issues, too.