The Lagrangean Relaxation for the Flow Shop Scheduling Problem with Precedence Constraints, Release Dates and Delivery Times

Abstract

This work aims to present a methodology to support a company in the automotive business on scheduling the jobs on its final processes. These processes are: (i) checking the final product and (ii) loading the dispatch trucks. These activities are usually found in the outbound area of any manufacturing company. The problem faced is defined as the flow shop problem with precedence constraints, release dates, and delivery times. The major objective is to minimize the latest date a client receives its products. We present a time-indexed integer mathematical model to compute feasible solutions for the presented problem. Moreover, we take advantage of the Lagrangean Relaxation procedure to compute valid lower and upper bounds. The experiments were held based on the company’s premises. As a conclusion, the results showed that the methodology proposed was able to compute feasible solutions for all the instances tested. Also, the Lagrangean Relaxation approach was able to calculate better bounds in a shorter computational time than the Mathematical problem for the more complicated instances.

This work is licensed under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

1. Introduction

Many companies sort their processes in a sequential way. The sequential standard follows quite well the concept that each process has its suppliers and clients, which may be represented by the previous and the successor processes, respectively.

The problem defined above may be viewed as a flow shop one [1]. In the flow shop approach, each process may be viewed as a single or a set of machines. Each machine is responsible for executing a specific task. Moreover, all the jobs must follow the same order of machines. So, after a job completes a task in a machine, it must join the queue at the next machine. Furthermore, the tasks must be executed under some constraints such as release dates or resources availability. In this work, we approach a real-world problem that may be equivalent to a flow shop problem with precedence constraints, release dates, and delivery times. The company evaluated in this work, focuses its activities on the car-assembling business. We concerned with a part of the company’s processes to carry out the work. To be precise, we focus on the three final processes of the company’s production flow, which are the checking, loading, and dispatching. In addition, we work under a set of premises. As a result, we state the studied problem as the flow shop problem with precedence constraints, release dates, and delivery times with the objective function of minimizing the makespan. That problem is defined as a strongly NP-hard problem [2]. The problem is depicted in Figure 1 and described as follows.

[figure omitted; refer to PDF]

The observed company acts in the automotive business, and it is able to produce up to 2.000 products each day. We highlight that the products are not all the same, because there may exist differences between them. So, after the manufacturing phases, each product is assigned to a cluster. A cluster is represented by the letters A, B, and C in Figure 1. One cluster is set based on the similarities of the products. Also, each cluster must pass a quality control process to avoid sending poor-quality products to the final clients. The control consists of evaluating each product individually. As a result, the operator receives a list of clusters needed to be checked. Then, each cluster is schedule and checked one by one. It is noteworthy to state that the time spent at each cluster may vary according to the type of the products that compound the cluster, and the failures that may be found, as well. Usually, the cluster is compounded by a set of products that do not significantly differ from themselves.

In contrast, some products do differ from themselves, and that is the reason that justifies the clustering procedure. So, the company does not mix different products in the same cluster.

Afterward the checking phase, an established cluster is fragmented. In other words, the products that compound that cluster, are placed in a waiting zone and assorted according to its destinations. Usually, clients receive products that belong to a variety of clusters. So, after a truck’s load has already been completely placed in the waiting area, the dispatching truck is authorized to get inside the marquee. Therefore, a truck is not allowed to get inside before all its cargo have already been placed in the waiting zone. So, we can assume that each outgoing truck has a precedent-jobs list. Then, after the truck arrival, the operators start to load the truck and conclude their task after an amount of time, which may vary according to the truck type, the cargo and the paperwork required. In this work, we assume that there is one team in charge of loading the trucks. As a result, we can not assume that more than one truck is loading at the same time.

Finally, the last process is the Dispatching one. Here the truck departs from the company towards the client’s location. We highlight that we did not consider evaluating which route the truck driver should do, but the average duration to reach the clients’ locations instead.

So, we considered modeling the checking and the loading process as machines. So, the checking process is defined as the Machine 1 ( $M_1$ ) and the loading process as the Machine 2 ( $M_2$ ). Moreover, we state the main objective is to minimize the maximum date when a client receives its products. As a result, we decided to model this problem as a two-machine flow shop scheduling problem. Therefore, we define this problem as the two-machine flow shop scheduling problem with precedence constraints, release dates and delivery times.

Also, we modeled it through a time-indexed formulation which is based on the discretization of the time horizon. This kind of formulation is known to provide tighter linear relaxation bounds. However, the model presents a high number of variables.

