A Heuristic search algorithm for flow-shop scheduling.

This article describes the development of a new intelligent heuristic search algorithm ([IHSA.sup.*]) which guarantees an optimal solution for flow-shop problems with an arbitrary number of jobs and machines provided the job sequence is constrained to be the same on each machine. The development is described in terms of 3 modifications made to the initial version of [IHSA.sup.*]. The first modification concerns the choice of an admissible heuristic function. The second concerns the calculation of heuristic estimates as the search for an optimal solution progresses, and the third determines multiple optimal solutions when they exist. The first 2 modifications improve performance characteristics of the algorithm and experimental evidence of these improvements is presented as well as instructive examples which illustrate the use of initial and final versions of [IHSA.sup.*].

Keywords: Admissible heuristic function, dominance, flow-shop scheduling, optimal heuristic search algorithm

Povzetek: Opisan je nov hevristicni iskalni algoritem [IHSA.sup.*].

1 Introduction

The optimal solution to the flow-shop scheduling problem involving n jobs and m machines determines the sequence of jobs on each machine in order to complete all the jobs on all the machines in the minimum total time (i.e. with minimum makespan) where each job is processed on machines 1, 2, 3...., m, in that order. The number of possible schedules is [(n!).sup.m] and the general problem is NP-hard. For this general problem it is known that there is an optimal solution where the sequence of jobs is the same on the first two machines and the sequence of jobs is the same on the last two machines [4]. Consequently, for the general problem with 2 of 3 machines there is an optimal solution where the jobs ate processed in the same sequence on each machine and the optimal sequence is among only n! job sequences. However, in the optimal solution for the general problem with more than 3 machines the jobs ate not necessarily processed in the same sequence on each machine. This article is concerned with the development of an algorithm ([IHSA.sup.*]) which is guaranteed to find an optimal solution for flow-shop scheduling problems involving an arbitrary number of jobs and machines where the problem is constrained so that the same job sequence is used on each machine.

Early research on flow-shop problems is based mainly on Johnson's theorem, which gives a procedure for finding an optimal solution with 2 machines, or 3 machines with certain characteristics [20], [21]. Other approaches for the general problem include integer linear programming and combinatorial programming, which use intensive computation to obtain optimal solutions and are generally not feasible from a computational standpoint because the number of variables increases exponentially as the number of machines increases [35]. Branch-and-bound methods use upper or lower bounds to guide the direction of the search. Depending on the effectiveness of the heuristic and the search strategy this method may return only near optimal solutions but with long computation time [19], [29], [30], [36]. Heuristic methods have received significant attention [9], [18], [26], [27], [37], [40], [41], [42]. However, even the most powerful heuristic method to-date, the NEH heuristic developed by Nawaz et al. [31] fails to reach solutions within a reasonable bound of the optimal solution in some difficult problem cases [47]. A review of approaches by Zobolas et al. [47] indicates that there has been strong interest in artificial intelligence optimization methods referred to as metaheuristics including: Simulated Annealing [32], [34]; Tabu Search [11]; Genetic Algorithms, which may give an optimal solution but due to the evolutionary nature of this approach the computation time is unpredictable [2], [3], [5], [38]; Fuzzy Logic [13], [14], [15], [16], [17]; Ant Colony and Particle Swarm Optimization [28], [43]; Iterated Local Search [39]; and Differential Evolution [33]. The strong interest in metaheuristics generated the development of hybrid approaches which combine different components of more than one metaheuristic [1].

An initial version of a new intelligent heuristic search algorithm ([IHSA.sup.*]) for flow-shop problems with an arbitrary number of jobs and machines and subject to the constraint that the same job sequence is used on each machine has been proposed in [6], [7], [8]. It is based on the Search and Learning [A.sup.*] algorithm presented in [44], [45], [46] which is a modified version of the Learning Real Time [A.sup.*] algorithm in [24], [25] which is, in turn, a modified version of the original [A.sup.*] algorithm [10], [12].

At the start of the search using [IHSA.sup.*] different methods are considered for computing estimates for the total time needed to complete all of the jobs on all of the machines assuming in turn that each of the jobs is placed first in the job sequence. It is shown that if there are m machines then there are m different methods that should be considered. Among the estimates associated with each method the smallest estimate is referred to as the value of the heuristic function that is associated with that method and it identifies the job that would be placed first in the job sequence at the start of the search if that method is used. If the value of the heuristic function does not exceed the minimum makespan for the problem then the heuristic function is said to be admissible and in such cases [IHSA.sup.*] is guaranteed to find an optimal solution provided the job sequence is the same on each machine. The proof of this result for [IHSA.sup.*] is given in [8] and is similar to that given in [22] and [23] in relation to the [A.sup.*] algorithm from which [IHSA.sup.*] is derived. The term "heuristic" is used in the title of [IHSA.sup.*] because the optimality of the algorithm and its performance depends on the selection of an appropriate admissible heuristic function at the start of the search and this function continues to guide the search to an optimal solution.

The purpose of this article is to describe the development of [IHSA.sup.*] which has occurred since the initial version was first presented in [6]. For simplicity of presentation the development is described in terms of problems involving an arbitrary number of jobs with 3 machines. However, the notations, definitions, proofs, and concepts presented may be extended to problems involving more than 3 machines if the job sequence is the same on each machine and these extensions are noted at the appropriate places throughout the presentation. Three significant modifications have been made to the initial version of [IHSA.sup.*]. The first concerns the choice of an admissible heuristic function at the start of the search. The second concerns the calculation of heuristic estimates as the search progresses, and the third determines multiple optimal solutions when they exist.

Following an introduction to the initial version of [IHSA.sup.*] each of the 3 modifications is presented. Experimental evidence of improvements in performance characteristics of the aigorithm which result from the first 2 modifications is provided in the Appendix and discussed in section 5. Instructive examples are given to illustrate the initial and final versions of [IHSA.sup.*] and these have been limited to 3 machines in order to allow interested readers to familiarize themselves with the algorithm by reworking the examples by hand. The proofs of results related to the modifications are presented in the Appendix.

2 The initial version of [IHSA.sup.*]

Before presenting the initial version of the algorithm notations and definitions are introduced and the state transition process associated with [IHSA.sup.*] is described together with the features of search path diagrams which are used to illustrate the development of an optimal job sequence.

2.1 Notations and definitions

The following notations and definitions are introduced fora flow-shop problem involving n jobs [J.sub.i], [J.sub.2]...., [J.sub.n] and 3 machines [M.sub.1], [M.sub.2], [M.sub.3].

[O.sub.ij] is the operation performed on job [J.sub.i] by machine [M.sub.j] and there are 3n operations. For job [J.sub.i] the processing times [a.sub.i], [b.sub.i], and [c.sub.i] denote the times required to perform the operations [O.sub.i1], [O.sub.i2], and [O.sub.i3], respectively and these processing times ate assumed to be non negative integers. If [O.sub.ij] has commenced but has not been completed then [p.sub.ij] represents the additional time required to complete [O.sub.ij] and at the time when [O.sub.ij] starts [p.sub.ij] is one of the values among [a.sub.i], [b.sub.i], or [c.sub.i]. The sequence [PHI].sub.st] = {[J.sub.s] ..., [J.sub.1]} represents a sequence of the n jobs with [J.sub.s] scheduled first and [J.sub.t] scheduled last. T([[phi].sub.st]) is the makespan for the job sequence [[phi].sub.st] and S([[phi].sub.st]) is the time at which all of the jobs in [[phi].sub.st] are completed on machine [M.sub.2].

