Journal of Applied Sciences

Year: 2008 | Volume: 8 | Issue: 20 | Page No.: 3621-3629
DOI: 10.3923/jas.2008.3621.3629

Hybrid Electromagnetism-Like Algorithm for the Flowshop Scheduling with Sequence-Dependent Setup Times

M. Zandieh, F. Jolai, S.M.T. Fatemi Ghomi and M. Mirabi

Abstract: This study investigate the permutation flowshop scheduling problem in which there are sequence dependent setup times on each machine, commonly known as the SDST flowshop. The optimization criteria considered is the minimization of the makespan or C_max. Many heuristics and meta-heuristics have been successfully applied to this kind of problem before like genetic algorithm, tabu search and greedy algorithm and the objective of this study is to assess their effectiveness in a more realistic and complex environment. We present a hybrid electromagnetism-like (HEM) algorithm for the permutation flowshop scheduling with sequence dependent setup times that have shown superior performance against other meta-heuristics when applied to proposed problem. The proposed HEM algorithm benefits of a new concept named priority assigning to calculate electrostatic force and also it implements a new formulation for solution charge. Using a good approach for acquiring the initial solutions and also some effective local searches to finding neighborhood solutions are other novelties of the HEM. For evaluating the proposed algorithm we have coded several well-known algorithms for SDST flowshop. All methods including HEM are tested on the randomly instances and results indicate that HEM is very competitive with the existing best-performing algorithms.

Keywords: flowshop, Scheduling, hybrid meta-heuristics, sequence-dependent setup times and electromagnetism-like algorithm

INTRODUCTION

The flowshop scheduling problems (FSP) have been studied for over five decades. The classical flowshop problem with the makespan minimization criterion has always attracted the attention of researchers because of its applications in practice. The flowshop problem is easy to describe and formulate, yet computationally it is rather challenging. Therefore, this problem has inspired the development of a number of solution procedures (Ekşioğlu et al., 2008).

In an m machine flowshop, there are m stages in series, where there exist one or more machines at each stage. Each job has to be processed in each of the m stages in the same order. That is, each job has to be processed first in stage 1, then in stage 2 and so on. Processing times for each job in different stages may be different.

In the flowshop literature, one can find an overwhelming number of papers for the regular flowshop problem with the objective of minimizing the maximum completion time across all jobs. However, the sequence-dependent setup time flowshop problem (SDST flowshop problem in short) has attracted much less attention. Setup is sequence-dependent if its duration depends on both the current and the immediately preceding job and is sequence-independent if its duration depends only on the current job to be processed.

The objective in flowshop scheduling problems is to find a sequence for processing the jobs on the machines so that a given criterion is optimized. This yields a total of n! possible orderings of the operations on each machine and a total of (n!)^m possible processing sequences. In flowshop scheduling research usually only so called permutation sequences are considered, where the processing order of operations is the same for all machines. Here, we also adopt this restriction. In this study, we consider sequence dependent flowshop scheduling problem with the makespan minimization criterion.

Regarding the computational complexity, the SDST flowshop with the C_max objective has been shown to be NP-hard even when m = 1 and also when m = 2 and setups are present only on the first or second machine (Ruiz and Stutzle, 2008). For m = 1, the SDST flowshop is known to be a special case of the traveling salesman problem (TSP) that is also well known to be NP-hard which means that an efficient algorithm for solving the problem to optimality is unavailable.

Compared to the regular flowshop, on which hundreds of papers have been published, the literature on the SDST counterpart is scarce. In the pioneering work of Johnson, he author proposed a simple rule to obtain optimal sequences for the permutation flowshop problem (PFSP) with two machines (Ruiz et al., 2005). This study raised significant interest in the PFSP and was followed by several attempts for solving the PFSP with more than two machines. Due to the NP-completeness of the PFSP, researchers have mainly focused on the development of effective heuristics and meta-heuristics. For a recent review and evaluation of PFSP heuristics and metaheuristics, the reader can refer to Ruiz and Concepcion (2005). Stafford and Tseng (1990) reported minor corrections to the SG/SDST model and showed that the revised model (SGST/SDST) was robust with regard to the triangular inequality relationship of setup times. Rios-Mercado and Bard (1988) showed that the SGST/SDST model performed better than their new MILP model for the SDST flowshop. Tseng and Stafford (2001) extended the Stafford MILP model to solve both the SDST and the SDST/NIQ flowshop problems.

