A novel dynamic assignment rule for the distributed job shop scheduling problem using a hybrid ant-based algorithm

Abstract

Distributed scheduling problems are among the most investigated research topics in the fields of Operational Research, and represents one of the greatest challenges faced by industrialists and researchers today. The Distributed Job shop Scheduling Problem (DJSP) deals with the assignment of jobs to factories and with determining the sequence of operations on each machine in distributed manufacturing environments. The objective is to minimize the global makespan over all the factories. Since the problem is NP-hard to solve, one option to cope with this intractability is to use an approximation algorithm that guarantees near-optimal solutions quickly. Ant based algorithm has proved to be very effective and efficient in numerous scheduling problems, such as permutation flow shop scheduling, flexible job shop scheduling problems and network scheduling, etc. This paper proposes a hybrid ant colony algorithm combined with local search to solve the Distributed Job shop Scheduling Problem. A novel dynamic assignment rule of jobs to factories is also proposed. Furthermore, the Taguchi method for robust design is adopted for finding the optimum combination of parameters of the ant-based algorithm. To validate the performance of the proposed algorithm, intensive experiments are carried out on 480 large instances derived from well-known classical job-shop scheduling benchmarks. Also, we show that our algorithm can process up to 10 factories. The results prove the efficiency of the proposed algorithm in comparison with others.

1 Introduction

Following [5], scheduling problems can be broadly defined as ”the problems of the allocation of resources over time to perform a set of tasks”. The scheduling literature is full of very diverse scheduling problems [7, 25]. The Job shop Scheduling Problem (JSP) is one of the most important and complex problems in machine scheduling.

The classical JSP is NP-hard in the strong sense [27] and it represents probably one of the most computationally intractable combinatorial problems considered so far. A practical proof of this intractability comes from the fact that a small example with 10 jobs and 10 machines proposed by Muth and Thompson [43] remained open for over 15 years. It was solved in 1980 by Carlier and Pinson [9] as the achievement of a considerable amount of research. A feasible schedule is obtained by permuting the processing order of operations on the machines (operations sequence) without violating the technological constraints. Since each operation sequence can be permuted independently of the operation sequences of other machines, we have a maximum of (n!)^m different solutions to a problem instance, where n denotes the number of jobs and m denotes the number of machines involved [31]. The explosive exponential growth in the number of alternative schedules with the size of the problem increases the difficulty of identifying one of these as the solution of the JSP problem. In the JSP, there are n jobs and m machines to be scheduled; each job consists of a predetermined sequence of operations, which have to be processed on a set of m machines, and each operation is characterized by the required machine and the fixed processing time.

The JSP, as a field of research, has displayed exponential growth during the last six decades and a vast amount of literature that has been published in this area. Roy and Sussmann [50] were the first to propose the disjunctive graph representation and Balas [3] was the first to apply an enumerative approach based on the disjunctive graph. Since, various strategies over the years have been applied trying to solve the problem: exact methods, heuristic and meta-heuristic algorithms. Exact methods, such as branch and bound [62], guarantee to find an optimal solution for the problem, but have an exponential computational complexity, so that the time to solve the problem may grow exponentially with its size. Therefore, the use of approximate methods and heuristics is inevitable for solving NP-hard problems. Unlike heuristics, which usually find reasonably ”good” solutions in a reasonable time, approximation algorithms provide provable solution quality and provable run-time bounds. For instance, dispatching rules were adapted in Grabot’s work [14, 60], bottleneck-based heuristics [11, 67], neural networks [64], expert systems and constraint satisfaction [57]. Within the local search category, many methods have been applied to the JSP since its appearance. They include algorithms such as Simulated Annealing (SA) [54], Genetic Algorithms (GA) [2, 28, 48, 63], Tabu Search (TS) [12, 24, 49], ant optimisation [68], scatter search, path relinking (SS& PR) [32] and Invasive Weed Optimization algorithm (IWO) [69]. Swarm intelligence and bio-inspired algorithms were widely used to solve the JSP. Heinonen and Pettersson [30] developed a hybrid approach based on an Ant Colony Optimization algorithm (ACO) and a post-processing algorithm to enhance the ACO performance for solving the JSP. Tasgetiren et al. [59] presented a hybrid method (PSO-VNS) based on the Particle Swarm Optimization (PSO) and the Variable Neighborhood Search (VNS) to improve the solution quality in JSP. To further improve efficiency of PSO, a new hybrid swarm intelligence algorithm (MPSO) consisting of particle swarm optimization, Simulated Annealing (SA) and a multi-type individual enhancement scheme was developed by Lin et al. [38]. Inspired by the decision making capability of bee swarms, Chong et al. [15] explored an evolutionary computation based on Bee Colony Optimization (BCO) to solve the JSP. Yao et al. [65] presented an Improved Artificial Bee Colony algorithm (IABC) to enhance the search performance of the original ABC for solving the JSP.

