# A Scheduling Problem to Minimize Total Weighted Tardiness in the Two-Stage Assembly Flowshop

Authors: Ik Sun Lee
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This paper considers an assembly scheduling problem which minimizes the total weighted tardiness. The system consists of multiple manufacturing machines in the first stage and an assembly machine in the second stage. A job is composed of multiple components, each component is manufactured on a dedicated machine in the first stage, and the assembly starts on the assembly machine after the completion of all the components’ manufacturing in the first stage. This paper is to try to find effective and efficient schedules to minimize the total weighted tardiness of jobs. This paper analyzes some solution properties to improve search effectiveness and efficiency. Moreover, some lower-bound procedures are derived, and then four constructive heuristics and a branch-and-bound algorithm are suggested. The performances of the derived algorithms are evaluated through numerical experiments. For the problems with no more than 15 jobs, the branch-and-bound algorithm finds the optimal solutions within 20 minutes, and the performance of the four heuristics seems to be similar. However, for problems with more than 30 jobs, HWT shows the best performance among the four heuristics except for two machines.


---

## Body

## 1. Introduction

This study considers a two-stage assembly production system, which manufactures components in the first stage and then assembles all the components in the second stage. The assembly can begin after all the components belonging to the product are completed. In the system, two stages are physically located in a series as the components’ production stage and the assembly stage, but the components are produced on the manufacturing machines in parallel.Framinan et al. [1] and Pan et al. [2] conducted a review paper on the assembly scheduling problem. From the review papers, there are two types of research depending on whether dedicated machines or flexible machines are used for manufacturing components in the first stage. First, the dedicated machine environment represents that each component is processed on a designated machine. Second, the flexible machine environment means that each machine can process all types of components.This paper considers the first situation with dedicated machines in the first stage. Lee et al. [3] introduced a two-stage assembly scheduling problem with two dedicated manufacturing machines in the first stage and one assembly machine in the second stage. For the makespan minimization, Lee et al. [3] proved that the associated problem is NP-complete, proposed three heuristics based on Johnson's rule, and derived their error bounds. Potts et al. [4] conducted an extension of Lee et al. [3] by considering m machines in the first stage and proposed some heuristics using Johnson's rule. Hariri and Potts [5] proposed an effective branch-and-bound algorithm to find optimal solutions. Sun et al. [6] proposed 14 heuristics for the problem of Potts et al. [4]. Tozkapan et al. [7] and Lee [8] considered the total weighted completion minimization in a two-stage assembly scheduling problem and suggested a branch-and-bound algorithm. Framinan and Perez-Gonzalez [9] proposed a metaheuristic algorithm for the total completion minimization in a two-stage assembly scheduling problem. Talens et al. [10] addressed the two-stage multimachine assembly scheduling problem under a situation with several dedicated parallel machines in the first stage and identical parallel machines in the second stage. They proposed two heuristic algorithms for the total completion time minimization.Allahverdi and Al-Anzi [11] considered the maximum lateness objective in the two-stage assembly scheduling problem and derived a metaheuristic based on particle swarm optimization and tabu search. Allahverdi and Aydilek [12], Ha et al. [13], and Lee and Bang [14] considered the two-stage assembly scheduling problem to minimize the total tardiness with two dedicated machines in the first stage and one assembly machine in the second stage. Allahverdi and Aydilek [12] proposed metaheuristic algorithms, and Ha et al. [13] and Lee and Bang [14] derived a branch-and-bound algorithm. Kazemi et al. [15] investigated a two-stage assembly flowshop scheduling problem with a batched delivery system where there are m independent machines at the first stage and multiple assembly machines at the second stage. They proposed some heuristic algorithms so as to minimize the sum of tardiness penalty and delivery costs.Within the author's knowledge, no studies have addressed the total weighted tardiness objective on an assembly scheduling problem. This paper is to find effective and efficient schedules to minimize the total weighted tardiness of jobs. Section2 presents the problem description, and Sections 3 and 4 characterize some solution properties to improve search effectiveness and efficiency. Moreover, four constructive heuristics, HEDD, HWT, WSPTMAX, and WSPTAVER, are derived in Section 5, lower-bound procedures are derived in Section 6, and a branch-and-bound algorithm is derived in Section 7. The performance of the proposed algorithms is evaluated through numerical experiments in Section 8.


## 2. Problem Description

