Computer Systems Science & Engineering DOI:10.32604/csse.2023.022716
Article

Hybrid Flow Shop with Setup Times Scheduling Problem

Mahdi Jemmali1,2,3,* and Lotfi Hidri4

1Department of Computer Science and Information, College of Science at Zulfi, Majmaah University, Majmaah, 11952, Saudi Arabia
2Mars Laboratory, University of Sousse, Sousse, Tunisia
3Department of Computer Science, Higher Institute of Computer Science and Mathematics of Monastir, Monastir University, Monastir, 5000, Tunisia
4Industrial Engineering Department, College of Engineering, King Saud University, Riyadh, 11421, Saudi Arabia
*Corresponding Author: Mahdi Jemmali. Email: m.jemmali@mu.edu.sa
Received: 16 August 2021; Accepted: 17 September 2021

Abstract: The two-stage hybrid flow shop problem under setup times is addressed in this paper. This problem is NP-Hard. on the other hand, the studied problem is modeling different real-life applications especially in manufacturing and high performance-computing. Tackling this kind of problem requires the development of adapted algorithms. In this context, a metaheuristic using the genetic algorithm and three heuristics are proposed in this paper. These approximate solutions are using the optimal solution of the parallel machines under release and delivery times. Indeed, these solutions are iterative procedures focusing each time on a particular stage where a parallel machines problem is called to be solved. The general solution is then a concatenation of all the solutions in each stage. In addition, three lower bounds based on the relaxation method are provided. These lower bounds present a means to evaluate the efficiency of the developed algorithms throughout the measurement of the relative gap. An experimental result is discussed to evaluate the performance of the developed algorithms. In total, 8960 instances are implemented and tested to show the results given by the proposed lower bounds and heuristics. Several indicators are given to compare between algorithms. The results illustrated in this paper show the performance of the developed algorithms in terms of gap and running time.

Keywords: Hybrid flow shop; genetic algorithm; setup times; heuristics; lower bound

1  Introduction

The hybrid flow shop problems (HFSP) are commonly utilized in several sectors like the manufacturing area. Indeed, HFSP is modeling several production systems in different industries such as paper, electronics, cars, chemicals, and semiconductors [1–4].

The two-stage HFSP is a particular case, which is well studied in the literature. This is due to its practical applications, and its theoretical challenging aspect. Plenty of results are provided to solve this problem using heuristics, meta-heuristics, and exact methods. Authors in [5] proposed an efficient exact method to solve the two-stage HFSP. The latter research doesn't achieve the setup times constraint and the time provided to solve the problem is remarkable. The Two-stage HFSP with transportation times is addressed in [6]. In the latter work, several heuristics and exact methods are developed. In the experimental results, it is clear the luck of the big scale class to show the performance of the developed method when the number of jobs is real big. The two-stage HFSP with availability constraint is addressed in [7], and an exact algorithm is proposed. In the latter paper, there is only one machine in stage 1. In addition, only one interval of maintenance for each machine. Authors in [8] solved the problem using a genetic algorithm (GA). Several constructive heuristics are developed in the latter work to apply the genetic algorithm seeking the enhancement of the results. The luck of the development of lower bounds to be used as a measurement of the real performance of the heuristics is remarkable for the latter work.

In [9], the authors proposed an exact solution for the hybrid flow shop under sequence-dependent setup time for stage one. An upper bound utilized Hungarian method is proposed. In addition, the authors proposed three heuristics. The experimental results need to be performed when the author gives more attention to the big scale instances.

The problem with batch processing machines is studied in [10], where a decomposition approach with variable neighborhood search (VNS) is developed. Unequal ready times for jobs are considered a constraint for the latter problem. This problem with parallel dedicated machines is addressed in [11], and several heuristics are proposed. The objective was the minimization of the total completion time. Besides, the number of machines is limited to one for stage 1 and two for stage 2. Only two heuristics are developed in the later work.

In [12] authors proposed an approximate solution based on a Branch and Bound exact procedure to tackle the problem of two-stage hybrid flow with dedicated machines. Besides, the authors proposed four constructive heuristics to solve the problem and three dominance priorities. In the experimental results, the instances are generated with a maximum of 100 jobs.