As can be seen, the JSP problem has been extensively discussed in the literature and has had several extensions [46, 53]. In the majority of studies, we have noticed a common assumption is that all jobs are processed in the same factory which is not always the case when it comes to model real-life problems. In fact, in today’s globalization economy, many companies have turned from traditional single-factory production to multi-factory production to remain competitive and for closer proximity to the market. This will allow companies to save time and reduce costs, hence, respond effectively to customer demands. Consequently, researchers have been increasingly attracted by the distributed scheduling problems which deal with the assignment of jobs to various factories geographically distributed and their scheduling over machines. In this context, the JSP has evolved from the classical version to the Distributed Job shop Scheduling Problem (DJSP) and becomes, increasingly, one of the most important issues to raise.

The DJSP is much more complicated than the JSP since other decisions have to be taken. The difficulty is two fold: first, there is the problem of allocating jobs to suitable factories and second, sequencing the operations on machines with the objective of minimizing one or more predefined performance criteria. Garey et al. [24] proved that the JSP is strongly NP-hard. Hence, the DJSP is ordinarily NP-hard and the case of the simple JSP can be obtained when the number of factories is equal to 1.

In this paper, we propose to solve the DJSP with makespan criterion using a novel Dynamic Assignment method of jobs to factories with a Hybrid Ant Colony Optimization algorithm (DAHACO). Our intention is to increase the diversity of the population and the portion of the search space that is explored. In fact, in the field of DJSP, researches have neglected communication between factories, and all works in the literature have considered the case of static assignment of jobs to factories. In other words, once the job is assigned to a factory, it is frozen and cannot be moved to another one. This limits the search for a better solution and reduces the problem to a classical one that comes to solving a scheduling problem in each factory separately and neglects the overall aspect of the problem. This is why we propose to develop a novel dynamic assignment method which apply a first allocation of job to factories using the workload method introduced in [44], then improve the results generated by applying numerous jobs-permutations between factories in order to have several combinations of assignments. These combinations will serve to broaden the initial population for the algorithm and offer a large research space to explore. Our proposed algorithm is combined with a local search in order to reduce the idle time of machines and improve the solution.

So, this study is the first attempt in the literature to solve the DJSP with a dynamic assignment of jobs to the factories. A comparative study between static assignment rule and dynamic one is presented. Furthermore, we investigate on the influence of the different parameters by using the Taguchi method, and the best parameter setting is suggested. 480 benchmark instances have been used to evaluate the performance of the proposed DAHACO. The experimental results prove that the proposed DAHACO algorithm is both effective and efficient. In essence, the contributions of this paper are threefold as follows:

• It proposes a novel assignment rule of jobs to factories in distributed environment;

• It proposes a hybrid ant-based algorithm for solving the DJSP;

• It adopts the Taguchi method for parameter design in determining the optimum level of parameters used in the algorithm.

The rest of the paper is organized as follows. In Section 2, the distributed job shop scheduling problem is formally defined. Then, a comprehensive literature review of the problem is provided in Section 3. In Section 4, the original framework of the ant colony algorithm is presented in detail. Section 5 introduces the proposed DAHACO to solve the DJSP with makespan criterion. The Taguchi Method is introduced in Section 6. Parameter setting and numerical testing results are provided in Section 7. Conclusions are finally drawn in Section 8, along with recommendations for future researches.

2 The distributed job shop scheduling problem

A typical Distributed Job shop Scheduling Problem (DJSP) can be stated as a set of n jobs, which have to be processed on a set of m machines geographically distributed on f identical factories. The main objective of the DJSP is to find an optimal scheduling minimizing a specified criterion which is generally time related such as makespan, maximum tardiness or total tardiness. The most widely adopted criteria among literature is minimizing the makespan which can be set as the maximum of completion times needed for processing all jobs. Distributed Scheduling problems in multi-factory production are much more complicated than classical scheduling problems since two decisions have to be taken: assign jobs to suitable factories and generating a feasible scheduling while minimizing a predefined performance criterion.

A job consists of a set of operations which have to be processed on machines in a predetermined order. These operations are subject to various assumptions in the DJSP. All factories should be able to process all jobs and once a job is assigned to a factory, it cannot be moved to another one until all its operations are proceeded in the same plant. At the starting time, all jobs and machines are available. Jobs are independent and there are no precedence constraints among the operations of different jobs. A job can be processed by at most one machine at a time and a machine can process at most one job at a time. It is assumed that every job has to be processed on every machine exactly once and neither the release times nor due dates are specified. Each operation is characterized by the required machine and the fixed processing time. Setup times of machines and transit times between operations are negligible in our problem.

As discussed in the introduction, the DJSP is strongly NP-hard since we have more decisions to be taken and the global objective becomes the minimization of the makespan among several factories. For clarity’s sake, we give an illustrative example of DJSP representation. Given an instance with six jobs, two machines and two factories, the processing times of the jobs on each machine is given in Table 1 (let us remind that factories are identical). A Distributed Job shop Problem instance can be visualized by a directed graph D = (N, A, E), where N represents the set of nodes corresponding to all operations O processed in the same factory, A the set of conjunctive directed arcs, based on the precedence rules and E the set of disjunctive directed edges that connect two operations from two different jobs executed on the same machine and factory. Figure 1 shows the disjunctive graph of the example and a feasible Gantt chart of this problem is shown in Fig. 2. Makespan in factory 1 is 8 and makespan in factory 2 is 10, leading to the conclusion that the makespan of this DJSP is equal to the maximum makespan between the two factories, which is 10.