This study hasn jobs to process and a job consists of m components which are processed in the first stage, and the m manufactured components are assembled in the second stage. Component k (k = 1, 2, …, m) of each job is processed in dedicated machine k, and the processing time ajk is required for component k of job j (j = 1, 2, …, n, k = 1, 2, ..., m). In addition, the assembly of job j can start in the assembly machine after the completion of all the components, and the required assembly time is bj (j = 1, 2, ..., n). The assembly system in this paper is presented in Figure 1.Figure 1
The assembly system in this paper.It is assumed that more than one job in a machine cannot be processed at the same time, and no preemption is allowed in any processing. The completion time of a job is the completion time of the assembly at the second stage, which is expressed asCj. dj denotes the due date for job j, and then the tardiness value of job j is computed as Tj=maxCj−dj,0. Thus, the total weighted tardiness of n jobs is ∑j=1nwjTj=∑j=1nwjmaxCj−dj,0, where wj denotes the weight for job j.This paper introduces Property1 which can reduce the solution space to search, where the permutation schedule means that the production order is the same in all the machines.Property 1.
An optimal schedule exists among permutation schedules.Proof.
It can be easily shown by a pairwise job interchange augment.


## 3. Identical Weight Casew1=w2=⋯=wn

Now, we characterize some dominance properties for finding better schedules for the problem. These properties can be used in some heuristic algorithms and a branch-and-bound algorithm. This section considers the situation where all the job weights are identical; that is,w1=w2=⋯=wn.For the property derivation, assume that jobsp and q are processed consecutively. Denote by S a schedule in which job p is processed immediately before job q, while R denotes a schedule which is identical to S but job q is processed immediately before job p. Moreover, π denotes a set of jobs processed before jobs p and q in S and R. Some solution properties are presented for jobs p and q as follows.Property 2.
If the following conditions hold, jobq should be processed immediately before p:(1)CpR≤dp,(2)CpR≤CqS.Proof.
We prove that scheduleS is dominated by R under conditions (1) and (2). First, we can easily see that the completion time of job q in schedule R is smaller than that of job q in S, so that the relation TqR≤TqS holds. Condition (1) implies TpR=0, so that the following relation holds:(3)TpR+TqR=TqR≤TpS+TqS.
If condition (2) is satisfied, the earliest start time of a job after jobs p and q on the assembly machine in R is no later than the earliest start time of a job after p and q in S. Therefore, we can conclude that schedule S is dominated by schedule R.Property 3.
If the following conditions hold, jobq should be processed immediately before p:(4)CpR≤dp,(5)CpR≤minx∉π∪p,qmax1≤k≤m∑y∈π∪p,qayk+axk.Proof.
As we discussed earlier in Property2, condition (4) implies that the following relation holds:(6)TpR+TqR=TqR≤TpS+TqS.
In condition (5), the right-hand-side term means the possible earliest start time after jobs p and q on the assembly machine. Condition (5) represents that the q ⟶ p sequence in R does not delay the processing of any jobs after jobs p and q. Therefore, we can conclude that schedule S is dominated by schedule R.Property 4.
If the following conditions hold, jobq should be processed immediately before p:(7)CpR≤CqS,(8)CqR≤CpS,(9)dq≤dp.Proof.
Remind that theq ⟶ p sequence is in schedule R, while the p ⟶ q sequence is in schedule S. From equations (7) and (8), we can see that the completion times of jobs q and p in R are earlier than the completion times of p and q in S, respectively. Now, the following cases are considered:(i)
Case 1. CqR≤dq and CpR≤dp.In this case, both jobsp and q are completed before each due date, so the following relation holds:(10)TqR+TpR=maxCqR−dq,0+maxCpR−dp,0=0.From the above equation, we can see thatTqR+TpR≤TpS+TqS holds.(ii)
Case 2. CqR>dq and CpR>dp.In this case, both jobsp and q are tardy, so the following relation holds:(11)TqR+TpR=maxCqR−dq,0+maxCpR−dp,0=CqR−dq+CpR−dp≤CpS−dq+CqS−dp,(due to conditions (7)–(9))(12)≤maxCpS−dp,0+maxCqS−dq,0=TpS+TqS.(iii)
Case 3. CqR≤dq and CpR>dp.From the condition,TqR+TpR=maxCqR−dq,0+maxCpR−dp,0=CpR−dp≤CqS−dp≤CqS−dq (due to conditions (7) and (9)) ≤maxCpS−dp,0+maxCqS−dq,0=TpS+TqS.(iv)
Case 4. CqR>dq and CpR≤dp.From the condition,TqR+TpR=maxCqR−dq,0+maxCpR−dp,0=CqR−dq≤CpS−dq (due to condition (8)) ≤maxCpS−dp,0+maxCqS−dq,0=TpS+TqS.
From cases 1, 2, 3, and 4, we can say thatTqR+TpR≤TpS+TqS holds.Property 5.
If the following conditions hold, jobq should be processed immediately before p:(13)CqR≥dq,(14)CqR≤CpS,(15)tv+aqv≤mintu+apu,tx+bq,where tk represents the completion time of the last-positioned job before jobs p and q on machine k.
The indicesx, u, and v represent the machine indices satisfying the following relation:(16)tx+apx+apx=max1≤k≤mtk+apk+aqk,tu+apu=max1≤k≤mtk+apk,tv+aqv=max1≤k≤mtk+aqk.Proof.
At first, we try to showCpR≤CqS. CqS and CpR can be expressed as follows:(17)CqS=maxtA,tu+apu,tx+apx+aqx−bp+bp+bq,CpR=maxtA,tv+aqv,tx+aqx+apx−bq+bp+bq,where tA denotes the completion time of the job immediately before jobs p and q on the assembly machine. From condition (15), the following relation is true:(18)tu+apu≥tv+aqv.
Then, in order to prove the relationCpR≤CqS, we have to show that the tu+apu≥tx+aqx+apx−bq holds as follows:(19)tu+apu−tx+aqx+apx−bq≥tx+apx−tx+aqx+apx−bqfrom the definition of the indexu=tx+bq−tx+aqx≥tx+bq−tv+aqvfrom the definition of the indexv.
From condition (15), the relation tx+bq≥tv+aqv is true. Thus, the above equation tx+bq−tv+aqv≥0 is true; then,(20)tu+apu≥tx+aqx+apx−bq.
From equations (18) and (20), the following equation holds:(21)CpR≤CqS.
From condition (14) and equation (21), we have CqR≤CpS and CpR≤CqS. In order to say that schedule R is better than schedule S, due date dp should be examined additionally as in the two following cases:(i)
Case 1.CpS≥dp. Both p and q are tardy from condition (13), so the following relation holds:(22)TpS+TqS=CpS−dp+CqS−dq,TqR+TpR=CqR−dq+CpR−dp.From equations (14) and (21), we can see that TqR+TpR≤TpS+TqS holds.(ii)
Case 2.CpS<dp. From (13) and (14), the following relation holds:(23)dq≤CqR≤CpS<dp.
From (14), (21), and (32), we can say that TqR+TpR≤TpS+TqS holds according to Property 4.
Property6 is an extension of Schaller [16], dominance property which is applied in this paper.Property 6.
If the following conditions hold, jobq should be processed immediately before p:(24)TqR+TpR≤TpS+TqS,(25)TpS+TqS−TqR+TpR≥CpR−CqSn−nπ−2,where nπ denotes the number of jobs in the set π.Proof.
If condition (24) is satisfied, the sum of tardiness of jobs p and q in R is smaller than that of S. In condition (25), the right-hand-side term CpR−CqSn−nπ−2 represents the upper limit of the potential tardiness increment of the jobs after p and q. From condition (25), we can say that schedule S is dominated by schedule R.