Ríos-Mercado and Bard (1999a) addressed the sequence dependent flowshop problem with makespan criterion (denoted as F_m/ST_sd/C_max). In the first study (Ríos-Mercado and Bard, 1999a), they presented a branch and bound algorithm, incorporating lower and upper bounds and dominance elimination criterion, to solve the problem. They provided test results for a wide range of problem instances. In the second study (Ríos-Mercado and Bard, 1999b), they proposed a heuristic for the same problem, which transforms an instance of the problem into an instance of the traveling salesman problem by introducing a cost function that penalizes both large setup times and bad fitness of a given schedule. Ruiz et al. (2005) proposed two genetic algorithms for the same problem and showed that their heuristics outperform that of Ríos-Mercado and Bard (1999b) and others. Ruiz and Stutzle (2008) presented two simple local search based iterated greedy algorithms and showed that their algorithms perform better than those of Ruiz et al. (2005). Ríos-Mercado and Bard (2003) studied the polyhedral structure of two different MIP formulations for the same problem. One is related to the asymmetric traveling salesman problem and the other is derived from an earlier proposed model. The two approaches were evaluated using a branch and cut algorithm, which indicated that the approach related to the asymmetric traveling salesman problem was inferior in terms of the computational time. Stafford and Tseng (2002) also proposed two MILP models, which are based on the study of Tseng and Stafford (2001), for the same problem. The MIP models proposed by Ríos-Mercado and Bard (2003) and Stafford and Tseng (2002) were independently developed and hence, remain to be compared to each other. Tseng et al. (2005) developed a penalty-based heuristic algorithm for the same problem and compared their heuristic with an existing index heuristic algorithm. The F_m/ST_sd/C_max problem was studied by Norman (1999) where there exist buffers with finite capacity between machines. He proposed a tabu search based heuristic and compared it with some other methods. Computational experiments showed the effectiveness of the tabu search approach.

Sun and Hwang (2001) addressed a related problem of F₂/ST_sd/C_max, where the setup times are present only on the second machine and the setup time of a job depends on k (k>1) immediately preceding jobs. They proposed a dynamic programming formulation and a genetic algorithm for the problem.

Allahverdi et al. (2008) have put together a much more updated and comprehensive review of scheduling research with setup times in which other relevant papers related to the SDST flowshop can be found.

Recently, EM algorithm has been used for optimization problems like scheduling. The approach starts with a randomly selected point from the feasible region for a given optimization problem. EM employs an attraction-repulsion mechanism to move points (particles) towards the optimal solution. Each point (particle) is treated as a solution and has a charge. A better solution contains a stronger charge. The charge of each point relates to the objective function to be optimized. A theoretical study of this EM analysis and a modification for convergence to the optimal solution are presented in Birbil et al. (Chang et al., 2007). However, this study only deals with continuous optimization problems. Debels et al. (2006) integrated a scatter search with EM for the solution of resource constraint project scheduling problems. This is the first study that includes an EM type methodology for the combinatorial optimization problem. Their experimental results show that the hybrid method of incorporating EM type analysis outperforms the current best solution available in literature.

Though EM algorithm is designed for solving continuous problems, the algorithm can be extended to solve scheduling problems. Chang et al. (2007) applied the random-key approach to represent a schedule incorporated with the EM methodology to solve a single machine scheduling problem and the objective is to minimize the total sum of earliness and tardiness penalties. In this study we apply priority assigning idea to incorporate EM algorithm for solving flowshop scheduling with sequence dependent setups and makespan criterion.

FORMULATION

We present a MILP model for this SDST flowshop scheduling problem that has been derived from the scheduling literature (Das and Canel, 2005 ).

Notation

Objective function: The objective is to minimize the makespan which is given by the completion time of the last job on the last machine.
Minimize makespan = c_nm

Constraint sets:

Constraint (1) is required to ensure that all jobs are scheduled and that the completion times of any job i on machine 1 is at least as great as the processing time for that job on the machine.

Processing of job i cannot begin on machine j, unless its processing is completed on the previous machine (j-1). Constraint (2) ensures that the completion time of job i on machine j, must be greater than the completion time of the same job on the previous machine (j-1), by at least the processing time required for job i on machine j.

where, k>i≥l,

and M is a very large No.

Constraints (3) and (4) ensure that for any given sequence of n jobs, only one of the constraints is binding. It assures the precedence relationship between jobs.

Constraints (5) and (6) ensure that only one job can follow a job in the schedule.

ELECTROMAGNETISM-LIKE ALGORITHM

Introduction of electromagnetism-like algorithm: Birbil and Fang propose a so-called electromagnetism-like (EM) optimization heuristic for unconstrained global optimization problems, i.e. the minimization of non-linear functions (Chang et al., 2007). In a multi-dimensional solution space where each point represents a solution, a charge is associated with each point. This charge is related to the objective function value associated with the solution. As in evolutionary search algorithms, a population, or set of solutions, is created, in which each solution point will exert attraction or repulsion on other points, the magnitude of which is proportional to the product of the charges and inversely proportional to the distance between the points (Coulomb`s Law). The principle behind the algorithm is that inferior solution points will prevent a move in their direction by repelling other points in the population and that attractive points will facilitate moves in their direction. This can be seen as a form of local search in Euclidian space in a population-based framework. The main difference with existing methods is that the moves are governed by forces that obey the rules of electromagnetism (Debels et al., 2006).

EM simulates the attraction-repulsion mechanism of electromagnetism theory which is based on Coulomb`s law. Each particle represents a solution and the charge of each particle relates to its solution quality. The higher charge the particle has the better solution quality of the particle. Moreover, the electrostatic force between two point charges is directly proportional to the magnitude of each charge and inversely proportional to the square of the distance between the charges. The fixed charge of particle i is shown as follows:

where, qⁱ is the charge of particle i, f(xⁱ),f(x^best) and f(x^k) denote the objective values of particle i, the best solution and particle k, respectively. Finally, m is the population size. The solution quality or charge of each particle determines the magnitude of an attraction and repulsion effect in the population. A better solution encourages other particles to converge to attractive valleys while a bad solution discourages particles to move toward this region. These particles move along with the total force and so diversified solutions are generated. The following formulation is the force of particle i:

The fundamental procedure of EM includes initialization, local search, calculating total force and moving the particles. The generic pseudo-code for the EM is as follows (Chang et al., 2007):

Algorithm 1: EM ()

Proposed hybrid electromagnetism-like algorithm: Flowshop scheduling problem can be regarded as a hard optimization problem. A simple EM may not perform well in this situation. Therefore, the EM developed in this study benefits of a new approach for the initial solutions, acceptance criteria and a local search. EM hybridizes with the modified NEH heuristic proposed by Ruiz et al. (2005). Besides the modified NEH, it also hybridizes with the local optimizer. We use three different search neighborhoods as pairwise interchange neighborhood, forward insertion neighborhood and backward insertion neighborhood (Gupta and Smith, 2006). One step in the local search is to decide whether the new sequence is accepted or not as the incumbent solution for the next iteration. A pure descent criterion would be to accept solutions with better objective function values. However, this acceptance criterion is prone to stagnation. As an alternative, we consider an acceptance criterion that is frequently used in simulated annealing (SA) algorithms. The hybrid system starts from determining whether a new solution obtained from one of initial solution using local search is accepted by SA or moved by EM.

The algorithm 2 is the pseudo code of the main procedure of the hybrid framework.

Algorithm 2: HEM ()

By line 9 we mean randomly generate a neighboring solution of x^New using either the interchange neighborhood, forward insertion neighborhood or backward insertion neighborhood. According to the algorithm 2 (algorithm 2, line 1), we initiate the solutions in the population. Then, the neighborhood search procedure is implemented before the EM procedure (algorithm 2, line 9). To determine which solution is good or inferior one, an average objective value B is calculated. Then, if the solution is not worse than B, it is accepted and substituted with the worst solution in the population (algorithm 2, lines 12-13). Otherwise, this solution is accepted with probability of e^-Δ/T and substituted with the worst solution (algorithm 2, line 17) or moved by modified EM algorithm with probability of 1-e^Δ/T (algorithm 2, line 19). After solutions are obtained, their makespan can be calculated. The best makespan is final solution. Finally, the initialization, priority assigning, solution charge, calculated total force and move are modified. Following discusses these topics in details.

Initialization: The initial solution for EM is ideally generated by a high performance constructive heuristic. For the sequence dependent flowshop scheduling with makespan criterion, we use the NEHT-RMB heuristic and a modified NEHT-RMB heuristic proposed by Ruiz et al. (2005) for the initialization of the population. Recall that NEH is an insertion heuristic, where at each step the next unscheduled job is tentatively inserted in each possible position of some partial solution. The job is then finally inserted into the position where the objective function takes the lowest value. For executing such an insertion heuristic, the jobs need to be ordered in some way. For more details how this is done in NEHT-RMB and modified NEHT_RMB (Ruiz et al., 2005). We obtain m initial solutions based on this method.

Priority assigning: In this step we assign one random variable xⁱ_k between 0 and 1 to each job k in each solution i. For example consider one problem with 4 jobs numbered 1 to 4. Assume the second initial solution is represented by (1, 4, 3, 2). It means job 1 is the first job in the sequence, job 4 is second, job 3 is third and job 2 is the last. We assign one random variable between 0.75 and 1 to job 1, one between 0.5 and 0.75 to job 4, one between 0.25 and 0.5 to job 3 and finally one between 0 and 0.25 to job 2. One of the results can be shown as follows:

Therefore x² = (0.89, 0.54, 0.48, 0.11). Also if there are n jobs in each sequence, one random variable between (n-1)/n and n is assigned to the first job, one between (n-2)/n and (n-1)/n to the second and so on. Finally random variable of the last job is between 0 and 1/n. Hence if there are m initial solutions, there are m random variables for each job i (i = 1,…,n).

Solution charges, electrostatic force and move: In the previous section it was described that each solution i has one vector of random variable denoted as xⁱ including n random variables from xⁱ_l to xⁱ_n. Therefore C_max(xⁱ) is equivalent to C_max(solution(i)). Let the force exerted on neighborhood solution (denoted as x^Nei in algorithm 2, line 9) by current solution i use the fixed charge of q_i (related to the fixed charge of solution i indicated in 7). We have:

where B is the average makespan of all solutions i (i = 1,…,m). It is clear that

After the q_i is obtained, we calculate the force on x^Nei by other solutions i. To calculate the electrostatic forces imposed by all solution for x^Nei, we obtain electrostatic forces imposed to each particle of x^Nei (particle means x₁^Nei, x₂^Nei,…, x_n^Nei) as follows (related to the force of particle i indicated in 8):

Therefore,

We can set upper and lower bounds for x_k^New. If x_k^New is greater than upper bound or less than lower bound, it is substituted with the value of bounds. Hence we have one x^New with new particles. We sort all jobs in x^New based on its x_k^New in decreasing order and obtain a new sequence of jobs corresponding x^New. Thus solution x^Nei moves to x^Nei+F_k^New. For example if the solution related to x^Nei is represented by (2, 1, 4, 3) and new particles of x^New are (0.22, 0.52, 0.43, 0.85), the new solution will be (3, 1, 4, 2). Therefore to obtain x^New (algorithm 2, line 19), we follow algorithm 3.

Algorithm 3: Move neighborhood solution by EM ()

Finally, in order to maintain the feasibility of each solution, we check the boundary feasibility by the algorithm 4.

Algorithm 4: Check boundary ()

Stopping criterion: The stopping criterion of the EM could be a maximum number of iterative cycles, specified CPU time limit, or maximum number of cycles between two improvements of the global best solution. In this study, we use a given number of iterative cycles as the stopping criterion. Therefore, in our experiment setting, the algorithm will terminate when a given number of cycles has been executed. This loop is executed for Itemax = 2500 iterations.

COMPUTATIONAL EXPERIMENTS

Here, the proposed hybrid electromagnetism (referred to as HEM) with the other metaheuristics is compared. These are: iterated greedy heuristic by Ruiz and Stutzle (2008) that will be denoted as IG, hybrid genetic algorithm by Ruiz et al. (2005) that will be denoted as HGA and the tabu search algorithm by Ekşioğlu et al. (2008), which will be referred to as TS. For evaluating the different algorithms we used the performance measure stated as:

where, Heu_sol is the makespan obtained by a given algorithm and Best_sol is the makespan of the best solution obtained by all algorithms. The platform of our experiments is a personal computer with a Pentium-III 1.2 Hz CPU and 256 MB RAM. The programs are coded in MATLAB. All algorithms are compared using different problem sizes (n = 10, 20, 30, 40, 50, 100, 200 and m = 5, 10, 15, 20). For each class of the problem defined by given (n, m), 10 instances of problem are randomly generated. Thus we obtain a total of 280 problem instances. Processing time and setup time are given from Uniform random U(1, 99) and U(1, 9) discrete distributions, respectively. The numerical results are averaged through each ten instances.

The average, minimum and maximum PM values for all algorithms are shown in Table 1. The `Min` labeled columns show, in subscript, the number of instances for which the algorithm solution was equal to the corresponding Best_sol. In `Average` column we show two sub columns including average PM and average time to solve all 10 instances.

With respect to the solutions gained, Table 1 demonstrates that the algorithms have the rank of: 1. HEM, 2. IG, 3. HGA and 4. TS. Figure 1 shows the difference of Heu_sol-Best_sol for each heuristics in each instance.

It is noticeable that the fastest algorithm is HGA (but gained solutions are not so good) and HEM is a little slower than IG.

Now for more detailed comparison, two algorithms of HEM and IG are considered. In this step, it is desired to stop both algorithms at the same CPU time. The value of this CPU time has been taken the minimum CPU time between two algorithms in Table 1. For example the common CPU time for the first class of problem (n = 10, m = 5) is min (3.5, 2.08) = 2.08. We test the hypothesis that the population corresponding to the differences has mean μ zero.

Specifically, we test the (null) hypothesis μ = 0 against the alternative μ > 0. We assume that the makespan difference is a normal variable and choose the significance level α = 0.05. If the hypothesis is true, the random variable:

Ave: Average, MS: Makespan, SD: Standard deviation, Sig: Significant, Each class of problem contains 10 independent instances

has a t distribution with:

degrees of freedom. The critical value of c is obtained from the relation Prob (T > c) = α = 0.05. For example, the first entry in Table 2 corresponds to the sample size = n₁ = n₂ = 10, μ₀ = 0, sample mean for IG and HEM are = 762.70 and = 763.20, respectively. Sample standard deviation for IG and HEM are S₁ = 2.85 and S₂ = 3.81, respectively. Since t = 1.74 > T = 0.33, we conclude that the difference is not statistically significant. Table 2 displays HEM outperforms IG in all cases except seven classes of problem (classes 1, 2, 5, 6, 11, 13 and 23) and four of differences are significant (classes 2, 5, 13 and 23). Also in cases that HEM yields better results, all differences are significant except four classes (12, 15, 18 and 25). In fact HEM outperforms IG in 75% of cases and significantly outperforms in 61%.

CONCLUSIONS

By using priority assigning the EM algorithm is able to be applied in solving the scheduling problem. To improve the performance of the EM algorithm, a hybrid method is developed in this research which, the EM benefits of a new approach for the initial solutions, acceptance criteria and a local search. The purpose of this hybrid method is to take advantage of the EM algorithm, SA algorithm and local search.

We study the flowshop scheduling problem in sequence dependent condition to challenge a large number of real world problems. FSP is a hard optimization problem. To solve this problem, HEM is used. Computational results demonstrate the performance of our algorithm compared to some of the strong algorithms recently developed. It is noticeable when the differences between HEM and GA (strongest algorithm between all previous algorithms) are concerned, most of them are also significant in the level α = 0.05. It demonstrates the significant strength of HEM to solve scheduling problems compared to previous developed algorithm.

REFERENCES