Table 1 Processing time matrix

Fig. 1

Directed graph representation for the DJSP with f = 2; n = 6 and m = 2

Fig. 2

Gantt Chart of the DJSP with f = 2; n = 6 and m = 2

3 Related works

In recent years, considerable attention has been given to the DJSP, but the literature is still relatively limited since the issue is recent. So far, the methods that have dealt with the DJSP can be divided into two categories: exact methods and metaheuristics. For the exact methods, we can find [44] that have mathematically formulated the DJSP with two different Mixed Integer Linear Programming models (MILP). The first model dealt with the problem as a sequencing decision while the second one dealt it as a positional one. The authors have proposed another MILP model in their next paper [45]. In order to evaluate the developed MILP models, the authors used two performance measures: size and computational complexities. All other studies applied metaheuristics to solve the DJSP. Indeed, Jia et al. [34] presented the first attempt to solve the problem. In their study, they proposed a web-based system to enable production scheduling with the utilization of the World Wide Web technology, in order to facilitate collaboration between geographically distributed plants. A Genetic Algorithm (GA) approach was adopted to deal with the distributed scheduling problems. In their next paper, authors in [36] presented a Modified Genetic Algorithm (MGA) in which a two-step encoding method was used. The first one to encode the factory candidates and the second one, to affect jobs and operations. To evaluate the performance of their MGA, the authors used benchmark instances (10 jobs/10 machines and 20 jobs/5 machines) proposed by [43]. In fact, MT1963 are instances for simple job shop problems which are adapted to the DJS by distributing different jobs on the factories. Later, Jia et al. [35] refined their previous approach and proposed a GA integrated with Gantt Chart (GC) to derive the factory combination and schedule. The experimental results showed that the application of the GC is able to facilitate the chromosome evaluation procedures and thus improve the computational performance algorithm. Recently, in [44], three well-known heuristics were applied; these are Shortest Processing Time first (SPT), Longest Processing Time first (LPT) and Longest Remaining Processing Time (LRPT). Finally, three Greedy Heuristics have been developed and adopted to solve the problem (GH1, GH2 and GH3). The performance of the two proposed mathematical models and six heuristics (SPT, LPT, LRPT, GH1, GH2 and GH3) are evaluated and tested. With regards to the obtained optimal solutions, it is concluded that the developed GH3 performs better than the other algorithms. In their next paper [45], the authors applied three different versions of Simulated Annealing (SA) and designed two different local search engines to improve operation sequence for the factories. The first local search aims to decrease the makespan and the second one aims to increase the makespan. The first version of the proposed algorithms,

called SA, is implemented without any local search. The second one, called hybridized simulated annealing (HSA), is hybridized with local search type 1 which assumes that the job number is first inserted into m random positions. Then, the position of one randomly selected job number is shifted to a random position. Finally, the third version, called greedy simulated annealing (GSA), employs the greedy local search 2 which assumes that job number is added into permutation one by one. To evaluate the proposed algorithms, three sets of instances were generated. The first set is for parameter tuning, the second one is for the experiment with small instances, and finally, the last one is for the experiment with larger instances. The solutions proposed in this article obtained promising results and outperformed the other tested algorithms. Chaouch et al. [10] surveyed the literature related to the DJSP. They presented papers dealing with the problem and a classification of the employed techniques is well established. As we can see, researchers have in recent years attempted to resolve the DJSP using various methods and producing different results compared to each others. Hence, trying to apply new and leading edge approaches is a growing challenge in order to find better results. Table 2 summarizes all papers dealing with the DJSP and provides a clear classification of them in term of year of publication, objective function, employed techniques for resolution and scheduling type (dynamic or static). In the next section, we present an overview of ant colony optimization algorithm as well as the main motivation to employ it as a solution for the DJSP with makespan criterion.

Table 2 Classification of distributed job shop scheduling problem papers

4 Ant colony optimization

Imitating natural evolutionary processes of living beings to solve hard optimization problems have received a great interest which gave rise to Evolutionary Algorithms (EAs) in the late 1960s. Since that, we witnessed the emergence of many metaheuristic algorithms belonging to EAs that can often outperform classical optimization methods when applied to difficult real world problems. Swarm Intelligence is a collection of nature-inspired algorithms under the big umbrella of evolutionary computation [47], among them, Ant Colony Optimization (ACO) [19] is perhaps the most widely known type of swarm intelligence algorithms used. Marco Dorigo and colleagues introduced the first ACO algorithms in the early 1990s [19, 21, 22]. Then, several studies have applied the ACO to solve different problems, such as Traveling Salesman Problem [20], vehicle routing [26], quadratic assignment problems [42], graph coloring [23] and scheduling problems [6]. Ant colony-based algorithms have been shaped by a number of people who have made valuable contributions to the development of the field. Table 3 summarizes some of the proposed ACO algorithms in the literature.

Table 3 Some of the most used ACO algorithms