## 4. Nonidentical Weight Case

Now, we present some dominance properties for the situation where all the job weights would be nonidentical. Some solution properties are characterized for jobsp and q as follows.Property 7.
If the following conditions hold, jobq should be processed immediately before p:(26)CpR≤dp,CpR≤CqS.Proof.
The proof is the same as in Property2.Property 8.
If the following conditions hold, jobq should be processed immediately before p:(27)CpR≤dp,CpR≤minx∉π∪p,qmax1≤k≤m∑y∈π∪p,qayk+axk.Proof.
The proof is the same as in Property3.Property 9.
If the following conditions hold, jobq should be processed immediately before p:(28)wqTqR+wpTpR≤wpTpS+wqTqS,wpTpS+wqTqS−wqTqR+wpTpR≥CpR−CqS∑x∉π∪p,qwk.Proof.
The proof can be made in a similar manner in Property6.


## 5. Constructive Heuristic Algorithms

This paper proposes four constructive heuristic algorithms. Letπ denote a partial sequence whose processing order is already assigned. The heuristic algorithms in this paper are based on a scheme which selects one job that has not been yet allocated and attaches it to the end position of the partial sequence π. Let Cπ denote the completion time of the last-positioned job in π.This paper proposes an EDD (Earliest Due Date) type heuristic. A specific procedure is as follows, whereCπj denotes the possible completion time of job j when attaching job j to the end position of π, and thus, Cπj=maxmax1≤k≤mCkπ+ajk,Cπ+bj, where Ckπ denotes the completion time of the last-positioned job in machine k in π.


### 5.1. Heuristic HEDD

Step 0.y⟵0, π⟵∅, Cπ⟵0, Ckπ⟵0 for k = 1, 2, …, 0Step 1. Select a jobj∗ with the smallest due date dj value for j ∉ πStep 2. Add the jobj∗ to the end position of the set πy⟵y+1,π⟵π∪j∗,Cπ⟵Cπj∗,Ckπ⟵Ckπ+aj∗k,fork=1,2,…,0Step 3. Ify=n, then terminate. Otherwise, go to Step 1It is true that EDD-type heuristics generally perform well in the scheduling problems associated with the due date objective measures. However, in the total weighted tardiness as in this study, it may be difficult to guarantee the performance of EDD-type heuristics because the schedule must be changed according to the job weight. Therefore, this paper presents another heuristic based on the job weight as follows.