In this work, we face two primary objectives. The first is to present a suitable model to cope with the flow shop problem with precedence constraints, release dates and delivery times. The second goal is to solve the proposed model problem through an appropriated decomposition method. Here, we propose an integer linear programming model on time-indexed variables and a Lagrangean Relaxation (LR) approach to obtain both upper and lower bounds. The sub-gradient method was chosen to carry out the convergence of the LR. See [3].

The paper is organized as follows. The mathematical model section presents the integer linear programming model. The Lagrangean Relaxation section describes the decomposition approach. The Computational Results section reports experiments results. Finally, the Conclusions section concludes the paper.

2. The Mathematical Model

The two-machine flow shop scheduling problem with precedence constraints, release dates and delivery times is set as ( $F2|prec,r_j,q_j|D_{\max }$ ). In other words, we aim to solve a scheduling problem, whose target is to minimize the date when the last product will be delivered to the client. Moreover, we deal with a set of constraints related to the company’s machines. These constraints state that the machines are not allowed to work with more than one job at the same time. Also, all those jobs must be executed only once. Besides that, there is a precedence list in order to enable a job to be processed in machine 2. We present the mathematical model of this formulation next.

The notation was set based on [1]. The term F2 means that there are two machines in sequence. The terms ( $prec,r_j,q_j$ ) mean that there are three classes of constraints applied, which are: the precedence, the release dates and the delivery times ones, respectively. Finally, the $D_{\max }$ term refers to the objective function of minimizing the latest date a client receives its products. Moreover, the ( $F2|prec,r_j,q_j|D_{\max }$ ) can be described as follows. Consider a set $J^1=\left\{1,...,n\right\}$ of jobs to be processed on the first machine $M_1$ , which correspond to the clusters to be processed at the first machine. Likewise, consider a set $J^2=\left\{1,...,m\right\}$ of jobs to be processed on the second machine $M_2$ , which correspond to outgoing trucks to be loaded at the loading process. The processing time of a job j at a machine $i=\left\{1,2\right\}$ is denoted by $p_{ij}$ , which corresponds to the time for processing a cluster at the $M_1$ . The precedence constraints applied imply that to each job (truck) $j\in J^2$ is associated a nonempty set $S_j\subseteq J^1$ such that j can only be processed in M ₂ after all clusters belonging to $S_j$ have been processed in $M_1$ . Furthermore, we consider the delivery time $d_i$ for each job $j\in J^2$ . It corresponds to the time required to deliver the job $j\in J^2$ to its final client. The delivery time data refers to the time spent on the road. As a reference, the reader may consider that the delivery time is related to the time spent from Spain to another European country and those in North Africa.

So, the problem consists of finding a sequence of clusters in $J^1$ to be processed in $M_1$ and a sequence of the jobs in $J^2$ to be processed in $M_2$ to minimize the maximum date when a client receives its job. In other words, we aim to minimize $D_{\max }$ , which is equivalent to the latest time that one client receives its products.

To this aim, we propose a time-indexed model, which is based on a time-discretization of the planning horizon into a set $T=\left\{0,...,h\right\}$ of periods. Time-indexed formulations have been shown in the literature to be likely to provide better LP-relaxation bounds than other formulations for scheduling problems, see [4–6]. Continuing, we define two binary variables: $x_{jt}$ (resp. $y_{jt}$ ) assumes value 1 if a job $j\in J^1$ (resp. $j\in J^2$ ) starts its processing in $M_1$ (resp. $M_2$ ) in period $t\in T$ , and 0 otherwise. Also, the integer variable $D_{\max }$ , which is the maximum time when the last client receives its products. The integer linear programming (ILP) formulation proposed for that version of the ( $F2|prec,r_j,q_j|D_{\max }$ ) is presented as follows: $$\begin{array}{}\text{(1)}& \min D_{\max }\end{array}$$ $$\begin{array}{}\text{(2)}& \sum _{t=0}^{h-p_{1j}}{x}_{jt}=1\forall j\in J^1\end{array}$$ $$\begin{array}{}\text{(3)}& \sum _{t=0}^{h-p_{2j}}{y}_{jt}=1\forall j\in J^2\end{array}$$ $$\begin{array}{}\text{(4)}& \sum _{t=0}^{h-p_{2j}}t{y}_{jt}-\sum _{t=0}^{h-p_{1k}}\left(t+p_{1k}\right)x_{kt}\ge 0\forall j\in J^2,\forall k\in S_j\end{array}$$ $$\begin{array}{}\text{(5)}& \sum _{j\in J^1}\sum _{s=\max \left(0;t-p_{1j}+1\right)}^t{x}_{js}\le 1\forall t\in T\end{array}$$ $$\begin{array}{}\text{(6)}& \sum _{j\in J^2}\sum _{s=\max \left(0;t-p_{2j}+1\right)}^t{y}_{js}\le 1\forall t\in T\end{array}$$ $$\begin{array}{}\text{(7)}& D_{\max }\ge \sum _{t=0}^{h-p_{2j}}\left(t+p_{2j}+d_j\right)y_{jt}\forall j\in J^2\end{array}$$ $$\begin{array}{}\text{(8)}& x_{jt}\in \left\{0,1\right\}\forall j\in J^1,\forall t\in T,t\le h-p_{1j}\end{array}$$ $$\begin{array}{}\text{(9)}& y_{jt}\in \left\{0,1\right\}\forall j\in J^2,\forall t\in T,t\le h-p_{2j}\end{array}$$ $$\begin{array}{}\text{(10)}& D_{\max }\in Z^{+}\end{array}$$