The inspiring source of ACO algorithms was the observation of the collective behaviour of ants and more specifically, the ants’ foraging behaviour. When searching for food, ants are able to find the shortest path between a food source and their nest according to their indirect communication by means of chemical pheromone trails. Initially, ants follow different paths surrounding their nest in a random way. As soon as an ant finds a food source, and while walking from food sources to the nest, ant lays down a chemical pheromone on the ground, forming a pheromone trail which guides other ants towards best path. When choosing their way, ants tend to choose, probabilistically, paths marked by strong pheromone concentrations which may depend on the quantity and quality of the food. In the literature, several studies have considered the ACO algorithm in the resolution of the Job shop Scheduling Problem and led to good results.

In a paper by Colorni et al. [17] Ant System (AS) was applied to job shop scheduling problem and proved to be a noteworthy candidate when faced with the task of choosing a suitable algorithm for scheduling problems. The paper concluded that the AS is one of the most easily adaptable population-based heuristics so far proposed and that its computational paradigm is indeed effective under very different conditions. Lu and Romanowski [39] have also achieved good results when applying the ACO to the dynamic job shop problem. As an example of ACO robustness, Jayaraman et al. [33] used an ACO algorithm in solving a combinatorial optimization problem of multiproduct batch scheduling as well as the continuous function optimization problem for the design of multiproduct plant with single product campaigns and horizon constraints. Further real world applications with regard to ACO algorithms would be using ACO to solve an established set of vehicle routing problems as done by Bell and McMullen [4] and a dynamic regional nurse-scheduling problem in Austria by Gutjahr and Rauner [29]. The former paper concluded that the results were competitive and in the latter paper ACO was compared to a greedy assignment algorithm and achieved highly significant improvements. Ying et al. [66] applied the ant colony system to permutation flow-shop sequencing and effectively solved the problem n/m/P/Cmax, and commented that the ant colony system metaheuristic is well worth exploring in the context of solving different scheduling problems.

Motivated by the effectiveness of the ant algorithms in solving different kinds of optimization problems, our approach, presents in the first part, a novel dynamic assignment method of jobs to factories, then, the ant colony optimization algorithm combined with a local search is applied to solve the Distributed Job shop Scheduling Problem.

5 The proposed DAHACO algorithm for the DJSP

In the field of DJSP, researches have overlooked the communication between factories which is a fundamental aspect to consider when solving distributed scheduling problems. Allocating jobs to suitable factories have a significant influence over the quality of the scheduling and so on the value of the makespan. This is why we propose to develop, in the assignment phase, a novel dynamic assignment method which apply the workload method introduced in [44], then improve the results generated by applying numerous jobs-permutations between factories in order to have several combinations of assignments. These combinations will serve to broaden the initial population for DAHACO and offer a large research space to explore.

Our choice to develop an ant-based algorithm is highly motivated by the distributed aspect of the ACO algorithm as we are dealing with a distributed scheduling problem. The coordinated behaviour of real ant is exploited to organize populations of artificial agents, which are artificial ants, that communicate with each other to solve computational problems. If we take a closer look, we can find several similarities between the foraging process of ant colonies and the DJSP. Consider the operations as ants, they must find the best order of processing on the machines minimizing the makespan. By analogy, ants want to search the best path for food while minimizing the length of the path. The start and dummy operation are like an ants’ nest and a food source, respectively. And finally, the link of any two operations can be seen as an alternative route for ant when considering an operation as an ant’s path for foraging food. Our proposed DAHACO is combined with a local search in order to reduce the idle time of machines. In fact, despite the performance of ant colony algorithms, they can easily be trapped in a local optimum due to their stochastic aspects (for example, random solution construction). This is what leads us to think that implementing a local search procedure to improve the solution is strongly recommended, and this will be proven in the experimental part.

In order to adapt the ant colony optimization algorithm to solve the DJSP, a number of elements have to be defined:

• The way in which jobs should be assigned to factories

• Sequencing of jobs assigned to each factory

5.1 Job factory assignment phase

An important step in solving the Distributed Job shop Scheduling Problem is the allocation of jobs to factories. The objective is to partition jobs on factories so as to equilibrate the workloads. In other words, the aim is to have near values of workloads between factories. The job factory assignment phase will be divided in two steps. In the first one, we will use the job-facility assignment rule introduced in [44] with the static assignment of jobs: once jobs are allocated, they cannot be moved from one factory to another. Then, we propose a novel dynamic assignment rule allowing movement of jobs which has proved its effectiveness in most cases.

5.1.1 Workload rule

Let us consider n jobs that will be assigned to f factories. The workload on each machine is separately calculated using the following rule [44], which is defined for each job j on each machine i as follows:

$$ workload(j,i)= \left( \sum\limits_{k\in R_{j,i}} p_{j,k} \right) + p_{j,i} \hspace{0.5cm} ,\forall_{i,j} $$

(1)

