# Tabu Search Algorithm Based on Lower Bound and Exact Algorithm Solutions for Minimizing the Makespan in Non-Identical Parallel Machines Scheduling

Authors: Mohammed A. Noman; Moath Alatefi; Abdulrahman M. Al-Ahmari; Tamer Ali
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Recently, several heuristics have been interested in scheduling problems, especially those that are difficult to solve via traditional methods, and these are called NP-hard problems. As a result, many methods have been proposed to solve the difficult scheduling problems; among those, effective methods are the tabu search algorithm (TS), which is characterized by its high ability to adapt to problems of the large size scale and ease of implementation and gives solution closest to the optimum, but even though those difficult problems are common in many industries, there are only a few numbers of previous studies interested in the scheduling of jobs on unrelated parallel machines. In this paper, a developed TS algorithm based on lower bound (LB) and exact algorithm (EA) solutions is proposed with the objective of minimizing the total completion time (makespan) of jobs on nonidentical parallel machines. The given solution via EA was suggested to enhance and assess the solution obtained from TS. Moreover, the LB algorithm was developed to evaluate the quality of the solution that is supposed to be obtained by the developed TS algorithm and, in addition, to reduce the period for searching for the optimal solution. Two numerical examples from previous studies from the literature have been solved using the developed TS algorithm. Findings show that the developed TS algorithm proved its superiority and speed in giving it the best solution compared to those solutions previously obtained from the literature.


---

## Body

## 1. Introduction

Scheduling plays an essential role in the management of production. The scheduling dictates what will be done, where, and with what resources [1]. Production scheduling is an important decision-making process at the operational level and is a difficult problem depending on the number of calculations needed to get a schedule that will maximize the criterion chosen. Many scheduling issues exist in modern manufacturing environments. There are many shops in the factory, depending on the machine configuration and workflow [2]. A flow shop is a shop in which machines are organized in series; jobs start processing on an initial machine, cross several intermediate machines, and end in a final machine. In a job shop, jobs can be done in any order on machines. In other words, no unique restriction of machine order is enforced.Machine scheduling is one of the most widely researched fields in the research literature on operations, and it covers a wide range of issues [3]. The issue discussed in this paper is that independent jobs should be scheduled on nonidentical parallel machines to minimize the total completion time of the job “makespan.” There are n separate jobs, each with its own processing time and can be processed on any m parallel machine that is nonidentical. Each of these unrelated machines has a different speed as Si. Makespan (Cmax) is the completion time for the last job leaving the system for scheduling issues. Typically, small Cmax means a high use. Reducing Cmax should also result in a higher performance level [4, 5].There arem machines and n jobs which need to be handled in an organized way. Jobs may not need all m machines and may need to be visited by those machines more than once. Only one machine is able to perform a specific task. In reality, many copies of the same machine are always present (parallel machine). There are also several machines that can perform the work. Scheduling determines the number of jobs completed. The requisite inputs are a list of operations that must be performed, the time it takes for each operation, and a list of any prior restrictions that define the operations that must be followed by others. If jobs have no precedence constraints, it is named as an open shop. In a general job shop, there are two scheduling types: for the first one, for a single machine and n jobs, there are n! choices of possible schedules. For the second type, if there are m machines and n jobs, the number of possible schedules is (n!) m [2]. Therefore, the scheduling problem is more difficult to be solved via dispatching rules (LPT, SPT, EDD, etc.), and these are called NP-hard problems [6, 7]. With traditional optimization approaches, it is very difficult to achieve an optimum solution. Mathematical optimizations can provide an optimal solution for a reasonable size problem, but their implementation is limited in the case of a large-scale problem. Dispatch rules can be only adapted for small-scale problems, and there are no good results in different problems with a single dispatching rule [8]. Consequently, many previous studies’ effort centered on heuristic methods to solve complex problems.In this study, the tabu search (TS) algorithm has been developed to solve like these complex problems based on the exact (EA) and lower bound (LB) algorithms. The reason for presenting TS for minimizing the makespan in nonidentical parallel machines’ scheduling in this paper is that the solutions of the proposed method depend on the value of the lower bound to stop, unlike the previous TS methods, in which the solution iterations are predetermined to stop, even if they do not find the optimum solution. Also, it is known that the exact algorithm (EA) cannot solve the large scheduling problems. Unlike the proposed approach, it can solve big scheduling problems quickly.