### 5.2. Heuristic HWT

Step 0.y⟵0, π⟵∅, Cπ⟵0, Ckπ⟵0 for k = 1, 2, …, 0Step 1. Select a jobj∗ with the largest weight wj value for j ∉ πSteps 2 and 3. The same as in the heuristic HEDDHeuristic HEDD can be expected to show excellent performance in situations sensitive to the due date parameters, while heuristic HWT can be expected to show better performance in the weight-sensitive situations. However, it can be said that the two heuristics now have limitations in that they do not consider processing times on machines. Now, this study presents two additional heuristics, called WSPTMAX and WSPTAVER, which consider processing times. The first heuristic WSPTMAX calculates the maximum value of the processing times of each job in the first stage and selects a job with the smallest value of the value αj=max1≤k≤majk+bj/wj. The second heuristic WSPTAVER calculates the average value of the processing times of each job in the first stage and selects a job with the smallest value of the value βj=1/m∑k=1majk+bj/wj. The two heuristics have an inherent limitation that they do not consider due dates, but they can be said to be very advantageous in that they consider processing times and weights together. If the completion time can be accelerated considering the processing times, it can be said that due date parameters are satisfied as a result. The specific procedures of the two heuristics are presented as follows.


### 5.3. Heuristic WSPTMAX

Step 0.y⟵0, π⟵∅, Cπ⟵0, Ckπ⟵0 for k = 1, 2, …, 0Calculate the valueαj=max1≤k≤majk+bj/wj for all job jStep 1. Select a jobj∗ with the smallest αj value for j ∉ πSteps 2 and 3. The same as in the heuristic HEDD


### 5.4. Heuristic WSPTAVER

Step 0.y⟵0, π⟵∅, Cπ⟵0, Ckπ⟵0 for k = 1, 2, …, 0Calculate the valueβj=1/m∑k=1majk+bj/wj for all job jSteps 1, 2, and 3. The same as in the heuristic WSPTMAX


## 5.1. Heuristic HEDD

Step 0.y⟵0, π⟵∅, Cπ⟵0, Ckπ⟵0 for k = 1, 2, …, 0Step 1. Select a jobj∗ with the smallest due date dj value for j ∉ πStep 2. Add the jobj∗ to the end position of the set πy⟵y+1,π⟵π∪j∗,Cπ⟵Cπj∗,Ckπ⟵Ckπ+aj∗k,fork=1,2,…,0Step 3. Ify=n, then terminate. Otherwise, go to Step 1It is true that EDD-type heuristics generally perform well in the scheduling problems associated with the due date objective measures. However, in the total weighted tardiness as in this study, it may be difficult to guarantee the performance of EDD-type heuristics because the schedule must be changed according to the job weight. Therefore, this paper presents another heuristic based on the job weight as follows.


## 5.2. Heuristic HWT

Step 0.y⟵0, π⟵∅, Cπ⟵0, Ckπ⟵0 for k = 1, 2, …, 0Step 1. Select a jobj∗ with the largest weight wj value for j ∉ πSteps 2 and 3. The same as in the heuristic HEDDHeuristic HEDD can be expected to show excellent performance in situations sensitive to the due date parameters, while heuristic HWT can be expected to show better performance in the weight-sensitive situations. However, it can be said that the two heuristics now have limitations in that they do not consider processing times on machines. Now, this study presents two additional heuristics, called WSPTMAX and WSPTAVER, which consider processing times. The first heuristic WSPTMAX calculates the maximum value of the processing times of each job in the first stage and selects a job with the smallest value of the value αj=max1≤k≤majk+bj/wj. The second heuristic WSPTAVER calculates the average value of the processing times of each job in the first stage and selects a job with the smallest value of the value βj=1/m∑k=1majk+bj/wj. The two heuristics have an inherent limitation that they do not consider due dates, but they can be said to be very advantageous in that they consider processing times and weights together. If the completion time can be accelerated considering the processing times, it can be said that due date parameters are satisfied as a result. The specific procedures of the two heuristics are presented as follows.


## 5.3. Heuristic WSPTMAX

Step 0.y⟵0, π⟵∅, Cπ⟵0, Ckπ⟵0 for k = 1, 2, …, 0Calculate the valueαj=max1≤k≤majk+bj/wj for all job jStep 1. Select a jobj∗ with the smallest αj value for j ∉ πSteps 2 and 3. The same as in the heuristic HEDD


## 5.4. Heuristic WSPTAVER