Where R_j,i is the set of all machines preceding machine i in the processing of job j and P_j,i is the processing time of job j on machine i. The workload of each operation is calculated and regarding the total workloads, the jobs are ranked in descending order, from highest workload to the lowest ones. The f first jobs are assigned to factories 1...f, respectively. The workload of machines in different factories becomes equal to those of the assigned jobs and the maximum workload in the f factories is determined. To assign the next job, the maximum workload is recalculated if the job is assigned to a factory. All the possibilities should be enumerated and the workload is calculated at each time. Then, the job is assigned to the factory with a minimum of the maximum workload. The procedure repeats for subsequent jobs until all jobs are assigned.

5.1.2 The proposed assignment procedure

The Workload Rule method [44] proved to be efficient to well equilibrate workloads in different factories. But the main disadvantage of this method is that jobs are allocated in a static way, once they are assigned to factories, they can’t be moved from one factory to another and only one assignment combination is explored.

This is what prompted us to think about making the assignment phase dynamic by allowing jobs to move from one factory to another based on the workload method. Our proposed approach takes the result of the workload assignment and performs a set of jobs permutations between factories while maintaining a certain balance in terms of the number of jobs in each factory. Our approach performs better for large instances with large number of jobs and machines. It has allowed to generate new combinations, thus exploiting new possibilities. To illustrate this concept, it is applied to Tai15x15 instance from well-known benchmarks for the Job shop Scheduling proposed by Taillard [55]. The two methods are implemented and ran 100 times, on Tai15x15 with 5 factories, 15 machines and 15 jobs. Figure 3 shows the obtained results and as we can see, in almost all cases, our proposed dynamic assignment method gives better values of makespan.

Fig. 3

Comparison between static and dynamic assignment

5.2 Sequencing phase

Once all jobs are assigned to their corresponding factory, they need to be sequenced. To do this, a hybrid ant-based algorithm is proposed aiming to explore more search space and potentially finding better possible solutions for the problem. In nature, ants are able to find the shortest path between a food source and their nest according to their collective behaviour. In DJSP, the aim is to find the best path giving the minimum makespan among all possible paths.

In this section, the main steps of our proposed algorithm DAHACO will be detailed. The basic principle of the DAHACO is to improve the solution generated by the Ant Colony System (ACS) by applying a local search procedure in order to explore more search space and found better results. The main steps of proposed DAHACO are listed below:

Step 1::

At the beginning of the algorithm, all parameters are initialized including the initial pheromone value of edges τ₀ > 0. Initially, ants choose their paths randomly and therefore, search the solution space more effectively.

Step 2::

Ants are placed on the first operation of each job.

Step 3::

This procedure consists of a probabilistic construction of solutions by all the ants according to the State Transition Rule as follows:

$$ P(i,s)(t)= \left\lbrace \begin{array}{c} \frac{\left[\tau_{i,s} \left( t\right) \right]^{\alpha}\times \left[\frac{1}{d_{i,s}}\right]^{\beta}{}}{{\sum}_{j \in Allowed Nodes} \left[\tau_{i,j}\left( t\right) \right]^{\alpha} \times \left[\frac{1}{d_{i,j}}\right]^{\beta}{}}\\ 0, otherwise \end{array}\right. $$

(2)

With:

• τ_i,j quantity on pheromone between the node_i and node_j

• d_i,j heuristic distance between node_i and node_j. In our case, d_i,j is the processing time of the operation.

• P(i,s) probability to branch from node_i to node_s

• The parameters α and β tune the relative importance in probability of the amount of pheromone versus the heuristic distance.

The probability for an ant to choose the next operation is directed by both the amount of pheromone on the route and heuristic distance from its current position to the next one. Artificial ants can be considered as stochastic greedy procedures that construct a solution in a probabilistic manner by adding solution components to partial ones until a complete solution is derived [56]. In the general ACS, the set of next operations for an ant in node_i is all not visited nodes. Which is not the case in the DJSP, choosing the next operation should respect the operation precedence constraints. Therefore, for each transition from a node_i to node_j, the ant has to build its allowed list containing the operation that can visit.

Step 4::

While constructing its solution, an ant will modify the amount of pheromone on the visited edges by applying the local updating pheromone rule:

$$ \tau_{i,s}(t+n) = (1-\rho) \times \tau_{i,s}(t) + \rho \times \tau_{0}(t+n) $$

(3)

Where ρ is the coefficient representing pheromone evaporation (0 < ρ < 1). The purpose of the local pheromone update rule is to make the visited edges less and less attractive as they are visited by ants, indirectly favouring the exploration of not yet visited edges. As a consequence, ants tend not to converge to a common path.

Step 5::

Once all ants have generated a solution, the global updating rule (7) is applied in two phases:

• An evaporation phase where a fraction of the pheromone evaporates and decreases automatically, so as to diversify the search procedure into larger solution spaces.

• A reinforcement phase where each ant deposits an amount of pheromone which is proportional to the generated solutions

$$ \tau_{i,s}(t+n) = (1-\xi) \times \tau_{i,s}(t) + \xi \times {\Delta} \tau_{i,s}(t+n) $$

(4)

$$ {\Delta} \tau_{i,s}(t+n)= \frac{Q}{Best C_{max_{ant}}} $$

(5)

Here: 0 < ξ < 1 is the pheromone decay parameter and Q is a constant. The global updating pheromone is only applied on the best solution found by the algorithm. The process is repeated until a termination condition has been reached which is a fixed number of iterations in our case.