## 2. Literature Review

In this section, prior research studies related to the scheduling of nonidentical parallel machines and related observations are summarized. Fanjul-Peyro and Ruiz [9] proposed a set of simple iterated greedy local search-based metaheuristics for nonidentical parallel machines’ scheduling with the objective to minimize the makespan, which produce solutions of very good quality in a very short amount of time. In the study of Vallada and Ruiz [10], a genetic algorithm (GA) was introduced to the nonrelated parallel scheduling machines with considered machine and job sequence setup times. The proposed GA includes a simple local search and a crossover operator enhanced with local search. The proposed method produced good results as a model for large-scale and small-scale experiments. Fanjul-Peyro and Ruiz [11] proposed mixed-integer programming mathematical formulations via two generalizations for scheduling the nonidentical parallel machines’ problem for makespan minimization: the first is a condition in which not every parallel machine available should be used and only a subset of parallel machines should be used; the second is no responsibility to manage all jobs available. Comprehensive tests show that the two suggested algorithms boost the results substantially. Balin [12] proposed GA and fuzzy processing time simulation for scheduling a set of jobs on unrelated parallel machines. The results were compared with those obtained from when using the longest processing time (LPT) rule. The proposed approach showed good results and achieved them easily and multiple times in one sprint. Joo and Kim [13] proposed two metaheuristics; these are GA and a new evolutionary metaheuristic population-based algorithm called self-evolution to assess job allocation and scheduling of nonidentical parallel machines to reduce the makespan. The efficiency of the metaheuristic algorithms is evaluated by using randomly generated several examples to compare with optimal solutions.Fleszar et al. [14] developed a variable neighborhood descent search algorithm hybridized with mathematical programming elements for minimizing the makespan for scheduling jobs on unrelated parallel machines. The study of Joo and Kim [15] proposed hybrid GA with dispatching rules for scheduling a set of jobs on nonidentical parallel machines with sequence- and machine-dependent setup times and machine-dependent processing times for minimizing the makespan. Geyik and Elibal [16] proposed a fuzzy linguistic approach for considering the learning effect for solving nonidentical parallel processor scheduling under uncertain processing times. Arroyo and Leung [17] developed a lower bound for the problem and proposed a mixed-integer programming model and several heuristics based on first-fit and best-fit earliest job-ready time rules to minimize the makespan in unrelated parallel batch-processing machines for scheduling nonidentical job sizes and unequal ready times. Tan et al. [18] proposed a hybrid GA and greedy strategy for green batch scheduling on unrelated parallel machines to minimize total electricity costs in production.Liu et al. [19] developed a mixed-variable differentiate evolution (MVDE) as the scheduling algorithm for coordinated charging scheduling of electric vehicles. Zhou et al. [20] proposed a self-adaptive differential evolution algorithm for scheduling a single batch-processing machine with arbitrary job sizes and release times. The study goal is to assign jobs into batches without breaking the machine capacity constraint and then sort the batches to minimize the makespan. Zhao et al. [21] proposed a self-learning discrete Jaya algorithm for multiobjective energy-efficient distributed no-idle flow-shop scheduling problem in the heterogeneous factory system. Zhao et al. [22] proposed a two-stage cooperative evolutionary algorithm with problem-specific knowledge for energy-efficient scheduling of the no-wait flow-shop problem.Many heuristics have been proposed such as branch and bound (B&B), simulated annealing (SA), genetic algorithm (GA), tabu search (TS), and neural network (NN). Among these different approaches to various scheduling problems, lately, there is an increasing interest in applying TS because of its high ability to give a solution that is very close to the optimal solution and its ease of implementation. Glover [23] implemented the TS algorithm, and since then, it has become very popular in solving the optimization issues. Many studies such as [24–26] have shown that the TS will yield higher timetables than others. TS approach uses the memory to store search-related information that helps avoid cycles (previous solutions that were visited could be reselected). Tabu list is the name of the memory used. The tabu list is updated for every TS iteration. Due to the limitations in the tabu list, the risk of rejecting solutions not yet produced may occur. Tabu solutions for a condition that is called aspiration criteria are then reviewed. If the tabu solution has a better objective value than the best objective value so far found, it is then acknowledged and excluded from the tabu list. This tabu solution will be removed from the tabu list [27]. TS algorithm has different elements that must be tuned before the search process is initiated. The primary solution, tabu list, neighboring structure, aspiration criteria, and stop criteria are the principal features of the TS. The initial TS solution was developed by using the LPT rule in which jobs in the nonincreasing order of processing time are sequenced. The two classic and useful operators for constructing promising neighborhood structures are parity interchange and reverse reintegration [28]. The pairwise interchange operator was implemented in the proposed TS algorithm for generating new candidate solutions. The importance of the metaheuristic parameters has an effect on its efficiency. In general, the main difficulties in TS include tabu list design, list management mechanism, and nonprohibited selection of the move [29]. This is not an easy job for certain optimization issues. In addition, TS may be very sensitive to certain parameters, such as tabu list size [27]. There are many studies that have good applications of TS which can be found in [23, 30–37].