In [13] a new application of the problem of two-stage HFSP is introduced and a heuristic with a local search method is developed and an ant colony optimization algorithm is developed. The bi objectives in the latter search are the total energy consumption and the makespan.

Authors in [14] addressed the problem and proposed a mutant firefly algorithm. Two objectives functions are proposed in the latter work. One of the objectives is the simultaneous ratio for the coming of several parts of products at the stage of assembly. The second objective is the on-time delivery ratio related to the products delivery assignment.

In [15] authors investigated the hybrid flow shop problem (DHFSP) under sequence-dependent setup times. Three sub-problems are involved. The first sub-problem is the allocation of factories for each job. The next sub-problem is to find the job sequence for every factory. The third sub-problem is the allocation of each job at each stage. To test the performance of the proposed solutions authors generated 780 benchmarks in total. In the same context authors in [16], a novel simulated-annealing (NSA) algorithm was proposed to find a reasonable manufacturing assignment in a good running time. Setup times are needed when switching between jobs. Considering the setup times while preparing the schedules of jobs on the machines allows having accurate production planning. To minimize the gap between theoretical points and real-life situations, the setup times are not neglected in this study. The two-stage HFSP with setup times is treated in literature [17–20].

In this study, the two-stage hybrid flow shop problem is addressed. Novel heuristics are proposed. These heuristics are based on the exact solution of the problem of the parallel machine under release and delivery times constraints. In addition, a lower bound allowing the assessment of the performance of heuristics are proposed. The studied problem is an NP-hard problem. It is very important to search for heuristics that give approximate solutions to the problem with acceptable time. In addition, the scale of the problem can impact the performance of the heuristics on time and gap. In this paper, a total of 8960 instances are generated and tested to prove the efficiency of the proposed lower bounds and heuristics. In the literature review, there is a lack of treatment of the big scale of instances to solve the problem. Indeed, the number of jobs reaching 200. The proposed heuristics give a solution easily for the big scale of instances with a satisfying time and gap.

The rest of this paper is structured as follows. Problem presentation is presented in Section 2. The lower bounds are developed and displayed in Section 3. The detailed heuristics are given in Section 4. An experimental study and discussion of results are reported in Section 5. Finally, the summarization of the studied work is presented in the conclusion with future lines.

2  Problem Definition and Proprieties

In this section, the presentation of the problem and its relevant proprieties are presented. In addition, the problem of the parallel machine under release and delivery times constraints as well as some of its characteristics are recalled. This is because of the important role of the latter problem in providing algorithms for the current studied problem. The two-stage hybrid flow shop problem with setup times is stated as follows. We are given a shop composed of two stages C1 and C2 in series, containing m1 and m2 identical parallel machines, respectively. A set J = {1, 2, …, n} of n jobs have to be executed on the machines of the two stages in the following way. A machine of C1 is prepared during a setup time s1,j to be ready for processing a job j during p1, j. After completion the stage 1, an available machine in the second stage C2 is prepared during s2, j to process the job j. All machines and jobs are ready for executing at the first time 0. Preemption is not permitted, and all job characteristics s1, j , s2, j, p1, j, and p2, j are deterministic and integral. The objective of the optimization problem is the minimization of the makespan. According to the three fields notation [21] the studied problem is denoted by Fm|s1, j, s2, j|Cmax .

Example 1:

Let m1 = 2 and m2 = 2. The setup times and processing times for the two stages illustrates in Tab. 1. Fig. 1 presents a feasible solution for example 1, where the makespan is Cmax = 142.

Figure 1: Feasible solution for example 1 p2, j

It is remarkable to note that the setup times in stage 1 are connected directly to the processing times, while in stage 2, the setup time might be separated from the processing time, as for job 8. Indeed, for this job c1,8 = 22 which is a release date in the second stage and the setup time is s2,8 = 17 < 22.

3  Lower Bounds

In this section, we present three new lower bounds based on the linear relaxation technique. The first one is obtained after applying the relaxation of the second stage using the problem of the parallel machine. The second lower bound is obtained after applying the relaxation of the first stage using the problem of the parallel machine. The third lower bound is an enhancement of the first one.

3.1 Relaxed Second Stage Based Parallel Machine Problem (LB1)