Step 6 : local search procedure :

Once all ants have generated a solution, a local search procedure is applied in order to explore more search space and found better result if it is possible. First of all, the last scheduled job over all machines is determined and selected to make the first improvement moves. The method consists of finding all inactive time intervals of machines and tries to insert the operations of the selected job in those intervals while respecting DJSP constraints. To place the operation on the inactive interval, the following constraints should be verified:

• The end time of the selected operation > End time of the inactive interval

• Processing time of the selected operation ≤ The length of the interval

• Precedence constraints of the DJSP = True

The main steps of the proposed method are represented in the following diagram, cf. Figure 4 and the two pseudo-codes below:

Fig. 4

The flowchart of the proposed DAHACO

In order to show the relevance and the influence of each implemented part of the algorithm, namely the dynamic assignment rule and the local search procedure, three versions are implemented, cf. Figure 5. In the next section, we conduct extensive computational experiments to analyse and validate the efficiency of our model.

Fig. 5

A diagram outlining the 3 implemented versions

6 Robust parameter design - parameter tuning

The time required to complete an experiment is extremely long, especially, for evaluating large numbers and various factors (parameters). The difficulties are even more complicated when experiments have to be repeated for several times until accurate and validated result is obtained. Considering these difficulties, Dr. Genichi Taguchi has developed a new experimental strategy, Taguchi method, for an experiment in the late 1940s [37, 51]. The application of Taguchi method has attracted more attention in the literature for the past 20 years and nowadays the Taguchi method has been widely applied to various fields, such as manufacturing systems [41]. Taguchi method is a powerful design of experiments which provide effective and efficient approach to optimize designs for performance, quality and cost. The most important difference between classical experimental design and Taguchi method is that the former tends to focus solely on the mean of the quality characteristic while the latter considers the minimisation of the variance of the characteristic of interest. In the present research, Taguchi method is used for parameter design. The purpose is to determine the factors (parameters) and their settings that will provide the best result. The two major tools used in Taguchi methodology are:

• Orthogonal arrays which accommodate many design factors (parameters) simultaneously

• Signal-to-noise ratio (S/N ratio) which measures quality with emphasis on variation

Using Orthogonal Array technique significantly reduces the number of experiments and a more reliable estimation of the effect of parameters can be obtained. The signal to noise ratio provides a measure of the impact of noise factors on performance. The larger the S/N, the more robust the product is against noise. The S/N ratio is expressed in decibel (dB) units. Based on the type of performance characteristics, different categories of S/N ratios have been defined. Three main categories are: nominal-the-better, smaller-the-better, and larger-the-better. In this study, smaller-the-better (STB) is considered to minimize the objective function value. For this case, the corresponding loss function for the objective of smaller-the-better can be expressed as follows:

$$ L_{STB} = RPD $$

(6)

where,

• L_STB is the loss function for smaller-the better

• RPD is the Relative Percentage Deviation used as performance measure in this study. It can be calculated as follows:

$$ RPD = \frac{Alg - Min}{Min} \times 100 $$

(7)

where: Alg is the makespan obtained by a given algorithm alternative on a given instance and Min is the lowest makespan obtained for the same instance. The objective is to maximize the S/N ratio. For minimization objectives, the S/N ratio is:

$$ S/N ratio = -10 \times log_{10}(RPD)^{2} $$

(8)

An analysis is carried out to identify which levels of the parameters are used which brings us closer to the desired value (Orthogonal arrays) and which maximize the S/N ratio. Taguchi methodology for parameter design can be applied in other algorithms such as genetic algorithm [13], particle swarm optimisation [1], and artificial bee colony algorithm [61] for NP-hard problems. They provide a cost-effective way of studying many factors in one experiment, at the expense of ignoring some high-order interactions. This is considered to be low risk, as high order interactions are usually insignificant and difficult to interpret anyway [58].

7 Experimental evaluation

Experimental results are conducted over two phases. We first performed parameter tuning using the Taguchi method and then experiments were conducted on well-known benchmarks with different level of f, proposed by Taillard [55]. The results described in the following sections have been obtained on a personal computer with 3.4 GHz Intel Core i7 and 8 GB of RAM memory.

7.1 Parameter design for DAHACO using Taguchi method

The choice of parameter values for metaheuristics highly influences the performance. Thus, an experiment is first conducted to fine tune the parameters of the proposed DAHACO. The algorithm includes four parameters, namely, α, β, ρ, and Q. In this work, five levels or values are considered for each parameter applied to Tai01 (15 jobs, 15 machines) proposed by Taillard [55]. The levels tested in this study are fixed based on Dorigo et al. [22] and are shown in Table 4. The number of ants is taken as 100 and the number of iterations in a cycle is fixed at 500. When five levels for each of the four parameters are considered, then the total number of experiments to be carried out for finding the optimum level of parameters results in 4⁵ experimental settings, i.e., 1,024. If each experiment is repeated five times, the total number of experiments required is 5,120. Obviously, this design becomes inefficient since it requires a large number of required trials. By applying the Taguchi method for robust design, the total number of experiments needed can be reduced to 125, i.e., 25 experiments, each with five replications as shown in Table 5.