## 3. Problem Description

In this study, a number ofn jobs on m nonidentical parallel machines are to be processed. Each machine (i) can process just one job (j) at a time. Each job should be handled continuously without any interruption. Put P (i, j) as the processing time of job j on machine i. The objective is to make the maximum makespan as minimized as possible.xi,j is the variable which determines whether job j is processed by machine i (if x (i, j) = 1) or not ifxi,j=0. The matrix X is composed of variables xi,j, and it has the following properties [38]:(1)
All elements are equal to “0” or “1,”xi,j∈0,1.(2)
Each column has only one element valued “1.”(1)∑i=1mxi,j=1,j=1,…,n.(3)
The number of elements valued “1” isn.(2)∑j=1n∑i=1mxi,j=n.In equation (3), the processing time j on different machines is expressed as follows:(3)Pi1,j×S1=Pi2,j×S2,where S1 is the speed of machine 1 and S2 is the speed of machine 2.Equation (4) expresses on the makespan of the jobs:(4)Cmax=maxi=1m∑j=1nxi,j×Pi,j.Thus, the objective function may be defined as follows:(5)minCmax.


## 4. The Proposed Methodology

The proposed methodology of this study consists of three phases. In the first phase, we proposed an exact algorithm to be used as a base of comparison to measure the effectiveness of the next two phases. Then, the second phase established a lower bound that judges the optimality of the next heuristic algorithm. Also, it helps in identifying the stopping criteria of the search. Finally, tabu search algorithm is used to search for the best and optimal solution depending on the proposed lower bound.


### 4.1. Scheduling Using the Exact Algorithm (EA)

This section discusses the exact algorithm that is intended to calculate optimal total completion time as the following:(1)
Decision variables:(6)xi,j=1if jobjis processed on machinei,0,otherwise.(2)
Objective function:(7)MinCmax.(3)
Constraints:(8)Cmax≥∑j=1nPi,j×xi,j,∀i∈1,…,m,(9)∑i=1mxi,j=1,∀j∈1,…,n,(10)xi,j∈0,1.The objective function shown in equation (7) is to minimize the maximum completion time for all the jobs. Constraint (8) calculates the completion time for each job. Constraint (9) guarantees that each job is assigned precisely to one machine. Constraint (10) is a binary decision variable.