The capacity of the second stage is relaxed and the number of machines m2 is supposed to be not finite. In this case, an ending processing job in stage 1 has no time to wait for processing in the second stage. Consequently, the obtained scheduling problem in stage 1 is a parallel machines problem under release date rj and delivery time qj denoted Pm|rj, qj|Cmax where:

▪     rj=s1, j∀j∈J.

▪     pj=p1, j∀j∈J.

▪     qj=p2, j∀j∈J.

▪    m = m1.

Lemma: Any lower bound of the latter defined problem, is a valid lower bound for Fm|s1, j,s2, j|Cmax .

Proof: Pm|rj,qj|Cmax is obtained after a relaxation of the current problem. Therefore, the optimal values Cmax∗ is a lower bound of the studied problem. Clearly, if LB is a lower bound of Pm|rj,qj|Cmax then it is also a valid lower bound for Fm|s1, j,s2, j|Cmax .

Remark: The Branch & Bound (B&B) algorithm for Pm|rj,qj|Cmax presented in [22] is used to obtained the optimal solution. This exact solution is a valid lower bound for the studied problem. Since the Pm|rj,qj|Cmax is NP-Hard, the B&B might fail to obtain the exact solution within a limit time LT (In this study the limit time LT is set to 100 s), in this situation the best returned lower bound value while calling the B&B is a valid lower bound for Fm|s1, j,s2, j|Cmax . This remark is valid for the subsequent other lower bounds. The obtained lower bound in this subsection is denoted LB1.

3.2 Relaxed First Stage Based Parallel Machine Problem (LB2)

The capacity of the first stage is relaxed and the number of machines m1 is supposed to be not finite. In this case, for any job a machine is set up at zero time and processes without delay in the first stage. Consequently, the obtained scheduling problem in the second stage is a parallel machine under rj and qj constraints denoted by Pm|rj,qj|Cmax where:

▪     rj= max(s1, j+p1, j,s2, j)∀j∈J.

▪     pj=p2, j∀j∈J.

▪     qj=0∀j∈J.

▪    m = m2.

Following the same steps as for LB1, the Branch & Bound (B&B) algorithm of Pm|rj,qj|Cmax presented in [22] is used to obtain the optimal solution, and therefore the second lower bound denoted LB2.

3.3 Enhanced Relaxed Second Stage Based Parallel Machine Problem (LB3)

The capacity of the second stage is relaxed and the number of machines m2 is supposed to be infinite. In this case, an ending processing job in stage 1 has no time to wait for processing in the second stage. Consequently, the obtained scheduling problem in stage 1 is parallel machines problem under rj and qj constraints denoted by Pm|rj,qj|Cmax where:

▪     rj=0∀j∈J.

▪     pj=s1, j+p1, j∀j∈J.

▪     qj=p2, j∀j∈J.

▪    m = m1.

In the same way, and applying the B&B algorithm a third lower bound denoted LB3 is obtained.

Remark: LB3 dominates LB1.

Proof: Clearly, an optimal solution of problem (P1) Pm|rj,qj|Cmax with rj = 0, pj = s1,j + p1,j , and qj = p2,j is a feasible solution for the problem (P2) Pm|rj,qj|Cmax with rj = s1,j, pj = p1,j, and qj = p2,j. Therefore, any lower LB1bound for problem (P2) is dominated by LB3.

Example 2:

In this example, we give the schedule applying LB3 with the same instance presented in Example 1. Now, we solve exactly the Pm|rj,qj|Cmax with rj, pj, and qj values presented in Tab. 2.

The optimal solution of Pm|rj,qj|Cmax for the first stage assign on machine 1 the jobs {4, 10, 6, 7} and on machine 2 the jobs { 8, 9, 3, 5, 1, 2}. The optimal solution of Pm|rj,qj|Cmax constitute the lower bound of the studied problem and illustrated in Fig. 2. Fig. 2 shows that the value of LB3 is equal to 91.

Figure 2: Schedule applying LB3

4  Heuristics

In this section, a metaheuristic and three heuristics are proposed. The developed metaheuristic is implemented using the genetic algorithm (GA). The three other heuristics are based on solving a parallel machines problem under release and delivery time constraints.