Table 4 Parameters and their levels

Table 5 L₂₅ Orthogonal array

This experimental design of Taguchi is based on the technique of matrix experiments [40]. In matrix experiments, there is a set of experiments where the user changes the settings of various parameters. Orthogonal arrays are used to study the effect of various factors efficiently. The columns of orthogonal array are pairwise orthogonal, i.e., for every pair of columns, all combinations of factor levels occur an equal number of times. The columns represent the parameters to be studied and the rows represent the individual experiments. The number of rows gives the total number of experiments and the number of columns gives the maximum number of parameters that can be studied using the orthogonal array. Based on the number of parameters to be analysed and their levels, orthogonal array L₂₅ is selected in the present study. The assigned experimental array is shown in Table 6.

Table 6 Modified L₂₅ Orthogonal array

From Table 7, the overall mean for S/N ratio is found to be -6,57 dB. The level average response analysis is based on averaging the experimental results achieved at each level for each parameter. In the present study, each level of the parameter is contained in five experiments. The level-average response analysis is carried out by calculating the average of the results (i.e., S/N ratio) from the five experiments corresponding to each level of the parameter as shown in Table 8. Figure 6 shows graphically the effect of the four parameters on the objective function value. Since S/N ratio has the characteristic of the larger the better, the analysis of the results leads to the conclusion that the best combination of each parameter is α at level 2, β at level 1, ρ at level 3, and constant Q at level 5. The corresponding values are as follows: α₂ = 1, β₁ = 0, ρ₃ = 0.7, Q₅ = 10000. From the responses for the experiments, the range of S/N ratio is calculated as follows:

$$ Range = max S/N - min S/N $$

(9)

Table 7 Average of response and S/N ratio for different experiments

Table 8 Results of level average response analysis

Fig. 6

Graphical representation of the effect of parameters

7.2 Confirmation experiment

The purpose of the confirmation experiment is to validate the conclusions drawn from the experiments. Once the optimal level of the parameters is selected, the final step is to predict and verify the improvement of the performance characteristics using the optimal level of the parameters. The estimated value of the S/N ratio η_predicted with the optimal levels of parameter combination can be calculated with the help of following prediction equation:

$$ \eta_{predicted} = \eta_{m} + (\eta_{\alpha_{2}} - \eta_{m})+ (\eta_{\beta_{1}} - \eta_{m})+ (\eta_{\rho_{3}} - \eta_{m})+ (\eta_{Q_{5}} - \eta_{m}) $$

(10)

Where:

η_m: overall mean for S/N ratio

$\eta _{\alpha _{2}}$: S/N ratio for parameter α at designated level 2

$\eta _{\beta _{1}}$: S/N ratio for parameter β at designated level 1

$\eta _{\rho _{3}}$: S/N ratio for parameter ρ at designated level 3

$\eta _{Q_{5}}$: S/N ratio for parameter Q at designated level 5

A confirmation experiment is executed five times with the optimal combination of parameters. The actual value of the S/N ratio (η_actual) is calculated based on this experiment. The predicted value which is calculated using Eq. (10) and the actual value of S/N ratio are provided in Table 9.

Table 9 Confirmation Experiment data

where max S/N is the maximum of S/N ratio and min S/N is the minimum of S/N ratio for the parameter considered. A ranking of parameters is made based on the range values. It can be seen that parameter β has the largest effect on the response of the experiment and parameter Q has the least effect.

The predicted value of the S/N ratio with the optimal level of parameters is very close to the S/N ratio of the actual value. This validates the experiment for predicting the best levels of the parameters using the Taguchi method.

7.3 Evaluation of the DAHACO algorithm

The novelty of the proposed approach is twofold. The first contribution lies in the dynamic assignment of jobs to factories and the second offers a hybrid ant-based algorithm which integrates a local search in order to improve the solutions. To evaluate our proposed DAHACO and prove the effectiveness of introducing local search on the one hand and the dynamic assignment on the other hand, we have developed three different variants of ant-based algorithms to show the relevance and the influence of each improvement made on our DAHACO. Table 10 summarizes the 3 implemented versions:

• The first one, called ”ACO”, uses the ant colony system algorithm without any hybridization and a static assignment procedure (workload).

• The second one, called ”HACO” uses a hybrid ant colony system algorithm that integrates a local search procedure and a static assignment procedure (workload).

• The third one, called ”DAHACO” uses a dynamic assignment of jobs to factories and the hybrid ant colony system algorithm for the scheduling.

Table 10 The three implemented algorithms