Using these notations and definitions Figure 1 illustrates the manner in which the operations associated with the job sequence [[phi].sub.st] are performed on the 3 machines.

[FIGURE 1 OMITTED]

A method for calculating an estimate of the total time to complete all of the n jobs on all of the 3 machines when job [J.sub.i] is the first job in the sequence is given by [a.sub.i] + [b.sub.i] + [n.summation over (i=1)] [c.sub.i]. Then the heuristic function associated with this method is [H.sub.3] where, [H.sub.3] = min [[a.sub.1] + [b.sub.1], [a.sub.2] + [b.sub.2], ..., [a.sub.s] + [b.sub.s], ..., [a.sub.n] + [b.sub.n]] + [n.summation over (i=1)] [c.sub.i]. (1)

If min [[a.sub.1] + [b.sub.1], [a.sub.2] + [b.sub.2], ..., [a.sub.s] + [b.sub.s], ..., [a.sub.n] + [b.sub.n]] = [a.sub.s] + [b.sub.s] then [H.sub.3] = [a.sub.s] + [b.sub.s] + [n.summation over (i=1)] [c.sub.i] and job [J.sub.s] would be scheduled first in the job sequence. It is seen from Figure 1 and proved in the Appendix that [H.sub.3] is an admissible heuristic function and [H.sub.3] is the heuristic function that was used in the initial version of the [IHSA.sup.*].

2.2 The state transition process

The procedure for developing the optimal job sequence using [IHSA.sup.*] proceeds by selecting an operation which may be performed next on an available machine. At the time that selection is made each of the 3n operations is in only one of 3 states: the not scheduled state; the in-progress state; or the finished state and the operation which is selected is among those in the not scheduled state. Operations not in the finished state are referred to as incomplete. A state transition occurs when one or more of the operations move from the in-progress state to the finished state and at any time the state level is the number of operations in the finished state.

[IHSA.sup.*] describes the procedure which takes the state transition process from one state level to the next and the development of the optimal job sequence is illustrated graphically using search path diagrams.

2.3 Search path diagrams

A search path diagram consists of nodes drawn at each state level with one of the nodes connected to nodes at the next state level. Each node contains 3 cells which are used to display information about operations on the machines [M.sub.1], [M.sub.2], and [M.sub.3], respectively. When a state transition occurs one of the nodes at the current state level is expanded and it is connected to the nodes at the next state level where each node represents one of the different ways of starting operations that ate in the not scheduled state. At each of these nodes a cell is labeled with [J.sub.i] to indicate that the operation [O.sub.ij] is either in progress or is one of the operations that may start on [M.sub.j], and [p.sub.ij] which is the time needed to complete [J.sub.i] on [M.sub.j]. A blank cell indicates that no operation can be performed on that machine at this time.

Near each node the heuristic estimate (h) associated with the node is recorded. The heuristic estimate is calculated using the heuristic function chosen in Step 1 of the algorithm in conjunction with the procedure used in Step 2. It is an estimate of the time required to complete the operation at the node identified by the procedure in Step 2 as well as all of the other operations that are not in the finished state. At each state level the node selected for expansion is the one which has associated with it the minimum heuristic estimate among all of the estimates for the nodes at that state level. Near this selected node the value of f = h + k is recorded where the edge cost (k) is the time that has elapsed since the preceding state transition occurred.

A comparison is made between f and h' where h' is the minimum heuristic estimate at the preceding state level. Based on that comparison the search path either backtracks to the node expanded at the preceding state level or moves forward to the next state level. If backtracking occurs then the value of h' is changed to the current value of f and the search moves back to that node. If the path moves forward then the value of the edge cost (k) is recorded below the expanded node. For convenience of presentation a new search path diagram is drawn when backtracking in the previous diagram is completed.

At state level 0 there are n root nodes corresponding to the number of jobs. The final search path diagram represents the optimal solution and traces a path from one of the root nodes, where the minimum makespan is the value of h or f, to a terminal node where h = f = 0. The optimal job sequence can be read by recording the completed operations along the path from the root node to the terminal node.

2.4 [IHSA.sup.*] (initial version)

Step 1: At state level 0 expand the node identified by calculating the value of [H.sub.3] from (1), and move to the nodes at state level 1. If more than one node is identified then break ties randomly.

For example, if [H.sub.3] = [a.sub.s] + [b.sub.s] [n.summation over (i=1)] [c.sub.i] then the

node with [J.sub.s] and [a.sub.s] recorded in the first cell is the node to be expanded.

Step 2: At the current state level if the heuristic estimate of one of the nodes has been updated by backtracking use the updated value as the heuristic estimate for that node and proceed to Step 3. Otherwise, calculate a heuristic estimate for each node at the current state level using Procedure 1 and proceed to Step 3.

Procedure 1 is described below.

Step 3: At the current state level select the node with the smallest heuristic estimate. If it is necessary then break ties randomly.

The smallest heuristic estimate is admissible and underestimates the minimum time required to complete all of the incomplete jobs on all of the machines.

Step 4: Calculate f = h + k where h is the smallest heuristic estimate found in Step 3 and k (edge cost) is the time that has elapsed since the preceding state transition occurred.

Step 5: If f > h', where h' is the minimum heuristic estimate calculated at the preceding state level, then backtrack to that preceding state level and increase the value of h' at that preceding node to the current value of f and repeat Step 4 at that node.

Step 6: If f [less than or equal to] h then proceed to the next state level and repeat from Step 2.

Step 7: If f = 0 and h = 0 then Stop.

Procedure 1 is used in Step 2 to calculate a heuristic estimate for each node at the current state level:

(a) If cell 1 is labelled with [J.sub.i] then the heuristic estimate h for the node is based on the operation in cell 1 and is given by,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (2)

(b) If cell 1 is blank, and cell 2 is labelled with [J.sub.i] then the heuristic estimate h for the node is based on the operation in cell 2 and is given by,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

(c) If cell 1 and cell 2 are blank, and cell 3 is labelled with [J.sub.i] then the heuristic estimate h for the node is based on the operation in cell 3 and is given by,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

In Procedure 1 the calculation of a heuristic estimate for a node is based on an operation in only one of the cells at the node and operations in the other 2 cells are not taken into account. For example, if cell 1 is not blank then the estimate is based only on the operation in cell 1. If cell 1 is blank then the estimate is based only on the operation in cell 2. An operation in cell 3 is only considered if the other 2 cells are blank.

The following example illustrates the use of the initial version of [IHSA.sup.*] to solve the flow-shop problem given in Table 1. For instructional purposes the problem is deliberately simple with only 3 machines and 3 jobs because it is intended to provide readers with an opportunity to become familiar with the algorithm using an example that can be reworked easily by hand.

For illustrative purposes only the first search path diagram is presented in Figure 2.

At the start of the search [H.sub.3] = 26. In total 5 search path diagrams are required to find the optimal sequence [J.sub.1][J.sub.2][J.sub.3] with a minimum makespan of 26. Twenty nodes are expanded, 16 backtracking steps are required, and 43 steps of the algorithm are executed.

3 Modifications to the initial version of [IHSA.sup.*]

The first modification determines the best heuristic function to use for a given problem and affects Step 1 of the algorithm. The second modification affects Procedure 1 used in Step 2 and the third modification affects Step 7 and enables multiple optimal solutions to be found when they exist.