4.1 Genetic Algorithm (H1)

John Holland in [23] presented for the first time the genetic algorithms (GAs). The GAs are inspired by natural evolution. Indeed, the main fundamentals of natural evolution in a given environment are memetic. During this process, the chromosomes are the main actors in which all the messages and mutations are performed. The different components are:

1.    Chromosome Representation: in this study, a chromosome represents a feasible solution. A chromosome is constituted by a permutation of jobs. The jobs in this permutation are scheduled on the machines of stage 1 according to the most available machine rule. That is, the first remaining job in the permutation is allocated to the most available machine. Once all the jobs are scheduled to stage 1, the jobs are scheduled on the second stage according to the non-decreasing order of their completion time in the first stage.

2.    Initial population: All the individuals in the initial population are arbitrarily generated, except one solution which is generated according to the LPT rule in the first stage. The jobs are sorted according to the non-increasing order of their processing time in the first stage. Once these jobs are assigned to stage 1 according to the LPT rule, they are scheduled in the second stage according to the increasing order of their completion time in the first stage.

3.    Selection Operator: During the selection phase an operator acts to pick the most suitable solutions in order to accelerate the convergence toward the global optimum. Several operators are utilized and the most used one is the roulette wheel selection rule, which is an adopted selection operator in this study.

4.    Reproduction: In this step, an individual passes to the next generation without modification, it is a cloning phase. The main objective of the reproduction phase is to preserve the individuals with high fitness from the actual generation to the next one.

5.    The Operator of Crossover: Enriching the diversity of the population is the main objective of the crossover operation. Indeed, in this step, the structure of the individuals (chromosomes) is manipulated. Conventionally, the crossover operator considers two parents and generates two children. To guarantee the innovation (even partially) of the children a crossbreeding is performed. The basic idea is that two successful parents will yield better children. The crossover rate pc(pc∈[0,1]) constitutes the proportion of parents on which a crossover operator will act. The position-based crossover operator (POX) is adopted in this strategy.

6.    Mutation: The main goal of the mutation is to create a small randomness element in the population of individuals. The mutation operator could increase or decrease the space of the possible feasible solutions, in addition to the variability of the individuals. pm determines the probability of mutating each element (gene) of representation. In this work, the adopted pm is to mutate a percentage of all genes.

7.    Replacement Strategies: In this step, individuals are withdrawn following a given selection strategy. Indeed, the best individuals from parents and offspring are kept. This approach allows a rapid convergence and some time to a moderate solution. In order to avoid such a situation, sometimes, bad (fitness) individuals are selected. Those replacement strategies can be deterministic or stochastic.

In practice, the tuple (Population, crossover rate, probability of mutating) considered in the genetic algorithm are chosen as following: (200;0.9;0.9), (200;0.8;0.9), (200;0.9;0.8), (200;0.7;0.9), (200;0.8;0.8), (200;0.6;0.9), (200;0.7;0.8), (200;0.6; 0.8), (200;0.5;0.9), and (200;0.4;0.9).

4.2 Heuristic H2

The heuristic H2 is based on solving optimally a sequence of two parallel machines under release and delivery time constraints. First, a parallel machines problem Pm|rj,qj|Cmax is solved in the first stage. The parameters of this parallel machine are:

▪     rj=0∀j∈J.

▪     pj=s1, j+p1, j∀j∈J.

▪     qj=p2, j∀j∈J.

▪    m = m1.

Once the above scheduling problem ( Pm|rj,qj|Cmax ) is solved and an optimal solution is obtained, the completion time of j ∈ J is denoted c1,j. Second, in stage 2, a parallel machines problem Pm|rj,qj|Cmax is optimally solved. The characteristics of the latter problem are:

▪     rj=max(c1, j,s2, j)∀j∈J.

▪     pj=p2, j∀j∈J.

▪     qj=0∀j∈J.

▪    m = m2.

In the third step, we remark that the obtained solution is not necessarily a feasible one since it may occur that a job has no setup time in the second stage. To overcome this drawback, an adjusted solution is introduced. The adjustment is as follows. If the first scheduled job in a machine of the second stage is the job j, then we have to check two cases:

1)   if s2,j ≥ c1,j then the completion time of j is c2,j = s2,j + p2,j.

2)   if s2,j < c1,j then the completion time of j is c2,j = c1,j + p2,j. If a job j is preceded by a job i in the same machine then:

1)   if c2,i + s2,j ≥ c1,j then the completion time of j is c2,j = c2,i + s2,j + p2,j.

2)   if c2,i + s2,j < c1,j then the completion time of j is c2,j = c1,j + p2,j.

The concatenation of the two feasible solutions respectively in the first and second stages provides a feasible solution for t Fm|s1, j,s2, j|Cmax .

Example 3:

We adopt the same instance represented in Tab. 1 in Example 1. In the first stage, we apply Pm|rj,qj|Cmax , and the exact solution is the same that described in Fig. 2. From this optimal solution, we determine all c1,j values and we represent rj, qj and pj to solve the second optimal problem applied on the second stage in Tab. 3.

The optimal solution of Pm|rj,qj|Cmax for the second stage with instance given in Tab. 3 assign jobs {4, 10, 6, 5, 7} on machine 1 and {8, 9, 3, 1, 2} on machine 2. Fig. 3 represents the related schedule. Fig. 3 displays a feasible schedule in the second stage as a result of the heuristic H2.

Figure 3: Feasible schedule for H2

4.3 Heuristic H3

The heuristic H3 is based on solving optimally a sequence of two parallel machines under release date and delivery time. First, a parallel machine scheduling problem Pm|rj,qj|Cmax is solved in the first stage. The parameters of this parallel machine are:

▪     rj=0∀j∈J.

▪     pj=s1, j+p1, j∀j∈J.

▪     qj=p2, j∀j∈J.

▪    m = m1.

Once the above scheduling problem ( Pm|rj,qj|Cmax ) is solved and an exact solution is returned, the completion time of a job j ∈ J is denoted c1,j. Second, in the second stage, a parallel machine scheduling problem Pm|rj,qj|Cmax is optimally solved. The characteristics of the latter problem are:

▪     rj=c1, j∀j∈J.

▪     pj=p2, j∀j∈J.

▪     qj=0∀j∈J.

▪    m = m2.

The obtained solution in the second stage does not include setup times. In this step, the setup times s2,j are embedded before the processing of jobs. The concatenation of the two feasible solutions respectively in the first and second stages provides a feasible solution for the studied problem.

4.4 Heuristic H4

The heuristic H4 is based on solving optimally a sequence of two parallel machines under release and delivery time constraints. First, a parallel machine scheduling problem Pm|rj,qj|Cmax is solved in the first stage. The parameters of this parallel machine are:

▪     rj=0∀j∈J.

▪     pj=s1, j+p1, j∀j∈J.

▪     qj=p2, j∀j∈J.

▪    m = m1.

Once the above scheduling problem ( Pm|rj,qj|Cmax ) is solved and an optimal solution is obtained, the completion time of a job j ∈ J is denoted c1,j. Second, in the second stage, a parallel machine scheduling problem Pm|rj,qj|Cmax is optimally solved. The characteristics of the latter problem are:

▪     rj=c1, j∀j∈J.

▪     pj=s2, j+p2, j∀j∈J.

▪     qj=0∀j∈J.

▪    m = m2.

In the expression of the processing times pj = s2,j + p2,j we consider the setup time and the processing time as one entity. This will give a feasible solution in the second stage which may largely exceed an optimal solution. To readjust the obtained solution, we split setup time from processing time, and we apply the following recursive rule in the jobs scheduled to the same machine. c2,j = max(c1,j, c2,j−1 + s2,j) where c2,j−1 is the completion time of the predecessor of job j in the same machine. The concatenation of the two feasible solutions respectively in the first and second stages provides a feasible solution for Fm|s1, j,s2, j|Cmax .

5  Computational Results

This section focuses on the illustration and the discussion of the obtained results. All proposed algorithms in this paper were coded in C++. All coded programs were executed by a workstation that has the following characteristics: Intel(R) Xeon(R) CPU E5-2687W v4 @ 3.00 GHz and 64 GB RAM.

5.1 Test Problems