Step 0.y⟵0, π⟵∅, Cπ⟵0, Ckπ⟵0 for k = 1, 2, …, 0Calculate the valueβj=1/m∑k=1majk+bj/wj for all job jSteps 1, 2, and 3. The same as in the heuristic WSPTMAX


## 6. A Lower-Bound Procedure

This section proposes a lower-bound procedure to evaluate the performance of the derived heuristic algorithms, and this lower bound can also be used in the branch-and-bound algorithm developed in a later part of this paper. In the following lower bound LB1, [y] denotes the y-th smallest number in the parameters ajk’s, bj’s, and wj’s.


### 6.1. Lower-Bound LB1

Step 0. Calculate theDj value as follows:(29)Dj=max1≤k≤m∑1≤y≤jayk+bmin,forj = 1, 2, …, n, where bmin=min1≤i≤nbiStep 1. CalculateLB1 as ∑1≤j≤nwn−j+1max0,Dj−dmax, where dmax=max1≤i≤ndiIn the above lower bound,Dj denotes a lower-bound value of the completion time of any possible j-th positioned job:(30)∑1≤j≤nwjTj=∑1≤j≤nwjmax0,Cj−dj≥∑1≤j≤nwjmax0,Cj−dmax.(k) denotes the k-th positioned job in any schedule, and then,(31)=∑1≤j≤nwjmax0,Cj−dmax≥∑1≤j≤nwjmax0,Dj−dmax.To derive a lower-bound value of equation (31), we sequence wj values in nondecreasing order:(32)≥∑1≤j≤nwn−j+1max0,Dj−dmax.Therefore, we can say that the lower-bound LB1 provides a lower bound for the original problem. The complexity order of the lower bound LB1 is Onlogn. Two more lower bounds are derived on Property 10, which was verified by Chu [17] and Kim [18].Property 10.
For theCj and dj values satisfying C1≤C2≤⋯≤Cn, then the following relation holds:(33)∑j=1nmaxCj−dj,0≥∑j=1nmaxCj−dj,0.
Based on Property10, this paper proposes two more lower bounds LB2 and LB3. The second lower bound LB2 is calculated as follows; we can begin with the fact that the completion time of the first job, C1, cannot be larger than the following value under the condition C1≤C2≤⋯≤Cn:(34)C1≥min1≤j≤nmax1≤k≤majk+b1.
In inequality (34), the value min1≤j≤nmax1≤k≤majk is the possible earliest starting time of processing, and b1 is the smallest assembly time among all the jobs. From (34), an additional relation for the x-th smallest completion time Cx holds as follows:(35)Cx≥min1≤j≤nmax1≤k≤majk+b1+b2+⋯+bx.
From (34) and (35), we can derive the second lower bound LB2 as follows:(36)LB2=∑j=1nwminmaxmin1≤i≤nmax1≤k≤maik+∑x=1jbx−dj,0.
Now, we show the process of deriving the third lower bound LB3; we can derive another relation that can replace equation (34) as follows:(37)C1≥max1≤k≤ma1k+bmin.
The valuemax1≤k≤ma1k is the possible earliest starting time of processing in the assembly machine. From (37), an additional relation for the x-th smallest completion time Cx holds as follows:(38)Cx≥max1≤k≤m∑j=1xajk+bmin.
From (37) and (38), we derive the second lower bound LB3 as follows:(39)LB3=∑j=1nwminmaxmax1≤k≤m∑x=1jaxk+bmin−dj,0.


## 6.1. Lower-Bound LB1