3.1 A modification to step 1

In the Appendix a set of 6 heuristic functions are derived for the case of 3 machines and proofs of the admissibility of these functions are presented. It is shown that among this set of 6 heuristic functions the one which is admissible and has a value which is closest to the minimum makespan will be the one among [H.sub.1], [H.sub.2], and [H.sub.3] which has the largest value where,

[FIGURE 2 OMITTED]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

where: [u.sub.1] = min[[c.sub.2], [c.sub.3], ..., [c.sub.n]]; [u.sub.k] = min[[c.sub.1], [c.sub.2], ..., [c.sub.k-1], [c.sub.k-1], ..., [c.sub.n]], for 2 [less than or equal to] k [less than or equal to] n - 1; and [u.sub.n] = min[[c.sub.1], [c.sub.2], [c.sub.3], ..., [c.sub.n-1]].

Choosing the admissible heuristic function among [H.sub.1], [H.sub.2], [H.sub.3] with the largest value in the first step of the algorithm ensures that the search begins with an estimate of the minimum makespan that is not greater than it but is the closest to it. This choice is expected to reduce the need for backtracking at a subsequent stage of the search since backtracking takes the search back to a previous node and increases the heuristic estimate at that node to a value which is admissible but closer to the minimum time required to complete all of the incomplete jobs on all of the machines.

Consequently, Step 1 in the initial version of [IHSA.sup.*] is modified and becomes:

Step 1: At state level O, from (5), choose the admissible heuristic function among [H.sub.1], [H.sub.2], and [H.sub.3] which has the largest value and if necessary break ties randomly. In the case where machine [M.sub.j] dominates the other machines select [H.sub.j]. Expand the node identified by the chosen admissible heuristic function and move to the nodes at state level 1. If more than one node is identified then break ties randomly.

The example in section 4 below illustrates the use of the modification to Step 1 in a simple problem which enables the reader to rework the example by hand. In the Appendix it is shown that in the particular case where machine [M.sub.j] dominates the other machines then the best admissible heuristic function among [H.sub.1], [H.sub.2], and [H.sub.3] is [H.sub.j] and it has a value which is greater than the value of either of the other two functions by at least (n - 1)(n - 2) where n is the number of jobs. Thus in the case of a dominant machine in the first step of the algorithm there is no need to calculate each of the values of [H.sub.1], [H.sub.2], and [H.sub.3] in order to choose the one with the largest value. Instead, it is known that it will be Hi if machine [M.sub.j] is the dominant machine.

In the case where there are m machines and m > 3 it is shown in the Appendix that the best admissible heuristic function to use in the first step of the algorithm is the one among [F.sub.1], [F.sub.2], ..., [F.sub.m] which has the largest value and if m = 3 then [F.sub.1] = [H.sub.1], [F.sub.2] = [H.sub.2,] and [F.sub.3]. = [H3.sub.3]. Experimental evidence of improvements in performance characteristics of the algorithm which result from using the modification to Step 1 is presented in the Appendix Table Al and is discussed below in section 5.

3.2 A modification to step 2

The second modification to the initial version of [IHSA.sup.*] concerns the calculation of heuristic estimates at nodes on the search path when the search has commenced. It is based on the principle that when heuristic estimates for the nodes at the same state level are being calculated in Step 2 it is desirable to obtain the largest possible estimate at each of these nodes before selecting the node with the smallest estimate as the node to be expanded. The larger the value of this smallest estimate then the less likely it is that the search will need to backtrack and this is expected to improve the performance characteristics of the algorithm. As noted above, the use of Procedure 1 in Step 2 in the initial version of [IHSA.sup.*] gives a heuristic estimate for a node based on an operation in only one of the cells while operations in the other 2 cells are not taken into account.

The second modification affects Procedure 1 and involves calculating heuristic estimates [h.sub.1],[h.sub.2], and [h.sub.3] at a node for cells 1, 2, and 3, respectively. Then max[[h.sub.1], [h.sub.2], [h.sub.3]] is used as the heuristic estimate (h) for the node. This is done for each node at the current state level and then, as before, in Step 3 the minimum estimate among these estimates identifies the node to be expanded.

Consequently, Procedure 1 is replaced by the following Procedure 2:

In Step 2 of the algorithm for a node at the current state level,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (6)

Procedure 2 refers to calculations specified in Procedure 1 which incorporate currently the heuristic function [H.sub.3]. However, (2), (3), and (4) are easily changed to incorporate [H.sub.1] or [H.sub.2] for problems where one of these functions has been selected using the modification to Step 1 of the algorithm. For example, if [H.sub.2] is used then (3) and (4) are not changed but (2) becomes,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where, [B.sub.1] is the sum of the values of [b.sub.k] for all values of k [not equal to] i such that [O.sub.k1] is in the not scheduled state and [w.sub.i] is the smallest value of [c.sub.k] for all values of k [not equal to] i such that [O.sub.k1] is in the not scheduled state.

Procedure 2 produces the same heuristic estimate as Procedure 1 if and only if one of the following 3 conditions is satisfied: [h.sub.1] = max[[h.sub.1], [h.sub.2], [h.sub.3]]; [h.sub.2] = max[[h.sub.1], [h.sub.2], [h.sub.3]] and cell 1 is blank; or [h.sub.3] = max[[h.sub.1], [h.sub.2], [h.sub.3]] and cells 1 and 2 are blank. Under any other conditions Procedure 2 will produce a heuristic estimate at a node which is larger than the estimate given by Procedure 1. Consequently, using Procedure 2 will never produce an estimate that is less than the estimate produced by Procedure 1 and in practice the estimate using Procedure 2 is usually larger and leads to a reduction in backtracking.

Using Procedure 2 in the initial version of [IHSA.sup.*] modifies Step 2 and it becomes:

Step 2: At the current state level if the heuristic estimate of one of the nodes has been updated by backtracking use the updated value as the heuristic estimate for that node and proceed to Step 3. Otherwise, at each node use Procedure 2 to calculate [h.sub.1], [h.sub.2], [h.sub.3] and use max[[h.sub.1], [h.sub.2], [h.sub.3]] as the heuristic estimate for the node.

If there are m machines and m > 3 then there are m cells at each node and an estimate is calculated for each cell by extending (6) and (2), (3), (4) to accommodate the heuristic function [F.sub.j] (see Appendix) used in Step 1 of the algorithm.

The example in section 4 below illustrates the use of the modification to Step 2 in a simple problem which enables the reader to rework the example by hand. Experimental evidence of additional improvements in performance characteristics of the algorithm from using the modifications to Steps 1 and 2 together is presented in the Appendix Table Al and is discussed below in section 5.

3.3 A modification to step 7

For some problems there are multiple optimal solutions and it is often important in practical situations to be able to find all of the optimal solutions since it may be required to find an optimal solution that also satisfies other criteria. For example, an optimal solution may be sought which also has the least waiting time for jobs that are queuing to be processed.

When [IHSA.sup.*] is implemented there are 2 situations which indicate the possible existence of multiple optimal solutions. The first situation occurs when there is more than 1 node at a state level with the smallest heuristic estimate. In this case the ties are broken randomly and one of the nodes is selected for expansion and the search continues and produces an optimal solution. At the completion of the search returning to that state level and selecting for expansion one of the other nodes which were not selected when the ties were broken may lead to a different optimal solution. The second situation occurs when at the completion of the search for an optimal solution one or more of the nodes at state level 0 has a heuristic estimate that is less than or equal to the minimum makespan. In this case returning to those nodes and beginning the search again may produce different optimal solutions.