### 4.2. Lower Bound (LB)

In this section, the lower bounds LB1 and LB2 that are used to evaluate the quality of the heuristic method that is used to find the optimal makespan are proposed. Set, for 1≤j≤n,Dj=mini=1,…,mpij, and LB1 is defined as a lower bound for the problem, LB1=∑j=1nDj/n, where Dj is the smallest processing time of each job. It is worth noting that every machine is busy processing some jobs. Next, define εj as an efficiency of the second smallest processing time of a job (j); therefore, εj=second smallest processing timecof jobj/smallest processing time of jobj. Then, the lower bound LB2 is iteratively calculated in order to improve the lower bound LB1 as described in Algorithm 1 [39].Algorithm 1: The algorithm to calculate LB2.
Put LB3 ← (smallest overall processing time of the jobs/total machines).LB2 ← LB3While LB2 ≤ LB3doRemove jobs that have the lowestεj percentage with preemption from machines that have makespan greater than LB2 to their second-fastest machines.LB3 ← (new minimum overall processing time of the jobs/total machines).LB2 = LB2 + 1end whileLB2 = LB2 − 1The objective is to increase the overall processing time from the likely minimum value step by step. LB3 is the new minimum total processing time of the jobs over the total machines, which is intuitively a lower bound. With this algorithm, the total processing time is increased each time; this increase is the minimum possible. While LB2 ≤ LB3, the value of LB2 will remain as a lower bound because it is less than the possible minimum makespan at that point of time. Only when LB2 > LB3, the last LB2 value will take as the lower bound.


### 4.3. Scheduling Using Tabu Search (TS)

This section discusses the TS algorithm that is intended to calculate optimal total completion time and shows how to select the parameter values for the TS algorithm.Parameter tuning is an important problem in the design of metaheuristics. To this end, test runs for a wide range of parameter values for the TS algorithm have been performed, and the best configuration has been selected and described as follows:(1)
Based on preliminary experiments, the number of candidates produced was 70(2)
There were three elements of the tabu list size, and an update to the tabu list was performed using the first-in-first-out (FIFO) technique(3)
The iterations have been designed to be 5000; the iterations stop if the tabu solutions equal with the lower bound(4)
The criteria for ambition have been defined as described previously (if a step leads to a better solution than the best one ever)In general, the TS algorithm can be defined as described in Algorithm2.Algorithm 2: TS algorithm template.
Choose the initial solution using LPT rules0Initialize memory structuresRepeatGenerate a set “A”of nontabu solutions s∈Ns0s=best solution ofAUpdate memory structuresIffs<fs0,thens0=sUntil stopping criterion trues0 is an approximate solution to the optimal solutionFirstly, the general structure of TS shows an initial solution of the problem using the LPT method and then creates a set of neighbor solutions; after that, the evaluation of the solutions is done using LB, and the best permissible solution is selected as described in Figure1.Figure 1
General structure of TS.


## 4.1. Scheduling Using the Exact Algorithm (EA)

This section discusses the exact algorithm that is intended to calculate optimal total completion time as the following:(1)
Decision variables:(6)xi,j=1if jobjis processed on machinei,0,otherwise.(2)
Objective function:(7)MinCmax.(3)
Constraints:(8)Cmax≥∑j=1nPi,j×xi,j,∀i∈1,…,m,(9)∑i=1mxi,j=1,∀j∈1,…,n,(10)xi,j∈0,1.The objective function shown in equation (7) is to minimize the maximum completion time for all the jobs. Constraint (8) calculates the completion time for each job. Constraint (9) guarantees that each job is assigned precisely to one machine. Constraint (10) is a binary decision variable.


## 4.2. Lower Bound (LB)