The objective function (1) minimizes the time of reception of the last job, which is equivalent to the biggest value possible of ( $t+p_{2j}+d_j$ ) $y_{jt}$ . Constraints (2) (resp. (3)) state that each job $j\in J^1$ (resp. $j\in J^2$ ) has to be started exactly once at $M_1$ (resp. $M_2$ ). In other words, one job must not be processed more than once by either the machines. The precedence constraints (4) ensure that a job $j\in J^2$ cannot be processed at M2 before all jobs in $S_j$ have been completed at M1. Further explanation could be found in Figure 2. Constraints (5) (resp. (6)) state that machine $M_1$ (resp. $M_2$ ) can handle at most one job at any time period. Consequently, the $M_1$ and $M_2$ are not able to process more than one job at the same time. The $D_{\max }$ value is established by the constraints (7). As a result, the period a final product the client is bigger or equal to the sum of its processing time in $M_2\left(p_{2j}\right)$ , the delivery time ( $d_j$ ) from the manufacturer up to the client, and the period when it has been started to be processed in $M_2\left(t\right)$ . Lastly, constraints (8)–(10) define the domain of the variables.

[figure omitted; refer to PDF]

3. The Lagrangean Relaxation

The approach proposed to obtain lower and upper bounds for the ( $F2|prec,r_j,q_j|D_{\max }$ ) is based on applying a Lagrangean Relaxation (LR) procedure to the previous ILP model. The precedence constraints (4) that couple the scheduling on machines $M_2$ and $M_1$ are relaxed in the LR approach. Figure 2 illustrates a scheduling which is not feasible to constraints (4). In this example, job 1 ( $J_{11}$ ) processed by $M_1$ begins its processing at $t=0$ , so, $x_{10}=1$ , and job 2 ( $J_{21}$ ) processed by $M_1$ begins its processing at $t=1$ , so, $x_{21}=1$ . Considering $S_1=\left\{J_{11},J_{21}\right\}$ as the predecessors of job 1 ( $J_{12}$ ) processed by $M_2$ , it can only start its processing at $t=4$ . However, in this example, $J_{21}$ begins its processing at $t=3$ , $y_{13}=1$ , and not at $t=4$ as expected, violating the precedence constraints.

Let ${\lambda }_{jk}\ge 0$ , $j\in J^2$ , $k\in S_j$ , be the Lagrangean multipliers associated with constraints (4). The La- grangean multipliers are equivalent to the dual variables associated with each relaxed constraint placed in the objective function, see [3]. If a job is scheduled in $M_2$ before one of its predecessor has been completed, the objective function will be penalised in the Lagrangean subproblem $L\left(\lambda \right)$ as follows: $$\begin{array}{}\text{(11)}& L\left(\lambda \right)=\min D_{\max }+\sum _{j\in J^2}\sum _{k\in S_j}{\lambda }_{jk}\sum _{t=0}^{h-p_{1k}}\left(t+p_{1k}\right)x_{kt}-\sum _{t=0}^{h-p_{2j}}t{y}_{jt}\end{array}$$

s.t. (2), (3), (5)–(10).We use the subgradient algorithm to solve the Lagrangean dual $\max \left\{L\left(\lambda \right):\lambda \ge 0\right\}$ . The resulting model allows us to decompose the Lagrangean subproblem into one smaller subproblem $L{\left(\lambda \right)}_x$ in $M_1$ .