The modification to the initial version of [IHSA.sup.*] that enables multiple optimal solutions to be determined affects Step 7. This modification is different from the previous 2 modifications in that it does not improve the performance characteristics of the algorithm but instead it is intended to find multiple optimal solutions if they exist.

Consequently, Step 7 becomes:

Step 7: If f = 0 and h = 0 then an optimal solution has been found. If along the path representing the optimal solution there is a node which was selected for expansion by breaking ties randomly among nodes at the same state level with the same minimum heuristic estimate then return to that state level and repeat from Step 2 ignoring any node that was selected previously for expansion as a result of breaking ties. If any of the values of h at root nodes (state level O) is less than or equal to the minimum makespan then return to state level 0 and repeat from Step 2 ignoring root nodes that lead to a previous optimal solution. Otherwise, Stop.

4 The final version of [IHSA.sup.*]

The final version of [IHSA.sup.*] incorporates each of the 3 modifications:

Step 1: At state level O, from (5), choose the admissible heuristic function among [H.sub.1], [H.sub.2], and [H.sub.3] which has the largest value and if necessary break ties randomly. In the case where machine [M.sub.j] dominates the other machines select [H.sub.j]. Expand the node identified by the chosen admissible heuristic function and move to the nodes at state level 1. If more than one node is identified then break ties randomly.

Step 2: At the current state level if the heuristic estimate of one of the nodes has been updated by backtracking use the updated value as the heuristic estimate for that node and proceed to Step 3. Otherwise, at each node use Procedure 2 to calculate [h.sub.1], [h.sub.2], [h.sub.3] and use max[[h.sub.1],[h.sub.2], [h.sub.3]] as the heuristic estimate for the node. Step 3: At the current state level select the node with the smallest heuristic estimate. If it is necessary then break ties randomly.

Step 4: Calculate f = h + k where h is the smallest heuristic estimate found in Step 3 and k (edge cost) is the time that has elapsed since the preceding state transition occurred.

Step 5: If f > h, where h is the minimum heuristic estimate calculated at the preceding state level, then backtrack to that preceding state level and increase the value of h at that preceding node to the current value of f and repeat Step 4 at that node.

Step 6: If f [less than or equal to] h then proceed to the next state level and repeat from Step 2.

Step 7: If f = 0 and h = 0 then an optimal solution has been found. If along the path representing the optimal solution there is a node which was selected for expansion by breaking ties randomly among nodes at the same state level with the same minimum heuristic estimate then return to that state level and repeat from Step 2 ignoring any node that was selected previously for expansion as a result of breaking ties. If any of the values of h at root nodes (state level O) is less than or equal to the minimum makespan then return to state level 0 and repeat from Step 2 ignoring root nodes that lead to a previous optimal solution. Otherwise, Stop.

If there are m machines and m > 3 then Steps 1 and Step 2 need to be modified in accordance with the discussion of this case presented in sections 3.1 and 3.2 above.

The simple instructive example which was used to illustrate the initial version of [IHSA.sup.*] (see Table 1) is used again to illustrate the final version of [IHSA.sup.*]. For this problem, from (5), [H.sub.3] = 26 > [H.sub.1] = 19 > [H.sub.2] = 16 and using the modification to Step 1 of the algorithm [H.sub.3] is used in Step 1 of the algorithm. Since no backtracking is necessary an optimal solution for the problem requires only 1 search path diagram which is shown in Figure 3 where the optimal solution has a minimum makespan of 26 and a job sequence [J.sub.1], [J.sub.2], [J.sub.3]. At each node the search path diagram shows the estimates [h.sub.1], [h.sub.2], [h.sub.3] and the heuristic estimate for the node h = max[[h.sub.1], [h.sub.2], [h.sub.3]] which result from the use of the modification to Step 2 of the algorithm.

It is noted that the minimum heuristic estimate at state level 1 is 24 at both of the nodes at that state level. In Step 3 of the algorithm the tie was broken randomly and the node at which job [J.sub.2] is scheduled on machine [M.sub.1] was selected for expansion. In Step 7, although for simplicity a second search path diagram has not been drawn, the search returns to state level 1 and instead the node at which job [J.sub.3] is scheduled on machine [M.sub.1] is expanded. This gives a second optimal solution where the job sequence is [J.sub.1], [J.sub.3], [J.sub.2].

[FIGURE 3 OMITTED]

5 Experimental evidence of improvements in performance

Experimental evidence of improvements in performance characteristics of [IHSA.sup.*] using the modifications to Steps 1 and 2 is presented in Appendix Table Al. The characteristics considered are: the number of nodes expanded; the number of backtracking steps required; and the number of steps of the algorithm executed.

In total 14 problems are considered involving: 3, 5 and 10 machines; and 3, 4, 10, 15, and 40 jobs. Each problem involving 3 machines was solved using the heuristic functions [H.sub.1], [H.sub.2], and [H.sub.3] in (5) which are the same as [F.sub.1], [F.sub.2], and [F.sub.3], respectively, when m = 3. Problems involving 5 and 10 machines were solved using their corresponding heuristic functions [F.sub.1], [F.sub.2], [F.sub.3], [F.sub.4], [F.sub.5] and [F.sub.1], [F.sub.2], [F.sub.3], ..., [F.sub.10], respectively. The solutions enabled improvements in the performance characteristics resulting from the use of only the modification to Step 1 to be assessed. In addition, for each problem the solution was obtained using the modification to Step 1 together with the modification to Step 2. The performance characteristics associated with each of these solutions enabled an assessment of any further improvements in performance characteristics resulting from the inclusion of the modification to Step 2.

From Table Al it is seen that for each problem regardless of the number of jobs and machines the modification to Step 1, which involves using the heuristic function with the largest value in Step 1, leads to improvements in all of the performance characteristics. Furthermore, in each problem using the modification to Step 1 together with the modification to Step 2, which affects the calculation of heuristic estimates as the search progresses, leads to further improvements in the performance characteristics.

6 Conclusion

Three modifications to the initial version of a new r intelligent heuristic search algorithm ([IHSA.sup.*]) have been described. The algorithm guarantees an optimal solution for flow-shop problems involving an arbitrary number of jobs and machines provided the job sequence is the same on all of the machines.

The first modification affects Step 1 of the algorithm and concerns the choice of an admissible heuristic function which is as close as possible to the minimum makespan for the problem. For problems with an arbitrary number of jobs and 3 machines ([M.sub.1], [M.sub.2], [M.sub.3]) a set of 6 possible functions is derived ([H.sub.1], [H.sub.2], ...., [H.sub.6]) and their admissibility is proved. It is shown that the function which has a value that is closest to the minimum makespan and is the best function to use in Step 1 of the algorithm is the function among [H.sub.1], [H.sub.2], and [H.sub.3] which has the largest value. In the particular case where one of the machines ([M.sub.j]) dominates the other 2 machines the best function is Hi and there is no need to calculate the values of the other 2 functions. Furthermore, its value is greater than the value of either of the other 2 functions by at least O([n.sup.2]) where n is the number of jobs. More generally, for problems with more than 3 machines ([M.sub.1], [M.sub.2], ...., [M.sub.m]) the best admissible heuristic function to use is the one among [F.sub.1], [F.sub.2], ..., [F.sub.m] with largest value and if machine [M.sub.j] dominates the other machines then [F.sub.j] is the best heuristic function. The proofs of these more general results may be obtained following the methods used in the proofs presented in the Appendix of the corresponding results for [H.sub.1], [H.sub.2], and [H.sub.3].