The generation of the setup times and processing times are applied according to the uniform distribution denoted by U[st, fi]. In this paper the choice of st = 1 and fi = {20, 40}. The class of instance is depending on the choice of the generation of s1, j, p1, j, s2, j and p2, j. So, we generate s1, j in [1, 20] or [1, 40], and same thing for p1,j, s2,j and p2,j. We denoted by C1, C2, C3, and C4 the choice of fi to generate s1, j, p1, j, s2, j and p2, j, respectively. The value of each variable C1, C2, C3, and C4 represent the manner that the setup times and processing times are generated. For example, if (C1 = 20, C2 = 20, C3 = 40, C4 = 20) meaning that we generate s1,j in [1, 20], p1,j in [1, 20], s2,j in [1, 40] and p2,j in [1, 20]. The number of permutations to generate classes is 42 = 16. The number of machines for each stage is chosen in {2, 3, 4, 5}. The number of permutation to constitute a pair (m1, m2) is 16.

Now, for the number of jobs, we adopt n = {10, 20, 30, 50, 100, 150, 200}. For each type of class (C1, C2, C3, C4), each (m1, m2) and each n we generate 5 instances. Finally, the total number of instances is 16 × 16 × 7 × 5 = 8960.

5.2 Performance Measures

To assess the performance of the heuristics and lower bounds, the following performance measures are used:

▪    Time: average CPU time (s)

▪     Gap=UB∗−LB∗LB∗ , where UB∗ the best heuristic value and LB∗ the best obtained lower bound value.

▪     GapL=LB∗−LLB∗ , where L is the studied lower bound value.

▪     GapU=U−UB∗UB∗ , where U is the studied heuristic value.

5.3 Results and Discussion

Tab. 4 represents the variation of the Gap according to n. As shown in this table when the number of jobs increases, the Gap increase. The maximum Gap of 0.27 is obtained when n = 200.

Tab. 5 shows the variation of Gap according to (m1) on stage 1 and to m2 on stage 2.

Tab. 6 presents the Gap values according to C1, C2, C3, and C4. The minimum gap value of 0.13 is obtained when C3= 20.

Now, we present the results obtained for the developed lower bounds. Tab. 7 shows that the best lower bound is LB3. Indeed, the percentage of this is lower when the number of instances that LB3 is the best one is 84.6% in an average time 16.37 and an average gap of 0.04.

Tab. 8, represents the variation of GapL according to n. For LB3 the maximum gap is obtained when n = {10, 20, 30}.

Tab. 9 presents the GapL and Time variation according to m1 and m2 for all lower bounds. The most time-consuming lower bound is LB3 when m1 = 5. In this condition, the running time is reached to 34.56 s.

The variation of GapL and Time according to C1, C2, C3, and C4 for all lower bounds is illustrated in Tab. 10.

The assessment of the proposed heuristics is presented in Tabs. 11 and 12.

The behavior of GapU and Time according to m1 and m2 for all heuristics is presented in Tab. 13.

Tab. 14 presents the variation of GapU and Time for C1, C2, C3, and C4 for all heuristics. The maximum reaching time is 21.43 s. This running time is obtained for heuristic H1 when C4 = 20. However, the minimum reached time 10.18 s is obtained for H3 when C2 = 20.

6  Conclusion

This paper focuses on the two-stage hybrid flow shop problem under setup times. Several lower bounds and heuristics were developed. The exact resolution of the problem of the parallel machine is utilized in this paper to elaborate on lower bounds and heuristics. A genetic heuristic is developed for the metaheuristic. A comparison between lower bounds and heuristics is detailed to show the proposed algorithms’ performance in terms of gap and time. The genetic algorithm developed in this paper is the best heuristic comparing with the proposed others ones.

In future research work, the elaboration of exact solutions based on B&B algorithms could be considered. Indeed, the proposed heuristics and lower bounds in the paper can be used to elaborate such an exact algorithm. In addition, some other metaheuristics could be explored to detect the most appropriate ones to this scheduling problem.

Acknowledgement: The authors would like to thank the Deanship of Scientific Research at Majmaah University for supporting this work under Project Number No. 1439-19.

Funding Statement: The authors would like to thank the Deanship of Scientific Research at Majmaah University for supporting this work under Project Number No. 1439-19.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.