First, the subproblem $L{\left(\lambda \right)}_x$ is the total weighted completion time scheduling problem on one machine. The completion of a job $k\in J^1$ is weighted by the sum of penalties applied on all jobs to be scheduled on $M_2$ which have $k$ among their predecessors. Setting ${\omega }_k^1={\sum }_{j\in J^2:k\in S_j}{\lambda }_{jk},k\in J^1$ , subproblem $L{\left(\lambda \right)}_x$ is written as follows: $$\begin{array}{}\text{(12)}& L{\left(\lambda \right)}_x=\min \sum _{k\in J^1}{\omega }_k^1\sum _{t=0}^{h-p_{1k}}\left(t+p_{1k}\right)x_{kt}\end{array}$$

s.t. (2), (5), and (7). Subproblem $L{\left(\lambda \right)}_x$ can be solved by the weighted shortest processing time first rule, in which jobs are sorted in decreasing order of ${\omega }_k^1/p_{1k}$ . The proof is stated in [1]. So, we can infer an UB based on the jobs sequenced on the $M_1$ . It will allow us to calculate the release dates of the jobs on the $M_2$ . We will discuss the UB next.

In order to obtain a valid UB, let ${\overline{x}}_{kt}$ , $k\in J^1$ , $t\in T$ , be an optimal solution of subproblem $L{\left(\lambda \right)}_x$ for a given value of the Lagrangean multipliers. On the one hand, a schedule on $M_2$ such that the starting time $r_j$ of each job $j\in J^2$ satisfies $r_j\ge {\max }_{k\in S_j}\left\{{\sum }_{t=0}^{h-p_{1k}}\left(t+p_{1k}\right){\overline{x}}_{kt}\right\}$ is feasible and provides an upper bound for the ( $F2|prec,r_j,q_j|D_{\max }$ ) problem. On the other hand, the total weighted completion time scheduling problem on one machine with release dates is NP-Hard [7]. Thus, we propose a Lagrangean heuristic that consists of solving, for a given value of the Lagrangean multipliers, subproblem $L{\left(\lambda \right)}_x$ in $M_1$ , and then applying the approximation algorithm proposed by Philipps et al. [8] to the resulting problem with release dates in $M_2$ .

In the first step, the algorithm allows preemption to get an optimal schedule with the remaining weighted shortest processing time first rule. In the second step, jobs are nonpreemptively scheduled in the same order of their completion times. The algorithm produces, in $O\left(n\right)$ time, a nonpreemptive schedule increasing the total weighted completion time by at most a factor of 2 to a preemptive schedule.

Then, to complement the subgradient algorithm, we need to calculate a valid Lower Bound (LB) value. To do so, we aim to obtain the biggest possible LB value at each iteration of the subgradient algorithm. In this problem, a LB value may correspond to a relaxation of one of the constraints. In this sense, the constraints selected to be relaxed were the (6) ones. These constraints regard to the availability of the $M_2$ . In other words, it means that two or more jobs cannot be processed at the same time by the $M_2$ . Afterward, we need to compute a valid value of the $D_{\max }$ . The $D_{\max }$ can be evaluated as the biggest term of $\left(t+p_{2j}+d_j\right)y_{jt},j\in J^2$ . It is computed following a rule we introduce next.

In order to calculate the date a client will receive its products, we need first to assign a minimum release date $r_j$ value for each job $j\in J^2$ , which is defined as $r_j={\sum }_{k\in S_j}{p}_{1k}$ . Then, we add to that value the respective processing time in the $M_2$ ( $p_{2j}$ ). Next, we sum the delivery time required to deliver the products into the client’s location ( $d_j$ ). Afterward, we sort the computed values in decreasing order. As a result, we assign the biggest value found, to the $D_{\max }$ variable. Therefore, the reader may notice that it is equivalent to the relaxation of the constraints (6). In this sense, the value computed is a valid LB. The Figures 3 and 4 depict examples of valid UB and LB solutions, respectively.

[figure omitted; refer to PDF] [figure omitted; refer to PDF]

Therefore, we did not use the complete formulation of the subproblem $L\left(\lambda \right)$ (equation (11)) to execute the LR. We did not take into account the whole objective function of the Lagrangean dual to obtain the bounds. Instead, we considered the sequence calculated on M1. We took advantage of the LR and the subgradient method structures to obtain valid UB values, as explained before. Moreover, the LB values were computed following a greedy rule based on the three components: (i) the minimum release date regarding each job $j\in J^2$ , (ii) the processing time in the M2, and (iii) the delivery time. Afterward, both UB and LB values were introduced to the subgradient algorithm to pursue its convergence. In this sense, we may refer to our approach as an adaptation of the LR method. The Figure 5 illustrates the conditions to the method that achieves the optimality.