The second modification changes the procedure used in Step 2 of the initial version of the algorithm to determine heuristic estimates at nodes on the search path. The initial version determines a heuristic estimate at a node by considering an operation in only one of the cells at the node while operations in the other cells are not taken into account. The modified procedure determines a heuristic estimate at a node by selecting the largest of the separate estimates calculated for each cell at the node. The modified procedure never produces an estimate for a node that is smaller than the estimate produced by the procedure used in the initial version of the algorithm and in many cases it will be larger.

The first and second modifications ensure that at the start of the search and as the search progresses heuristic estimates are admissible and ate as close as possible to the minimum time needed to complete all of the incomplete operations on all of the machines. This reduces the chance that the search will backtrack and improves the performance characteristics of the algorithm. Experimental evidence from problems involving various numbers of machines and jobs indicates that although the first modification produces improvements in performance characteristics of the algorithm these improvements ate enhanced when the second modification is included.

The third modification relates to Step 7 of the algorithm and concerns problems where there are multiple optimal solutions. It enables all of the optimal solutions to be found and this is convenient for situations where additional criteria may need to be satisfied by an optimal solution.

This article has focussed on describing the development of the final version of [IHSA.sup.*]. However, there are several areas for future investigation including a comparison of the performance of the algorithm with other methods such as branch- and-bound methods and methods for pruning the search tree in order to improve memory management during implementation.

Appendix

Derivation of heuristie functions

The purpose is to develop heuristic functions suitable for use in [IHSA.sup.*]. In each case the objective is to develop a function which underestimates the minimum makespan (i.e. admissible). Six functions are developed and the proof of their admissibility is presented in the next section.

From Figure 1, S([[phi].sub.st]) [greater than or equal to] max [[b.sub.t] +, [a.sub.s] + [n.summation over (i=1)][b.sub.i]] and

T([[phi].sub.st]) [greater than or equal to] max [S([phi].sub.st]) + [c.sub.t], [a.sub.s] + [b.sub.s] + [n.summation over (i=1][c.sub.i] which

means that:

T([[phi].sub.st]) [greater than or equal to] [a.sub.s] + [b.sub.s] + [n.summation over (i=1]) [c.sub.i] or, (A1)

T([phi].sub.st]) [greater than or equal to] S([phi].sub.st]) + [c.sub.t] [greater than or equal to][b.sub.t] + [c.sub.t] + [n.summation over (i=1)] [a.sub.i] or, (A2)

T([phi].sub.st])[greater than or equal to][a.sub.s] + [c.sub.t] + [n.summation over (i=1)][b.sub.i]. (A3)

From (Al) two heuristic functions [H.sub.3] and [H.sub.6] are proposed:

[H.sub.3] = min[[a.sub.1] + [b.sub.1], [a.sub.2] + [b.sub.2], ..., [a.sub.n] + [b.sub.n]] + [n.summation over (i=1)][c.sub.i] and