Step 0. Calculate theDj value as follows:(29)Dj=max1≤k≤m∑1≤y≤jayk+bmin,forj = 1, 2, …, n, where bmin=min1≤i≤nbiStep 1. CalculateLB1 as ∑1≤j≤nwn−j+1max0,Dj−dmax, where dmax=max1≤i≤ndiIn the above lower bound,Dj denotes a lower-bound value of the completion time of any possible j-th positioned job:(30)∑1≤j≤nwjTj=∑1≤j≤nwjmax0,Cj−dj≥∑1≤j≤nwjmax0,Cj−dmax.(k) denotes the k-th positioned job in any schedule, and then,(31)=∑1≤j≤nwjmax0,Cj−dmax≥∑1≤j≤nwjmax0,Dj−dmax.To derive a lower-bound value of equation (31), we sequence wj values in nondecreasing order:(32)≥∑1≤j≤nwn−j+1max0,Dj−dmax.Therefore, we can say that the lower-bound LB1 provides a lower bound for the original problem. The complexity order of the lower bound LB1 is Onlogn. Two more lower bounds are derived on Property 10, which was verified by Chu [17] and Kim [18].Property 10.
For theCj and dj values satisfying C1≤C2≤⋯≤Cn, then the following relation holds:(33)∑j=1nmaxCj−dj,0≥∑j=1nmaxCj−dj,0.
Based on Property10, this paper proposes two more lower bounds LB2 and LB3. The second lower bound LB2 is calculated as follows; we can begin with the fact that the completion time of the first job, C1, cannot be larger than the following value under the condition C1≤C2≤⋯≤Cn:(34)C1≥min1≤j≤nmax1≤k≤majk+b1.
In inequality (34), the value min1≤j≤nmax1≤k≤majk is the possible earliest starting time of processing, and b1 is the smallest assembly time among all the jobs. From (34), an additional relation for the x-th smallest completion time Cx holds as follows:(35)Cx≥min1≤j≤nmax1≤k≤majk+b1+b2+⋯+bx.
From (34) and (35), we can derive the second lower bound LB2 as follows:(36)LB2=∑j=1nwminmaxmin1≤i≤nmax1≤k≤maik+∑x=1jbx−dj,0.
Now, we show the process of deriving the third lower bound LB3; we can derive another relation that can replace equation (34) as follows:(37)C1≥max1≤k≤ma1k+bmin.
The valuemax1≤k≤ma1k is the possible earliest starting time of processing in the assembly machine. From (37), an additional relation for the x-th smallest completion time Cx holds as follows:(38)Cx≥max1≤k≤m∑j=1xajk+bmin.
From (37) and (38), we derive the second lower bound LB3 as follows:(39)LB3=∑j=1nwminmaxmax1≤k≤m∑x=1jaxk+bmin−dj,0.


## 7. A Branch-and-Bound Algorithm

This paper derives a branch-and-bound method to find the optimal solution for medium-size problems. The proposed branch-and-bound algorithm uses depth-first search as a branching rule, which means selecting the lowest node (i.e., the node with the largest partial permutation) in the branching tree when selecting a node. In the case of a tie, the node having the lowest lower bound is selected.In the B&B algorithm, the initial upper bound is obtained from the minimum value among the four heuristics H1, HEDD, WSPTMAX, and WSPTAVER proposed in Section 5:(40)UB=minH1,HEDD,WSPTMAX,WSPTAVER.This paper uses the largest of the three values LB1, LB2, and LB3 as the lower bound for the branch-and-bound algorithm as follows:(41)LB=maxLB1,LB2,LB3.


### 7.1. Branch-and-Bound Algorithm

Step 0 (initialization).r⟵0, πr⟵∅, π˜r⟵1,2,…,n.Calculate the valueUB=minH1,HEDD,WSPTMAX,WSPTAVER.Step 1 (lower bound). CalculateLBrj=maxLB1,LB2,LB3,forj∈π˜r.Step 2 (branching).Ifπ˜r=1, then go to Step 4.IfLBrj=∞,forj∈π˜r, then go to Step 5.Selectk such as argminj∈π˜rLBrj, and(42)r⟵r+1,πr⟵πr−1∪k,π˜r⟵π˜r−1−k.Step 3 (dominance properties).IfLBrk≥UB then go to Step 5.If any of Properties2∼9. holds, then go to Step 5.Go to Step 1.Step 4 (update the upper bound).If the last level of the enumeration tree is reached, the total weighted tardiness WTT is calculated.IfWTT<UB, then UB⟵WTT.Step 5. The current node no longer needs to be searched:(43)r⟵r−1,LBrk⟵∞.Ifr≥0, then go to Step 2. Otherwise terminate the B&B algorithm.The optimal solution is UB.


## 7.1. Branch-and-Bound Algorithm

Step 0 (initialization).r⟵0, πr⟵∅, π˜r⟵1,2,…,n.Calculate the valueUB=minH1,HEDD,WSPTMAX,WSPTAVER.Step 1 (lower bound). CalculateLBrj=maxLB1,LB2,LB3,forj∈π˜r.Step 2 (branching).Ifπ˜r=1, then go to Step 4.IfLBrj=∞,forj∈π˜r, then go to Step 5.Selectk such as argminj∈π˜rLBrj, and(42)r⟵r+1,πr⟵πr−1∪k,π˜r⟵π˜r−1−k.Step 3 (dominance properties).IfLBrk≥UB then go to Step 5.If any of Properties2∼9. holds, then go to Step 5.Go to Step 1.Step 4 (update the upper bound).If the last level of the enumeration tree is reached, the total weighted tardiness WTT is calculated.IfWTT<UB, then UB⟵WTT.Step 5. The current node no longer needs to be searched:(43)r⟵r−1,LBrk⟵∞.Ifr≥0, then go to Step 2. Otherwise terminate the B&B algorithm.The optimal solution is UB.


## 8. Computational Experiments