[figures omitted; refer to PDF]

As a result, the Langrangean Relaxation achieves an optimal solution whenever the computed UB and the LB values are the same. Consequently, it requires that both bounds converge to an equal value to obtain the optimal solution.

4. Computational Results

We report computational results on random instances, which are described as follows. The instances are divided into two groups: (i) short processing time jobs, and (ii) long processing time jobs. In the first (resp. second) group processing times are drawn from the uniform distribution between 1 and 10 (resp. 10 and 100). The number n of jobs in $J^1$ is set to 5, 10, 20, 40, and 60, and the number $m$ of jobs in $J^2$ is set to 0.6n, 0.8n, n, 1.2n, and 1.4n.

The set $S_j$ of predecessors of a job $j\in J^2$ is a random subset of $J^1$ with cardinality $\left|S_j\right|$ drawn from the uniform distribution between 1 and $n-1$ . In the Tables 1, 2, and 3, an instance is identified by $n-m-np-g$ , where np is the maximum number of predecessors a job in $J^2$ can have and $g$ is the group. Regarding the delivery times, the delivery time will be calculated in terms of the uniform distribution between 100 up to 1000 and from 1000 up to 5000 for elements of the group 1 and 2, respectively. The reader may interpret each slot of time as 10 minutes in the real world. Moreover, we believe this set of data represents quite well the processes studied and its variability, as well.

Table 1 summarizes the structure of the generated instances. The first column shows the group. The second and third columns show the possible values for the number of jobs in $J^1$ and $J^2$ , respectively. The fourth and the fifth columns show the uniform distribution intervals from which $\left|S_j\right|$ and the processing times are drawn, respectively. The sixth column refers to the time spent on the road to deliver the products to the final clients. The last column shows the identification, where one instance is generated for each value of $m$ in the second column.

Table 1

Summary of the instances structure.

Group	$n$	$m$	$\left|S_j\right|$	$p_j$	$d_j$	Identification
1	5	3-4-5-6-7	U(1, 4)	U(1, 10)	U(102, 103)	5− $m$ − 4− 1
	10	6-8-10-12-14	U(1, 9)	U(1, 10)	U(102, 103)	10− $m$ − 9−1
	20	12-16-20-24-28	U(1, 19)	U(1, 10)	U(102, 103)	20− $m$ −19−1
	40	24-32-40-48-56	U(1, 39)	U(1, 10)	U(102, 103)	40− $m$ −39−1
	60	36-48-60-72-84	U(1, 59)	U(1, 10)	U(102, 103)	60− $m$ −59−1
2	5	3-4-5-6-7	U(1, 4)	U(10, 102)	U(103, 5000)	5− $m$ −4−2
	10	6-8-10-12-14	U(1, 9)	U(10, 102)	U(103, 5000)	10− $m$ −9−2
	20	12-16-20-24-28	U(1, 19)	U(10, 102)	U(103, 5000)	20− $m$ −19−2
	40	24-32-40-48-56	U(1, 39)	U(10, 102)	U(103, 5000)	40− $m$ −39−2
	60	36-48-60-72-84	U(1, 59)	U(10, 102)	U(103, 5000)	60− $m$ −59−2

The experiments were carried out on the Operational System CentOS 7.x x86_64 with 27 compute nodes, 720 cores and 7.4 TB of RAM as the maximum capacity. We highlight that we applied only one node to proceed with the calculations. As a result, we did not use any parallel approach. Moreover, the programming languages C and C++ were used with compiler GNU GCC, and CPLEX 12.6.8. was used to solve the ILP models.

We first report the results obtained when trying to solve the ILP model running CPLEX with a time limit of 7,200 seconds. Table 2 shows results for the instances which CPLEX obtained lower and upper bounds within the time limit. Moreover, we introduced the same metrics for the Lagrangean Relaxation applied for the same instances. The results from instance group 1 are presented from the first to the ninth columns and for instance group 2 from the tenth to the eighteenth columns. For each group, we present the instance identification, the final upper (UB) and lower (LB) bounds obtained within the time limit, the percentage gap, and the time in seconds. The linear relaxation bounds are presented in the subsequent tables, along with results for the LR, as well. The percentage gap is computed as $\left(UB-LB\right)/UB$ . The dash symbol “-”in the tables means that a method did not finish within the time limit.

Table 2

Results for the ILP model running CPLEX with a time limit of 7,200 seconds. the GAP is defined as $\left(UB-LB/UB\right)$ . Results depicted for the groups of instances 1 and 2. The bolded LB and UB values represent an instance’s optimal solution.