The three algorithms were implemented and ran a certain number of times experimentally determined using the best parameters set determined previously α₂ = 1,β₁ = 0,ρ₃ = 0.7,Q₅ = 10000. We used instances from well-known benchmarks proposed by [55]. This benchmark includes 8 combinations for n and m, and 10 instances for each combination. Each instance is solved with different level of f (f = 2, 3, 4, 5, 6, 7) summing up 480 instances. The computational results are depicted from Tables 11, 12, 13, 14, and 15. Table 11 presents the value of makespan obtained by the 3 algorithms with the 480 instances. First, we notice that the total execution time of jobs on machines decreases when the number of plants increases. This is naturally explained by the fact that executing n jobs on f factories is faster than executing them on f/2 factories. This brings us directly back to thinking about the usefulness of factory distribution and its significant role in time saving. Table 12 summarizes the calculated Relative Percentage Deviation for the 480 instances, such as each value is the average value between different levels of f compared with the best value found by the three algorithms. As can be witnessed, the DAHACO outperforms the HACO and the ACO in almost all instances. Table 13 shows the Average Relative Percentage Deviation of the 3 algorithms grouped by n and m. As it can be seen, DAHACO beats the two other algorithms clearly, bringing down the average RPD to just 0.43 compared to a deviation of 7.95 for HACO algorithm and 35.42 for ACO. The smaller Average Relative Percentage Deviation shows that the proposed DAHACO is more robust and competitive than the HACO and ACO. Table 14 shows the average RPD of the three considered algorithms grouped by the number of factories f, i.e., each cell of the table contains the average RPD of 80 instances. It can be seen that DAHACO outperforms the other 2 algorithms in different factories levels and gets the best results for all combinations.

Table 11 Performance comparison of DAHACO, HACO and ACO

Table 12 Relative Percentage Deviation (RPD) of the 3 algorithms grouped by n and m

Table 13 Average relative percentage deviation of the 3 algorithms grouped by n and m

Table 14 Average RPD of the three algorithms grouped by f

Table 15 The computational time of the DAHACO (sec)

Figure 7 shows the average RPD of the tested algorithms vs. the number of factories. We can see that DAHACO algorithm outperforms the other algorithms regardless of the number of factories. As we can see, the DAHACO is stable with some factory as with several factories which is not the case for the other algorithms. But it is clear that when the number of factories increases, the performance of all algorithms is getting better. This observation is predictable because its logic that scheduling n jobs on two factories is costlier in terms of time than scheduling n jobs on three factories and so on. And this is what makes the distribution of factories a necessity in our days for the considerable gain of time.

Fig. 7

The average RPD of the tested algorithms versus the number of factories

The data in Table 15 show the influence of the number of factories on the computational time of the proposed DAHACO. We can notice that the computational time is interestingly reduced when we increase the number of factories. Our DAHACO is perfectly adapted to the distributed job shop scheduling problem and performs better in a distributed environment. It is important to mention that this is the first study that can deal with 10 factories in the DJSP. Figure 8 illustrates the curve of the computational time versus the number of factories. The efficiency compared to the 2 other algorithms is visible, especially, in the case of a small number of factories where job scheduling is more complicated because we have a larger number of jobs to execute in each factory. When the number of plants increases, the execution time is reduced considerably until reaching 0.07 sec for the 15x15 instance with 10 factories.

Fig. 8

The curve of the computational time versus the number of factories

To sum up, we can confirm that the proposed DAHACO outperforms two other algorithms in solving the DJSP. In fact, there are two important reasons for the rapid convergence and the good scheduling solutions of the proposed algorithm. The first is the variety of the assignment combinations, which offers more diversification thus exploiting new possibilities. The second is due to the local search procedure which enhances the capability of the algorithm to escape from local minimum and quickly guide the search to different regions of the solution space.

8 Conclusions and perspectives

This study proposed a novel dynamic assignment of jobs to factories, applied to a hybrid ant colony optimization algorithm combined with local search to solve the distributed job shop scheduling problem with makespan criterion. Firstly, the effective workload rule for assignment phase was combined with random permutations to create a dynamic assignment of jobs to factories. This step is very important to generate a diverse population for the ant-based algorithm. Moreover, a local search procedure is associated with ant-based algorithm in order to explore more search space and find better results. Furthermore, the Taguchi method for robust design is adopted for finding the optimum combination of parameters of the DAHACO algorithm. By applying the Taguchi method, the total number of experiments carried out for finding an optimum level of parameters has been reduced considerably. From the confirmation tests, a good agreement between the predicted S/N ratio and the actual S/N ratio is observed. This validates the proposed experiment based on the Taguchi method for parameter design.

The intensive experiments have been performed to evaluate our novel algorithm. Results proved that the effectiveness of the proposed DAHACO is able to reach best solutions. Besides, in order to verify the superiority of DAHACO, we have compared it with two ant-based algorithms with the use of the well-known instances proposed by Taillard [55]. Comparisons have proved that DAHACO can usually produce better solutions than other algorithms.

Even though this study proposed an effective DAHACO algorithm for the DJSP, there are some impediments that should be improved in future research work. In fact, this study has just considered the case when all factories are identical. This can be an idealization to the real problem, since it is rarely the case. On the basis of the satisfactory results obtained from this work and the limitations presented above, we plan to explore the following issues:

• Combining the proposed DAHACO algorithm with other methods in order to better explore the search space and improve the solution.

• Considering more complex real world constraints such as setup times and maintenance considerations.

• Investigating the applicability of the proposed approach to the multi-objective DJSP.

• Considering the case with non-identical factories.