[H.sub.6] = min [[a.sub.1], [a.sub.2], ..., [a.sub.n]] + min [[b.sub.1], [b.sub.2] ..., [b.sub.n] + [n.summation over (i=1)] [c.sub.i].

The rationale for the development of [H.sub.3] is: select the job that will be finished on [M.sub.2] at the earliest possible time if it is placed first in the job sequence. When this job is finished on [M.sub.2] min[[a.sub.1] + [b.sub.1], [a.sub.2] + [b.sub.2] , ..., [a.sub.n]] units of time have elapsed and the additional time needed to complete all of the jobs on all of the machines will be at least [n.summation over (i=1)] [c.sub.i] units of time. Since min[[a.sub.1] + [b.sub.1], [a.sub.2] + [b.sub.2], ..., [a.sub.n] + [b.sub.n]] [greater than or equal to] min[[a.sub.1] [a.sub.2], ..., [a.sub.n] + min[[b.sub.1], [b.sub.2] ..., [b.sub.n] it follows that [H.sub.3] [greater than or equal to] [H.sub.6] which is therefore also a plausible heuristic function.

[H.sub.1] and [H.sub.5] are derived from (A2):

[H.sub.1] = min [b.sub.12] + [c.sub.1], [b.sub.2] + [c.sub.2], ..., [b.sub.n] + [c.sub.n]] + [n.summation over (i=1] [a.sub.i] and [H.sub.5] = min[[b.sub.1], [b.sub.2] ..., [b.sub.n] + min [[c.sub.1], [c.sub.2], ..., [c.sub.n]] + [n.summation over (i=1)[a.sub.i].

The rationale for the development of [H.sub.1] is: select the job which requires the least total amount of time on machines [M.sub.2] and [M.sub.3] (i.e. min[[b.sub.1] + [c.sub.1], [b.sub.2] + [c.sub.2], ..., [b.sub.n] + [c.sub.n]] units of time) and suppose that it is placed last in the job sequence which means that the earliest time that it can start on [M.sub.2] is after [n.summation over (i=1)] [a.sub.i] unitst of time. Since min[[b.sub.1] + [c.sub.1], [b.sub.2] + [c.sub.2], ..., [b.sub.n] + [c.sub.n]] [greater than or equal to] min[[b.sub.1], [b.sub.2] ..., [b.sub.n]] + min[c.sub.1], [c.sub.2], ..., [c.sub.n]] it follows that [H.sub.1] [greater than or equal to] [H.sub.5], which is therefore also a plausible heuristic function. [H.sub.2] and {H.sub.4] are derived from (A3):

[H.sub.2] = min [[a.sub.1] + [u.sub.1], [a.sub.2] + [u.sub.2], ..., [a.sub.n] + [u.sub.n]] + [n.summation over (i+1)] [b.sub.i] and

[H.sub.4] = min [[a.sub.1], [a.sub.2], ..., [a.sub.n]] + min [[c.sub.1], [c.sub.2], ..., [c.sub.n]] [n.summation over (i=1)][b.sub.i],

where: [u.sub.1] = min [[c.sub.2], [c.sub.3], ..., [c.sub.n]]; [u.sub.k] = min [[c.sub.1], [c.sub.2], ..., [c.sub.k-1], [c.sub.k+1], ..., [c.sub.n]] for 2 [less than or equal to] k [less than or equal to] n = 1; and [u.sub.n] = min[[c.sub.1], [c.sub.2], [c.sub.3], ..., [c.sub.n-1]. The rationale for the development of H2 is: consider each job in turn and suppose that it is placed first in the job sequence and then from among all of the other jobs select the one which requires the least amount of time on [M.sub.3]. Now for each pair of jobs selected in this manner determine the pair that gives the least total time on [M.sub.1] and [M.sub.3]. This total time plus the minimum total time required to finish all of the jobs on [M.sub.2] is the value of [H.sub.2]. Also. min[[a.sub.1] + [u.sub.1], [a.sub.2] + [u.sub.2] ..., [a.sub.n] + [u.sub.n]] [greater than or equal to] min [[a.sub.1], [a.sub.2], ..., [a.sub.n]] + min[[u.sub.1], [u.sub.2], ..., [u.sub.n]] = min [[a.sub.1], [a.sub.2], ..., [a.sub.n]] + min [[c.sub.1], [c.sub.2], ..., [c.sub.n]] and it follows that [H.sub.2] [greater than or equal to] [H.sub.4], which is therefore also a plausible heuristic function.

Admissibility

Results and selected proofs related to the admissibility of the heuristic functions [H.sub.1], [H.sub.2], [H.sub.3], [H.sub.4], [H.sub.5], and [H.sub.6] are presented: [R.sub.1], [H.sub.3] [greater than or equal to] [H.sub.6] and both are admissible. [R.sub.2], [H.sub.2] [greater than or equal to] [H.sub.5] and both are admissible. [R.sub.3], [H.sub.1] greater than or equal to] and both are admissible.

Only a proof for R2 is given since the remaining proofs may be constructed in the same manner.

From (A3), T([[[phi].sub.st]) [greater than or equal to] [a.sub.s] + [c.sub.t] + [c.sub.t] + [n.summation over (i=1)[b.sub.i] for s, t = 1, 2, ...,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Hence, if [T.sup.*] ([[phi].sub.st]) denotes the earliest time at which any job sequence which starts with job [J.sub.s] is completed on [M.sub.3]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

From the results [R.sub.1], [R.sub.2], and [R.sub.3] it is seen that the heuristic functions [H.sub.1], [H.sub.2], [H.sub.3], [H.sub.4], [H.sub.5], and [H.sub.6] are all admissible. However, in order to select the heuristic function among these that is the closest in value to the minimum makespan (i.e. the best to use in Step1 of [IHSA.sup.*]) the cboice should be made from among only [H.sub.1], [H.sub.2], and [H.sub.3] because the function among these 3 which has the largest value is admissible and has a value which is larger than any of the other 5 admissible functions. Consequently, in Step1 of [IHSA.sup.*] the values of [H.sub.1], [H.sub.2], and [H.sub.3] are calculated and the function with the largest value is selected for use.

Dominance

Machine [M.sub.1] dominates the other 2 machines if min[[a.sub.1], [a.sub.2], ... [a.sub.n]] [greater than or equal to] max[[b.sub.1], [b.sub.2], ..., [b.sub.n]] and min[[a.sub.1], [a.sub.2], ..., [a.sub.n]] [greater than or equal to] max[[c.sub.1], [c.sub.2], ... [c.sub.n]] and similar definitions apply if machine [M.sub.2] or machine [M.sub.3] is dominant.

In the case of a dominant machine results R5, R6, and R7 identify immediately which heuristic function among [H.sub.1], [H.sub.2], and [H.sub.3] has the largest value and is the best to use in [IHSA.sup.*]. Also, from R8 it is seen that the best heuristic function has a value which is greater than the value of either of the other functions by O([n.sup.2]) where n is the number of jobs.

R5. If machine [M.sub.1] dominates then [H.sub.1] is the heuristic function with the largest value,

R6. If machine [M.sub.2] dominates then [H.sub.2] is the heuristic function with the largest value,

R7. If machine [M.sub.3] dominates then [H.sub.3] is the heuristic function with the largest value.

R8. If a machine is dominant then the best heuristic function has a value which is greater than the value of either of the other 2 functions by at least (n - 1)(n - 2) where n is the number of jobs and n [greater than or equal to] 3.

The proofs for R5 and R8 are given noting that proofs for the other results may be constructed in the same manner. Throughout these proofs min([a.sub.i]) = min[[a.sub.1], [a.sub.2], ..., [a.sub.n]], min([b.sub.i]) = min[[b.sub.1], [b.sub.2], ..., [b.sub.n]], min([c.sub.i]) = min[[c.sub.1], [c.sub.2], ..., [c.sub.n]], max([a.sub.i]) = max[[a.sub.1], [a.sub.2], ..., [a.sub.n]], max([b.sub.i]) = max[[b.sub.1], [b.sub.2], ..., [b.sub.n]], and max([c.sub.i]) = max[[c.sub.1], [c.sub.2], ..., [c.sub.n]].

Suppose machine MI dominates and for i = 1, 2, 3, ..., n: [a.sub.i] [member of] [[r.sub.1], [r.sub.1] + w - 1]; [b.sub.i] [member of] [[s.sub.1], [s.sub.1] + 1 - 1]; and [c.sub.i] [member of] [[t.sub.i], [t.sub.1] + d - 1] are distinct non negative integers from intervals of widths w, l, and d, respectively, each greater than or equal to n (the number of jobs).

It follows that the minimum values of [n.summation over (i=1)] [a.sub.i], [n.summation over(i=1)] [b.sub.i],

[n.summation over (i=1)] [c.sub.i] are n[r.sub.1] + 0.5n(n - 1), n[s.sub.1] + 0.5n(n - 1), and n[t.sub.1] + 0.5n(n - 1), respectively, and when these minimum values are attained min([a.sub.i]) = [r.sub.1], min([b.sub.i]) = [s.sub.1], min([c.sub.i]) = [t.sub.1], max([a.sub.i]) = [r.sub.1] + n - 1, max([b.sub.i]) = [s.sub.1] + n - 1, and max([c.sub.i)] = [t.sub.1] + n - 1 for i = 1, 2, 3 , ..., n.

Also, the maximum values of [n.summation over (i=1)] [a.sub.i], [n.summation over (i=1)] [b.sub.i],

[n.summation over (i=1)] [c.sub.i] are n([r.sub.1] + w) - 0.5n(n + 1), n([s.sub.1] + 1) - 0.5n(n + 1), and n([t.sub.1] + d) - 0.5n(n + 1), respectively, and when these maximum values are attained min([a.sub.i]) = [r.sub.1] + w - n, min([b.sub.i]) = [s.sub.1] + 1 - n, min([c.sub.i]) = [t.sub.1] + d - n, max([a.sub.i]) = [r.sub.1] + w - 1, max([b.sub.i]) = [s.sub.1] + 1 - 1, max([c.sub.i]) = [t.sub.1] + d - 1.

Now, [H.sub.1] = min[[b.sub.1] + [c.sub.1], [b.sub.2] + [c.sub.2], ..., [b.sub.n] + [c.sub.n]] + [n.summation over(i=1)] [a.sub.i] [greater than or equal to] min([b.sub.i]) + min([c.sub.i]) + min([n.summation over (i=1)] [a.sub.i]) (A4)

and similarly,

[H.sub.2] [less than or equal to] max([a.sub.i]) + max([c.sub.i]) + max([n.summation over (i=1)] [b.sub.i]) (A5)

and [H.sub.3] [less than or equal to] max([a.sub.i]) + max([b.sub.i]) + max([n.summation over (i=1)] [c.sub.i]). (A6)

If (A4), (A5), (A6) are all true then,

[H.sub.1] [greater than or equal to] [s.sub.1] + 1 - n + [t.sub.1] + d - n + n[r.sub.1] + 0.5n(n - 1), (A7)

[H.sub.2] [less than or equal to] [r.sub.1] + n - 1 + [t.sub.1] + d - 1 + n([s.sub.1] + 1) - 0.5n(n +1), (A8)

[H.sub.3] [less than or equal to] [r.sub.1] + n - 1 + [s.sub.1] + 1 - 1 + n([t.sub.1] + d) - 0.5n(n + 1). (A9)

From (A7) and (A8), [s.sub.1] + 1 - n + [t.sub.1] + d - n + n[r.sub.1] + 0.5n(n - 1) - [r.sub.1] - n + 1 - [t.sub.1] - d + 1 - n([s.sub.1] + 1) + 0.5n(n + 1) = [s.sub.1] - n[s.sub.1] + 1 - [n.sub.1] + n[r.sub.1] - [r.sub.1] + [n.sup.2] - 3n + 2 = (n - 1)[[r.sub.1] -([s.sub.1] + 1) + n - 2] [greater than or equal to] (n - 1)(n - 2) [greater than or equal to] 0, for n [greater than or equal to] 2, and so [H.sub.1] is greater than [H.sub.2] by a value which is at least (n - 1)(n - 2), for n [greater than or equal to] 3.

In a similar manner it follows from (A7) and (A9) that [H.sub.1] is greater than H3 by a value which is at least (n - 1)(n - 2), for n [greater than or equal to] 3 and this completes the proof of R5 and R8.

The best admissible heuristic function for an arbitrary number of machines

For the case where there are more than 3 machines there is a need to change the notation used previously to represent the time that each operation [O.sub.i,j] requires on each machine so that [t.sub.i,j] is the number of units of time required by job [J.sub.i] on machine [M.sub.j].

If there are m machines then the best admissible heuristic function will be the one with the largest value among the set of m functions [F.sub.1], [F.sub.2], [F.sub.3], ..., [F.sub.m] where,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For a problem with m machines where m > 3 and the job sequence is the same on each machine the function among [F.sub.1], [F.sub.2], [F.sub.3], ..., [F.sub.m] with the largest value is selected in Step 1 of [IHSA.sup.*].

If m = 3 then using [t.sub.1,i] = [a.sub.i], [t.sub.2,i] = [b.sub.i], and [t.sub.3,i] = [c.sub.i] for i = 1, 2, 3, ..., n and representing [u.sub.j,1], [u.sub.j,k], and [u.sub.j,n] simply by [u.sub.1], [u.sub.k], and [u.sub.n], respectively, the 3 admissible heuristic functions [H.sub.1], [H.sub.2], and [H.sub.3] in (5) which have been used throughout the description of the development of [IHSA.sup.*] are given by [F.sub.1], [F.sub.2], and [F.sub.3], respectively.

Experimental evidence of improvements in performance characteristics

Table A1: Performance of [IHSA.sup.*]: Modification to Step 1 compared to Modifications to Steps 1 and 2.

Note: For each problem: (a) the highlighted first row, associated with the use of the modification to Step 1, indicates the performance characteristics using the best heuristic function; (b) the highlighted last row, associated with the use of modifications to Steps 1 & 2, indicates the performance characteristics when the best heuristic function is used together with the modification to Step 2.

Table Al: Performance of IHSA *

No. of      Number of                    Modification
Machines       Jobs         Problem          Used

   3                           1              1

                                             1&2

                3              2              1

                                             1&2

                               3              1

                                             1&2

                               4              1

                                             1&2

                4              5              1

                                             1&2

                               6              1

                                             1&2

                               7              1

                                             1&2

                15             8              1

                                             1&2

                               9              l

                                             1&2

                40             10             1

                                             1&2

                               11             1

                                             1&2

                               12             1

                                             1&2

   5            15             1              1
                               3

                                             l&2

   10           10             1              1
                               4

                            Value of
No. of      Heuristic      Heuristic
Machines     Function       Function

   3            Hl             17
                H3             10
                H2             9

                H1             17

                H2             24
                H3             15
                H1             13

                H2             24

                H3             28
                H2             20
                H1             18

                H3             28

                H1             23
                H3             19
                H2             14

                H1             23

                H2             22
                H3             19
                H1             15

                H2             22

                H3             24
                H2             21
                HI             20

                H3             24

                Hl             26
                H3             18
                H2             16

                H1             26

                H2             28
                H3             20
                H1             16

                H2             28

                H3             29
                H2             20
                Hl             19

                H3             29

                Hl             43
                H3             38
                H2             35

                Hl             43

                H2             42
                H3             40
                Hl             37

                H2             42

                H3             45
                H2             38
                Hl             35

                H3             45

   5            F1             37
                F2             30
                F3             27
                F4             25
                F5             23

                F1             37

   10           F3             50
                F2             48
                F4             46
                F1             45
                F6             42
                F5             40
                F9             38
                F7             32
                F8             32
               F10             30

                F3             50

                   Performance
                 Characteristics

No. of        Nodes                       Algorithm      Minimum
Machines     Expanded      Backtracks       Steps       Makespan

   3            13             0              10           17
                22             11             33
                21             12             34

                10             0              7

                13             6              22           24
                36             39             88
                36             37             84

                8              2              17

                16             1              14           28
                17             3              16
                17             3              16

                13             0              10

                35             20             52           25
                50             30             72
                57             37             82

                35             15             42

                32             27             66           23
                79             70            152
                80             79            170

                31             21             54

                66             53            109           27
                69             63            138
                71             64            140

                63             43             96

                20             2              22           28
                24             l0             30
                26             15             36

                18             0              10

                20             9              38           31
                38             40             90
                40             45             98

                16             4              25

                19             2              22           30
                22             4              28
                25             4              29

                16             0              18

                50             12             70           45
                53             30            105
                70             38            113

                44             6              55

                49             30             60           43
                50             32             85
                66             45            115

                32             18             52

                68             46            115           50
                77             58            152
                90             93            205

                54             30             84

   5            42             12             65           39
                60             15             93
                72             18            104
                82             25            126
                97             32            150

                30             5              50

   10           35             20             63           52
                37             23             83
                41             28             89
                43             30             91
                45             33             95
                52             34            107
                60             40            123
                69             45            135
                72             48            137
                81             51            151

                30             2              40

Received: October 25, 2007

References

[1] Blum, C., Roli, A. "Metaheuristics in combinatorial optimization: overview and conceptual comparison," ACM Comput. Surv., 35, 2003, 268-308.

[2] Chen, C.L., Neppalli, R.V., Aljaber, N. "Genetic algorithms applied to the continuous flow shop problem," Computers and Industrial Engineering 30: (4), 1996, 919-929.

[3] Cleveland, G.A., Smith, S.F. "Using genetic algorithms to schedule flow shop," Proceedings of 3rd Conference on Genetic Algorithms, Schaffer, D.(ed.), San Mateo: Morgan Kaufmann Publishing, 1989, 160-169.

[4] Conway, R.W., Maxwell, W.L., Miller, L.W. Theory of scheduling, Addison-Wesley, Reading Massachusetts, 1967.

[5] Eitler, O., Toklu, B., Atak, M., Wilson, J. "A genetic algorithm for flowshop scheduling problems," J. Oper. Res. Soc., 55, 2004, 830-835.

[6] Fan, J.P.-O. "The development of a heuristic search strategy for solving the flow-shop scheduling problem," Proceedings of the IASTED International Conference on Applied Informatics, Innsbruck, Austria, 1999, 516-518.

[7] Fan, J.P.-O. "An intelligent search strategy for solving the flow-shop scheduling problem," Proceedings of the IASTED International Conference on Software Engineering, Scottsdale, Arizona, USA, 1999, 99-103.

[8] Fan, J.P.-O. An intelligent heuristic search method for flow-shop problems, doctoral dissertation, University of Wollongong, Australia, 2002.

[9] Framinan, J.M, Ruiz-Usano, R., Leisten, R. "Sequencing CONWIP flow-shops: analysis and heuristic," Int. J. Prod. Res., 39, 2001, 2735-2749.

[10] Gheoweth, S.V., Davis, H.W. "High performance [A.sup.*] search using rapidly growing heuristics," Proceedings of the International Joint Conference on Artificial Intelligence, Sydney, Australia, 1991, 198-203.

[11] Grabowski, J., Wodecki, M. "A very fast tabu search algorithm for the permutation flowshop problem with makespan criterion," Comput. Oper. Res., 31, 2004, 1891-1909.

[12] Hart, P.E., Nilsson, N.J., Raphael, B. "A formal basis for the heuristic determination of minimum cost paths," IEEE Transactions on Systems Science and Cybernetics, Vol. SSC-4: (2), 1968, 100-107.

[13] Hong, T.P., Chuang, T.N. "Fuzzy scheduling on two-machine flow shop," Journal of Intelligent & Fuzzy Systems, 6: (4), 1998, 471-481.

[14] Hong, T.P., Chuang, T.N. "Fuzzy CDS scheduling for flow shops with more than two machines," Journal of Intelligent & Fuzzy Systems, 6: (4), 1998, 471-481.

[15] Hong, T.P., Chuang, T.N. "Fuzzy Palmer scheduling for flow shops with more than two machines," Journal of Information Science and Engineering, Vol. 15, 1999, 397-406.

[16] Hong, T.P., Wang, T.T. "A heuristic Palmer-based fuzzy flexible flow-shop scheduling algorithm," Proceedings of the IEEE International Conference on Fuzzy Systems, Vol. 3, 1999, 1493-1497.

[17] Hong, T.P., Huang, C.M., Yu, K.M. "LPT scheduling for fuzzy tasks," Fuzzy Sets and Systems, Vol. 97, 1998, 277-286.

[18] Hong, T.P., Wang, C.L., Wang, S.L. "A heuristic Gupta-based flexible flow-shop scheduling algorithm," Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Vol. 1, 2000, 319-322.

[19] Ignall, E., Schrage, L.E. "Application of the branch and bound technique to some flow shops scheduling problems," Operations Research, Vol. 13: (3), 1965, 400-412.

[20] Johnson, S.M. "Optimal two- and three-stage production schedules with setup times included," Naval Research Logistics Quarterly, 1: (1), 1954, 61-68.

[21] Kamburowski, J. "The nature of simplicity of Johnson's algorithm," Omega-International Journal of Management Science, 25: (5), 1997, 581-584.

[22] Korf, R.E. "Depth-first iterative-deepening: an optimal admissible tree search," Artificial Intelligence, Vol. 27, 1985, 97-109.

[23] Korf, R.E. "Iterative-deepening [A.sup.*]: an optimal admissible tree search," Proceeding of the 9th International Joint Conference on Artificial Intelligence, Los Angeles, California, 1985, 1034-1036.

[24] Korf, R.E. "Real-time heuristic search," Artificial Intelligence, Vol. 42, 1990, 189-211.

[25] Korf, R.E. "Linear-space best-first search," Artificial Intelligence, 62: (1), 1993, 41-78.

[26] Lai, T.C. "A note on heuristics of flow-shop scheduling," Operations Research, 44: (6), 1996, 648-652.

[27] Lee, G.C., Kim, Y.D., Choi, S. W. "Bottleneck-focused scheduling for a hybrid flow-shop," Int. J. Prod. Res., 42, 2004, 165-181.

[28] Liu, B., Wang, L., Jin, Y-H. "An effective PSO-based memetic algorithm for flow shop scheduling, "IEEE T. Syst. Man. CY. B.," 37, 2007, 18-27.

[29] Lonmicki, Z. "A branch and bound algorithm for the exact solution of three machine scheduling problem," Operational Research Quarterly, 16: (1), 1965, 89-100.

[30] McMahon, C.B., Burton, P.G. "Flow-shop scheduling with the branch and bound method," Operations Research, 15: (3), 1967, 473-481.

[31] Nawaz, M., Enscore Jr. E., Ham, I. "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem," Omega-Int. J. Manage. S., 11, 1983, 91-95.

[32] Ogbu, F.A., Smith, D.K. "The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem," Comput. Oper. Res., 17, 1990, 243-253.

[33] Onwubolu, G.C., Davendra, D. "Scheduling flowshops using differential evolution algorithm," Eur. J. Oper. Res., 171, 2006, 674-692.

[34] Osman, I., Potts, C. "Simulated annealing for permutation flow shop scheduling," OMEGA, 17, 1989, 551-557.

[35] Pan, C.H. "A study of integer programming formulations for scheduling problems," International Journal of System Science, 28: (1), 1997, 33-41.

[36] Pan, C.H., Chen, J.S. "Scheduling alternative operations in two-machine flow-shops," Journal of the Operational Research Society, 48: (5), 1997, 533-540.

[37] Ravendran, C. "Heuristic for scheduling in flowshop with multiple objectives," Eur. J. Oper. Res., 82, 1995, 540-555.

[38] Ruiz, R., Maroto, C., Alcaraz, J. "Two new robust genetic algorithms for the flowshop scheduling problem," Omega-Int. J. Manage. S., 34, 2006, 461-476.

[39] Stutzle, T. "Applying iterated local search to the permutation flowshop problem," AIDA-98-04, TU Darmstadt, FG Intellektik, 1998.

[40] Taillard, E. "Some efficient heuristic methods for the flow shop sequencing problem," Eur. J. Oper. Res., 47, 1990, 65-74.

[41] Taillard, E. "Benchmarks for basic scheduling problems," Eur. J. Oper. Res., 64, 1993, 278-285.

[42] Wang, C.G., Chu, C.B., Proth, J.M. "Efficient heuristic and optimal approaches for N/2/F/SIGMA-C-I scheduling problems," International Journal of Production Economics, 44: (3), 1996, 225-237.

[43] Ying, K.C., Liao, C.J. "An ant colony system for permutation flow-shop sequencing," Comput. Oper. Res., 31, 2004, 791-801.

[44] Zamani, M.R., Shue, L.Y. "Developing an optimal learning search method for networks," Scientia Iranica, 2: (3), 1995, 197-206.

[45] Zamani, R., Shue, L.Y. "Solving project scheduling problems with a heuristic learning algorithm," Journal of the Operational Research Society, 49: (7), 1998, 709-716.

[46] Zamani, M.R. "A high performance exact method for the resource-constrained project scheduling problem," Computers and Operations Research, 28, 2001, 1387-14.

[47] Zobolas, G.I., Tarantilis, C.D., Ioannou, G.

"Minimizing makespan in Permutation Flow Shop scheduling problems using a hybrid metaheuristic algorithm," Computers and Operations Research, 2008, doi: 10.1016/j.cor.2008.01.007.

Joshua Poh-Onn Fan

Graduate School of Business

University of Wollongong, NSW, Australia

E-mail: [e-mail]

Graham K. Winley

Faculty of Science and Technology

Assumption University, Bangkok, Thailand

E-mail: [e-mail]

Table 1: Example of a Flow-shop Problem

Jobs/Machines   [M.sub.1]   [M.sub.2]   [M.sub.3]

[J.sub.1]           2           1           10
[J.sub.2]           4           6            5
[J.sub.3]           3           2            8