In this section, the lower bounds LB1 and LB2 that are used to evaluate the quality of the heuristic method that is used to find the optimal makespan are proposed. Set, for 1≤j≤n,Dj=mini=1,…,mpij, and LB1 is defined as a lower bound for the problem, LB1=∑j=1nDj/n, where Dj is the smallest processing time of each job. It is worth noting that every machine is busy processing some jobs. Next, define εj as an efficiency of the second smallest processing time of a job (j); therefore, εj=second smallest processing timecof jobj/smallest processing time of jobj. Then, the lower bound LB2 is iteratively calculated in order to improve the lower bound LB1 as described in Algorithm 1 [39].Algorithm 1: The algorithm to calculate LB2.
Put LB3 ← (smallest overall processing time of the jobs/total machines).LB2 ← LB3While LB2 ≤ LB3doRemove jobs that have the lowestεj percentage with preemption from machines that have makespan greater than LB2 to their second-fastest machines.LB3 ← (new minimum overall processing time of the jobs/total machines).LB2 = LB2 + 1end whileLB2 = LB2 − 1The objective is to increase the overall processing time from the likely minimum value step by step. LB3 is the new minimum total processing time of the jobs over the total machines, which is intuitively a lower bound. With this algorithm, the total processing time is increased each time; this increase is the minimum possible. While LB2 ≤ LB3, the value of LB2 will remain as a lower bound because it is less than the possible minimum makespan at that point of time. Only when LB2 > LB3, the last LB2 value will take as the lower bound.


## 4.3. Scheduling Using Tabu Search (TS)

This section discusses the TS algorithm that is intended to calculate optimal total completion time and shows how to select the parameter values for the TS algorithm.Parameter tuning is an important problem in the design of metaheuristics. To this end, test runs for a wide range of parameter values for the TS algorithm have been performed, and the best configuration has been selected and described as follows:(1)
Based on preliminary experiments, the number of candidates produced was 70(2)
There were three elements of the tabu list size, and an update to the tabu list was performed using the first-in-first-out (FIFO) technique(3)
The iterations have been designed to be 5000; the iterations stop if the tabu solutions equal with the lower bound(4)
The criteria for ambition have been defined as described previously (if a step leads to a better solution than the best one ever)In general, the TS algorithm can be defined as described in Algorithm2.Algorithm 2: TS algorithm template.
Choose the initial solution using LPT rules0Initialize memory structuresRepeatGenerate a set “A”of nontabu solutions s∈Ns0s=best solution ofAUpdate memory structuresIffs<fs0,thens0=sUntil stopping criterion trues0 is an approximate solution to the optimal solutionFirstly, the general structure of TS shows an initial solution of the problem using the LPT method and then creates a set of neighbor solutions; after that, the evaluation of the solutions is done using LB, and the best permissible solution is selected as described in Figure1.Figure 1
General structure of TS.


## 5. Results and Discussion