This section measures the performance of the branch-and-bound algorithms and the heuristic algorithms through various numerical tests. For the test, the generated experimental data is set as follows:(1)
The parametersajk, bj, and wj(j = 1,…,n, k = 1,…,m) are generated from U (1, 100), where U (x, y) represents a uniform distribution with the numbers x and y.(2)
The due datesdj (j = 1,…,n) are generated from UP1−TF−RDD/2,P1−TF+RDD/2, where P denotes a possible lower-bound value of the makespan value:(44)P=maxmax1≤k≤m∑j=1najk+min1≤j≤nbj,min1≤j≤nmax1≤k≤majk+∑j=1nbj.We conducted computational experiments with the number of jobsn in {5, 7, 9, 11, 13, 15} and the number of machines m in {2, 4, 6}. The coefficients RDD (relative range of due date) and TF (tardiness factor) are from the values {0.2, 0.5, 0.8} for the due date generation. 20 problems were randomly generated for 162 combinations of jobs and machines and RDD and TF values, and then a total of 3,240 problems were generated.For the performance evaluation of the proposed branch-and-bound algorithm, the computational experiments are summarized in Table1. In the table, “the number of nodes” refers to the total number of the generated nodes, and “computational time” refers to the computing time of the branch-and-bound algorithm. From the table, we can see that the optimal solutions were found within 1,200 seconds (CPU) for instances with up to about 15 jobs, and the average number of nodes and computational time of the B&B algorithm do not increase significantly as the number of machines increases. From the fact that the number of nodes and computational time decrease in some cases as the number of machines increases, we can possibly say that the lower-bound mechanism of the B&B algorithm is effective. Moreover, this paper tries to evaluate the performance of the dominance properties in Sections 3 and 4. We can see the performance summary of the B&B algorithm without any dominance properties applied. From the table, the computational time and the average number of search nodes increased significantly when the dominance properties were not applied, and specifically optimal solutions were not found for problems with 15 jobs within 20 minutes. From the comparative experiments, we can say that the dominance properties contribute to the performance of the B&B algorithm.Table 1
The performance summary of the branch-and-bound algorithm.
nmB&B with dominance propertiesB&B without dominance propertiesComputational timeThe number of nodesComputational timeThe number of nodesAverageMaxAverageMaxAverageMaxAverageMax520.00070.00434.11090.00080.00447.0917640.00080.00533.8960.00070.00147.510660.00080.00332.71050.00080.00347.6121720.0020.007456.521980.0030.008861.7309340.0020.01460.230120.0030.01920.1321560.0020.01399.917370.0030.01841.02471920.050.211893.4759860.090.426816.916293840.050.312159.7921720.10.527496.817052560.040.28685.7390960.10.324986.6879341122.0433.5383616.182903454.950.01231820.61569694042.344.2401569.194761355.653.21281161.91617386662.013.7287125.622302985.327.31060709.66218744132170.61147.526198107.8257803159352.11180.473275993.72479930274132.41140.918033822.7185741409376.71187.969507001.42491380796140.01120.216511705.6155593682378.21185.262695670.7204011606152910.21194.7113697715.3119565585∗∗∗∗4913.81144.996860705.2133536399∗∗∗∗6907.41171.986202170.587887442∗∗∗∗∗ means the problem instances that the B&B algorithm cannot find the optimal solutions.This paper conducted some experiments to investigate the performance change according to the RDD and TF values. The computational tests are carried out withn = 9 and m = 2 and are presented in Table 2. For each combination of RDD and TF values from {0.2, 0.5, 0.8}, 20 problems were randomly generated. The performance of the proposed B&B algorithm is summarized in Table 2. From the table, the performance of the B&B algorithm does not seem to fluctuate significantly according to the RDD and TF values.Table 2
The performance of the B&B algorithm according to RDD and TF undern = 9 and m = 2.
RDDTFComputational timeThe number of nodesAverageMaxAverageMax0.20.20.0290.17511626.45365200.50.0280.0714143.25120490.80.0390.155650.75235050.50.20.0490.1799536.7349110.50.0450.1227760.05235260.80.0510.1468294.2236230.80.20.0310.1275547.8217370.50.0610.16411497.05281910.80.0760.20514115.0539096The performance of four heuristics HEDD, HWT, WSPTMAX, and WSPTAVER are given in Tables 3 and 4. In the table, the term “error” means the average error of the associated heuristic compared to the lower-bound value and is defined as follows:(45)error=WTSH−LBWTSWorst−LB,where WT (SH) is the total weighted tardiness of an obtained solution from a heuristic and LB is a lower-bound value in Section 6; thus, LB=maxLB1,LB2,LB3, and WT (SWorst) is the largest value among solutions obtained from four heuristics HEDD, HWT, WSPTMAX, and WSPTAVER. The smaller the value error, the better the performance of the associated heuristic. 180 instances are solved for each combination of jobs and machines. In the table, NO denotes the number of problems that the associated heuristic found the best solution among four heuristic values. NO value can reach up to 180, but since multiple heuristics can produce the same value, the sum of the NO values of the four heuristics can exceed 180.Table 3
The performance summary of the four heuristic algorithms.
nmHEDDHWTWSPTMAXWSPTAVERAver. errorNOAver. errorNOAver. errorNOAver. errorNO520.881320.650800.639890.6489440.875350.656830.655940.6957160.882300.655980.676920.69676720.867330.633680.639720.6445840.868260.655730.660680.6984860.898250.667830.695640.70356920.832430.678610.685630.6885340.846370.650800.685560.7003560.851360.659830.691450.709461120.821420.703520.675580.6994840.829440.674640.695460.7214260.837400.647860.712370.743281320.831410.680450.637490.6615340.843410.653770.683370.7072960.826450.675820.707290.715261520.809460.673520.665500.6804040.807490.662730.714340.7332660.830440.656730.696360.70330Table 4
The performance of the four heuristics according to RDD and TF undern = 9, m = 2.
RDDTFHEDDHWTWSPTMAXWSPTAVERAver. errorNOAver. errorNOAver. errorNOAver. errorNO0.20.20.86840.50160.568100.561100.50.98200.593100.60180.57950.80.99700.677100.67480.70550.50.20.624110.67660.81420.830.50.93150.62760.62680.65260.80.97710.76960.7290.72560.80.20.221160.85630.79620.80200.50.90550.7470.72360.72870.80.98510.66770.646100.63911From the test result, it seems that HEDD does not show good performance and HWT shows relatively excellent results in the experiments. It may be because algorithms are more sensitive to the job weight fluctuations. Therefore, it can be interpreted to be more advantageous to process high-weight jobs preferentially.Table4 shows the performance change of the four heuristics according to the RDD and TF values. The experiment was carried out with the instances of 9 jobs and 2 machines, and 20 problems are solved for combinations of RDD and TF. In the table, NO value can reach up to 20, but the sum of NO values can exceed 20. From Table 4, it can be seen that the performance of the heuristics varies depending on the RDD and TF values. When the value of RDD increases and the value of TF decreases, the performance of HEDD tends to improve. The larger the RDD value, the greater the deviation of the due dates, and the smaller the TF value, the greater the chance of tardy jobs. It can be seen that HEDD heuristic performs better where the problem is more sensitive to due dates.We conducted computational experiments with large-size jobs from 30 to 270 and the number of machines in {2, 4, 6}. 180 problems were randomly generated for 9 combinations of RDD and TF values, and then a total of 4,860 problems were generated. Table5 shows the performance summary of the four heuristics. NO value can reach up to 180, but the sum of NO values can exceed 180. From the table, HWT shows the best performance among the four heuristics, while when the number of machines is 2, HEDD performs well.Table 5
The performance summary of the four heuristic algorithms for large-size problems.
nmHEDDHWTWSPTMAXWSPTAVERAver. errorNOAver. errorNOAver. errorNOAver. errorNO3020.776500.681510.690480.6983140.760510.658740.712350.7282060.761530.679740.728270.756266020.743590.694460.693530.7102240.743600.686780.743270.7741560.747560.658940.737210.75999020.740580.696530.703440.7182540.731600.671890.739210.7601060.734600.6751040.753110.782512020.733600.713510.731490.7522040.738590.676980.745150.773860.740580.6721110.76180.789315020.729610.707430.728500.7462640.732600.676990.748160.774560.729600.6761040.771120.802418020.746570.705520.716450.7352640.731600.6761060.76190.788560.724600.6591150.76540.796121020.744590.711490.719550.7411740.736600.6741050.764100.788560.737590.6691150.77460.803024020.743590.707560.723430.7432240.728600.6761100.76380.793260.721600.6681160.77630.809127020.730600.697520.711500.7301840.726610.6731070.756100.782260.727590.6581200.76510.8020


## 9. Concluding Remarks

This paper considers a two-stage assembly scheduling problem where there arem dedicated machines in the first stage and an assembly machine in the second stage. This paper proposes some solution approaches to establish effective and efficient schedules to minimize the total weighted tardiness measure. In this paper, we develop some dominance properties and lower-bound procedures, derive a branch-and-bound algorithm for finding optimal solutions, and derive four heuristics. Computational tests are performed to evaluate the solution approaches in this paper. For problems with no more than 15 jobs, the B&B algorithm finds optimal solutions within 20 minutes, and the performance of the four heuristics seems to be similar. However, for problems with more than 30 jobs, HWT shows the best performance among the four heuristics, while when the number of machines is two, the performance of HEDD is better.



---

*Source: 9723439-2020-09-27.xml*