Group 1 instances										Group 2 instances
Instance		Integer model CPLEX				Lagrangean Relaxation				Instance	Integer model CPLEX				Lagrangean Relaxation
		LB	UB	GAP (%)	Time (sec)	LB	UB	GAP (%)	Time (sec)		LB	UB	GAP (%)	Time (sec)	LB	UB	GAP (%)	Time (sec)
5-3-4-1	794		794	0	0	794	799	1	0	5-3-4-2	4,630	4,630	0	1	4,630	4,660	1	0
5-4-4-1	671		671	0	0	671	671	0	0	5-4-4-2	3,222	3,222	0	12	3,222	3,222	0	0
5-5-4-1	842		842	0	0	842	852	1	0	5-5-4-2	3,222	3,222	0	26	3,222	3,305	2	0
5-6-4-1	801		801	0	0	801	812	1	0	5-6-4-2	4,855	4,855	0	26	4,840	4,959	3	0
5-7-4-1	901		901	0	0	901	905	1	0	5-7-4-2	4,954	4,954	0	21	4,954	5,090	3	0
10-6-9-1	939		939	0	1	939	955	2	0	10-6-9-2	5,271	5,272	0.001	7,200	5,221	5,317	2	0
10-8-9-1	983		983	0	5	983	989	1	0	10-8-9-2	4,289	4,289	0	52	4,289	4,289	0	0
10-10-9-1	1,002		1,002	0	10	996	1,024	3	0	10-10-9-2	5,080	5,080	0	3,138	5,080	5,123	1	0
10-12-9-1	1,001		1,001	0	2	1,001	1,013	1	0	10-12-9-2	4,802	4,802	0	70	4,802	4,865	1	0
10-14-9-1	906		906	0	0	906	916	1	0	10-14-9-2	5,151	5,151	0	157	5,151	5,220	2	0
20-12-19-1	926		926	0	28	926	953	3	0	20-12-19-2	5,398	6,124	12	7,200	5,921	6,003	1	1
20-16-19-1	962		962	0	24	954	984	3	0	20-16-19-2	5,248	5,824	10	7,200	5,697	5,963	4	1
20-20-19-1	1,048		1,048	0	43	1,048	1,125	7	0	20-20-19-2	5,394	5,726	6	7,200	5,726	6,124	6	2
20-24-19-1	1,082		1,082	0	51	1,082	1,096	1	0	20-24-19-2	5,313	7,033	24	7,200	5,581	6,201	1	2
20-28-19-1	1,100		1,100	0	189	1,100	1,167	6	0	20-28-19-2	5,647	7,328	23	7,200	6,067	6,617	8	3
40-24-39-1	1,012		1,012	0	2,332	1,006	1,085	7	0	40-24-39-2	5,928	7,941	25	7,200	6,281	7,296	14	6
40-32-39-1	1,096		1,159	5	7,200	1,144	1,266	10	0	40-32-39-2	-	-	-	7,200	6,025	7,132	15	7
40-40-39-1	1,084		1,128	4	7,200	1,092	1,260	13	1	40-40-39-2	-	-	-	7,200	7,296	7,989	9	12
40-48-39-1	1,074		1,146	6	7,200	1,116	1,251	10	1	40-48-39-2	-	-	-	7,200	6,562	8,227	20	15
40-56-39-1	1,051		1,126	7	7,200	1,069	1,155	7	2	40-56-39-2	-	-	-	7,200	7,111	7,976	11	17
60-36-59-1	1,184		1,288	8	7,200	1,233	1,324	7	2	60-36-59-2	-	-	-	7,200	7,349	8,144	10	16
60-48-59-1	1,160		1,505	23	7,200	1,225	1,259	3	3	60-48-59-2	-	-	-	7,200	8,101	9,839	18	34
60-60-59-1	1,194		1,580	24	7,200	1,268	1,381	8	4	60-60-59-2	-	-	-	7,200	7,572	9,609	21	43
60-72-59-1	1,195		1,618	26	7,200	1,289	1,442	10	5	60-72-59-2	-	-	-	7,200	7,150	9,905	28	45
60-84-59-1	1,118		1,100,843	99	7,200	1,283	1,502	14	7	60-84-59-2	-	-	-	7,200	7,388	10,302	28	61

Regarding the results, the mathematical model is able to obtain the optimal solution for 16 instances of group 1 and only 9 instances for group 2. Furthermore, the CPLEX was not able to provide neither a feasible UB nor a LB for the most complicated instances of the Group 2. In contrast, the LR was able to compute valid bounds for all instances. Indeed, the LB values were verified to be the same as the optimal solutions in 21 opportunities. Moreover, the GAP values were smaller than 3% in 20 opportunities. To conclude, the maximum time spent by the LR to complete the method was 61 seconds and it was observed for the most complicated instance.