In this section, the scheduling problem ofn jobs on m nonidentical machines is solved using EA and TS algorithms described above. As a numerical example in the study of Balin [5], nine jobs are scheduled on four nonidentical machines. The objective is to minimize makespan (Cmax). Problem data are summarized in Table 1.Table 1
Nine jobs and four nonidentical parallel machines’ scheduling [5].
JobMachineM1M2M3M4Job 11894.53.6Job 21473.52.8Job 3241264.8Job 430157.56Job 516843.2Job 6201054Job 722115.54.4Job 826136.55.2Job 91473.52.8Table2 shows the scheduling of the nine jobs on the four nonidentical machines problem using GA proposed by Balin [5] and shows that the makespan obtained is 16 minutes. Gantt chart for scheduling every job on the machines is shown in Figure 2.Table 2
Scheduling with GA [5].
MachinesScheduled jobsCi (min.)M1Job 214M2Job 1, job 916M3Job 5, job 7, job 315.5M4Job 6, job 8, job 415.2Figure 2
Jobs’ scheduling using GA [5].Tables3 and 4 show the same scheduling solution of the same problem proposed by Balin [5] and show the best makespan using EA and TS which is only 15.6 minutes.Table 3
Scheduling with EA.
MachinesScheduled jobsCi (min.)M1Job 214M2Job 415M3Job 1, job 3, job 615.5M4Job 5, job 7, job 8, job 915.6Table 4
Scheduling with TS.
MachinesScheduled jobsCi (min.)M1Job 214M2Job 415M3Job 1, job 3, job 615.5M4Job 5, job 7, job 8, job 915.6Gantt chart for job scheduling every job on the machines using EA or TS is shown in Figure3. It is observed that the makespan obtained using EA and TS is 15.6 minutes which is best obtained from GA.Figure 3
Jobs’ scheduling using EA and TS.To show the effect of every algorithm on the makespan, Figure4 compares between the makespan solutions obtained from LPT and GA algorithms given by Balin [5] and the developed EA and TS algorithm solutions.Figure 4
Histogram of averages of makespan means forn = 9 and m = 4.To enhance the effect of the developed algorithms on minimizing the makespan, another big example from the study of Lei and Liu [40] is studied. The example consists of thirty jobs which are scheduled in five nonidentical parallel machines as shown in Table 5. The developed algorithms have given the best makespan over the artificial bee colony (ABC) algorithm which was used by Lei and Liu [40].Table 5
Thirty jobs and five nonidentical parallel machines’ scheduling [40].
JobMachineJobMachineM1M2M3M4M5M1M2M3M4M5150384349471650423042502464230495017453248343334435433637184740353846438434448481948454434445393947364920434133484464342355038213344493633738423839302248424735308343537343323324732344294748413942244232424536103230343831253448353941114138374833263839435049123738484931273846454031134041444545283736444048144340473740293132423944155042443940303546443833Gantt charts for job scheduling the problem studied by Lei and Liu [40] using ABC and (EA or TS) are shown in Figures 5 and 6, respectively. It is observed that the makespan obtained using EA and TS is 209 minutes which is best than that obtained from ABC, which is 218 minutes.Figure 5
Gantt chart for job scheduling using ABC [40].Figure 6
Gantt chart for job scheduling using EA and TS.To assess the quality of EA and TS algorithm solutions on minimizing the makespan, Figure7 compares between the ABC algorithm solution proposed by Lei and Liu [40] and the developed algorithm solutions. It is observed that the solution obtained from the developed algorithms is better than that obtained from the ABC algorithm. Additionally, it always equals the lower bound.Figure 7
Histogram of averages of makespan means forn = 30 and m = 5.Based on the value of the lower bound, the TS method was devised. There are no preset endpoints to the solution iterations, unlike the prior TS techniques. The EA is well known to be unable to address huge scheduling issues. In contrast to the proposed method, it can swiftly address large scheduling issues.


## 6. Conclusion

Many scheduling problems are NP-hard. Consequently, it is impossible to solve these problems efficiently via polynomial-time algorithms. Mathematical optimization techniques are suitable only for small-scale problems; therefore, they have limited applications in the case of a large-scale problem. Thus, the study efforts have focused on heuristic approaches. Among these approaches, TS outperforms others because of its high ability to give a solution that is very close to the optimum solution and its ease of implementation.This paper proposed a developed TS algorithm for scheduling a set of jobs on nonidentical parallel machines with the intention of studying this algorithm’s effect on minimizing the makespan. EA solution was proposed to enhance and evaluate the solution obtained from TS. Moreover, lower bound was developed to assess the quality of the proposed algorithm solution. The proposed algorithm solution is compared with the solutions obtained from other algorithms from the literature. Computational results showed that the solution obtained from the developed TS algorithm outperforms all the algorithms in the literature. The essential difference between TS and other heuristics is that TS is one of the most efficient heuristic techniques in the sense that it finds quality solutions in relatively short running time. Moreover, the developed TS algorithm always gives a solution that is equal or close to the lower bound.



---

*Source: 1856734-2021-12-25.xml*