Moreover, we present two figures that illustrate the application of the subgradient algorithm when solving the Lagrangean Subproblem. The first figure represents a scenario that the optimal solution was achieved and the other figure represents a scenario that the convergence was not achieved, Figures 6 and 7, respectively.

[figure omitted; refer to PDF] [figure omitted; refer to PDF]

Then, we report the results obtained with the linear relaxation of the ILP model. Also, we present the results based on the proposed LR. The time limit was set as 7,200 seconds for both experiments.

Table 3 shows the results for instance of the groups 1 and 2. Results obtained with Linear relaxation are shown from the second to the third columns and from the eighth to the nineth columns. Moreover, the LR results are shown from the fourth to the sixth columns and from tenth to the twelfth columns. The first column presents the instance, the second column the linear relaxation solution, and the third column presents the computational time in seconds. Then, we present the LR lower bound in the next column, followed by the variance between both lower bounds found, and finally the computational time in the LR in seconds. Afterward, the same structure repeats for instances of the Group 2. The dash symbol ‘-’ in the tables means that a method did not finish within the time limit.

Table 3

Results obtained with the linear relaxation and the LR on instances of groups 1 and 2. The LB ^∗values refer to the lower bounds provided by the Lagrangean Relaxation. Likewise, LB values refer to the lower bounds computed by the linear relaxation.

Group 1 instances						Group 2 instances
Instance	Linear relaxation		Lagrangean Relaxation			Instance	Linear relaxation		Lagrangean Relaxation
	LB	Time (sec)	LB ∗	(LB ∗/LB)	Time (sec)		LB	Time (sec)	LB ∗	(LB ∗/LB)	Time (sec)
5-3-4-1	788	0	794	1%	0	5-3-4-2	4,620	0	4,630	0%	0
5-4-4-1	666	0	671	1%	0	5-4-4-2	3,139	0	3,322	6%	0
5-5-4-1	840	0	842	0%	0	5-5-4-2	3,144	0	3,322	6%	0
5-6-4-1	795	0	801	1%	0	5-6-4-2	4,824	0	4,840	0%	0
5-7-4-1	895	0	901	1%	0	5-7-4-2	4,903	4	4,954	1%	0
10-6-9-1	932	0	939	1%	0	10-6-9-2	5,092	9	5,221	3%	0
10-8-9-1	966	0	983	2%	0	10-8-9-2	4,228	7	4,289	1%	0
10-10-9-1	985	0	996	1%	0	10-10-9-2	4,815	25	5,080	6%	0
10-12-9-1	995	0	1,001	1%	0	10-12-9-2	4,777	1	4,802	1%	0
10-14-9-1	905	0	906	0%	0	10-14-9-2	5,028	36	5,151	2%	0
20-12-19-1	909	1	926	2%	0	20-12-19-2	5,394	60	5,921	10%	1
20-16-19-1	941	2	954	1%	0	20-16-19-2	5,247	100	5,697	9%	1
20-20-19-1	1,009	4	1,048	4%	0	20-20-19-2	5,393	97	5,726	6%	2
20-24-19-1	1,044	6	1,082	4%	0	20-24-19-2	5,300	207	5,581	5%	2
20-28-19-1	1,046	5	1,100	5%	0	20-28-19-2	5,646	229	6,067	7%	3
40-24-39-1	978	10	1,006	1%	0	40-24-39-2	5,927	231	6,281	6%	6
40-32-39-1	1,066	10	1,144	7%	0	40-32-39-2	5,940	332	6,025	1%	7
40-40-39-1	1,060	15	1,092	3%	1	40-40-39-2	6,211	596	7,729	24%	12
40-48-39-1	1,064	15	1,116	5%	1	40-48-39-2	6,067	719	6,562	8%	15
40-56-39-1	1,045	26	1,069	2%	2	40-56-39-2	6,181	760	7,111	15%	17
60-36-59-1	1,135	28	1,233	9%	2	60-36-59-2	6,546	724	7,349	12%	16
60-48-59-1	1,118	40	1,225	10%	3	60-48-59-2	-	7,200	8,810	-%	34
60-60-59-1	1,173	75	1,268	8%	4	60-60-59-2	-	7,200	7,757	-%	43
60-72-59-1	1,174	100	1,289	10%	5	60-72-59-2	-	7,200	7,715	-%	45
60-84-59-1	1,162	112	1,283	10%	7	60-84-59-2	-	7,200	7,738	-%	61

For both groups of instances, the results show a common pattern. The LR provided either equal or better LB result than linear relaxation for all out of the 50 instances. Also, the CPLEX was not able to compute a valid LB for the most complicated set of instances. As a result, LR outperformed the linear relaxation for all out of 46 instances. Furthermore, the LR provided valid LB for the four most complicated instances. The linear relaxation was not able to compute valid LB for those instances within 7,200 seconds computing time.

As previously mentioned, instances of group 2 were generated with longer processing times than those of group 1, c.f., Table 1. As a result, those instances present a much larger time- horizon, increasing the number of variables drastically. This fact has a significant impact on the performance of the methods.

5. Conclusions

In this work, we considered a two-machine flow shop scheduling problem with precedence constraints, release dates and delivery time. Moreover, the problem’s objective is minimizing the time a client receives the last job. This problem is the usual case for many manufacturers’ production procedures, which must check each product as soon as it is done. By doing so, the company avoids sending poor-quality products to the final client.

We also propose an adaptation of the Lagrangean Relaxation (LR) approach, which presented the best overall results. On the one hand, the LR has obtained the optimal solution only in 3 cases out of 50. On the other hand, the LR outperformed the CPLEX for the most complicated instances. The LR was able to compute feasible solutions for all instances within 61 seconds of computing time. Even though the ILP provided the optimal solution for 26 instances, those optimal solutions were achieved only for the easier instances.

Therefore, the work presents an alternative way for companies that must schedule its activities in a flow shop fashion. Besides, the activities described in that work may be adapted for a range of others scenarios. As a result, the methodology presented is a contribution to the companies that must schedule their processes, in particular in the outbound area.

As future works, we consider developing a metaheuristic to provide better UB and LB in order to achieve better solutions for the large instances.

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Acknowledgments

This work has been partially supported by Doctorats Industrials, Agéncia de Gestió d’Ajuts Universitaria I de Recerca, Generalitat de Catalunya [2016 DI 022] (Marcelus Fabri), the Spanish Ministry of Economy and Competitiveness [TRA2013-48180-C3-2-P] (Helena Ramalhinho), and CAPES, CNPq, and FAPEMIG, Brazil (Martín Gómez Ravetti, Mauricio C. de Souza).

References

[1] M. L. Pinedo, "Scheduling: theory, algorithms, and systems," Operations Research Proceedings 1991, pp. 35-42, DOI: 10.1007/978-3-642-46773-8_5, 2016.

[2] H. Ramalhinho, "Sevast’yanov’s algorithm for the flow-shop scheduling problem," European Journal of Operational Research, vol. 91 no. 1, pp. 176-189, DOI: 10.1016/0377-2217(94)00356-4, 1996.

[3] F. Vanderbeck, L. A. Wolsey, "Reformulation and decomposition of integer programs," 50 Years of Integer Programming 1958–2008, pp. 431-502, DOI: 10.1007/978-3-540-68279-0_13, 2010.

[4] P. M. Cota, B. M. R. Gimenez, D. P. M. Araújo, T. H. Nogueira, M. C. de Souza, M. G. Ravetti, "Time-indexed formulation and polynomial time heuristic for a multi-dock truck scheduling problem in a cross-docking centre," Computers and Industrial Engineering, vol. 95, pp. 135-143, DOI: 10.1016/j.cie.2016.03.001, 2016.

[5] J. P. Sousa, L. A. Wolsey, "A time indexed formulation of non-preemptive single machine scheduling problems," Mathematical Programming, vol. 54 no. 1–3, pp. 353-367, DOI: 10.1007/bf01586059, 1992.

[6] J. M. Van Den Akker, C. A. J. Hurkens, M. W. P. Savelsbergh, "Time-indexed formulations for machine scheduling problems: column generation," Informs Journal on Computing, vol. 12 no. 2, pp. 111-124, DOI: 10.1287/ijoc.12.2.111.11896, 2000.

[7] J. K. Lenstra, A. H. G. Rinnooy Kan, P. Brucker, "Complexity of machine scheduling problems," Annals of Discrete Mathematics, vol. 1, pp. 343-362, DOI: 10.1016/S0167-5060(08)70743-X, 1977.

[8] C. Phillips, C. Stein, J. Wein, "Minimizing average completion time in the presence of release dates," Mathematical Programming, vol. 82 no. 1–2, pp. 199-223, DOI: 10.1007/BF01585872, 1998.