Iterative Flattening Search for the Flexible Job Shop Scheduling Problem

1 Introduction

The paper focuses on a family of solving techniques referred to as Iterative Flattening Search (IFS). IFS was first introduced in [Cesta et al., 2000] as a scalable procedure for solving multi-capacity scheduling problems. IFS is an iterative improvement heuristic designed to minimize schedule makespan. Given an initial solution, IFS iteratively applies two-steps: (1) a subset of solving decisions are randomly retracted from a current solution (relaxation-step); (2) a new solution is then incrementally recomputed (flatteningstep). Extensions to the original IFS procedure were made in two subsequent works [Michel and Van Hentenryck, 2004; Godard et al., 2005] both of which substantially improved its performance on reference benchmark problems and established additional new best solutions. More recently [Oddi et al., 2010] have performed a systematic study aimed at evaluating the effectiveness of single component strategies within the same uniform software framework.

In this paper we develop and evaluate an IFS procedure for solving a scheduling problem with a different structure than the multi-capacity job-shop problem. We focus specifically on the Flexible Job Shop Scheduling Problem (FJSSP), a generalization of the classical JSSP where a given activity may be processed on any one of a designated set of available machines. The FJSSP is more difficult than the classical Job Shop Scheduling Problem (which is itself NP-hard), since it is not just a sequencing problem. In addition to deciding how to sequence activities that require the same machine, it is also necessary to choose a routing policy, that is which machine will process each activity. The objective remains that of minimizing makespan. The problem is motivated by interest in developing Flexible Manufacturing Systems (FMS), as underscored in [Rossi and Dini, 2007]; an effective synthesis of the existing solving approaches is proposed in [Ben Hmida et al., 2010]. The core set of procedures which generates the best results include the genetic algorithm (GA) proposed in [Gao et al., 2008], the tabu search (TS) approaches of [Mastrolilli and Gambardella, 2000; Bozejko et al., 2010] and the discrepancy-based method, called climbing depth-bounded discrepancy search (CDDS), defined in [Ben Hmida et al., 2010]. We use the results produced by these procedures as our evaluation reference point in this paper.

The IFS variant that we propose relies on a core constraintbased search procedure as its solver. This procedure is an extension of the SP-PCP procedure proposed in [Oddi and Smith, 1997]. SP-PCP generates consistent orderings of activities requiring the same resource by imposing precedence constraints on a temporally feasible solution, using variable and value ordering heuristics that discriminate on the basis of temporal flexibility to guide the search. We extend both the procedure and these heuristics to incorporate an additional set of decision variables relating to resource choice. To provide a basis for embedding this core solver within an IFS optimization framework, we also specify a new metaheuristic procedure for relaxing a feasible solution by randomly disrupting the activity sequences on various machines and reintroducing resource choice. Empirical analysis of our algorithm shows that it is generally comparable in performance to the best algorithms published over the last 10 years.

The paper is organized as follows. Section 2 defines the FJSSP problem and Section 3 introduces a CSP representation. Section 4 describes the core constraint-based search procedure while Section 5 introduces details of the IFS metaheuristics. An experimental section describes the performance of our algorithm on a set of benchmark problems, and explains the most interesting results. Some conclusions end the paper.

2 Flexible Job Shop Scheduling Problem

The FJSSP entails synchronizing the use of a set of machines (or resources) R = {r1, . . . , rm} to perform a set of n activities A = {a1, . . . , an} over time. The set of activities is partitioned into a set of nj jobs J = {J1, . . . , Jnj}. The processing of a job Jk requires the execution of a strict sequence of nk activities ai ∈ Jk and cannot be modified. All jobs are released at time 0. Each activity ai requires the exclusive use of a single resource ri for its entire duration chosen among a set of available resources Ri ⊆ R. No preemption is allowed. Each machine is available at time 0 and can process more than one operation of a given job Jk (recirculation is allowed). The processing time pir of each activity ai depends on the selected machine r ∈ Ri, such that ei - si = pir, where the variables si and ei represent the start and end time of ai. A solution S = {(s1, r1), (s2, r2), . . . , (sn, rn)} is a set of pairs (si, ri), where si is the assigned start-time of ai, ri is the selected resource for ai and all the above constraints are satisfied. Let Ck be the completion time for the job Jk, the makespan is the value Cmax = max1≤k≤nj{Ck}. An optimal solution S∗ is a solution S with the minimum value of Cmax. The FJSSP is NP-hard since it is an extension of the JSSP problem [Garey and Johnson, 1979].

3 ACSP Representation

There are different ways to model the problem as a Constraint Satisfaction Problem (CSP), we use an approach similar to [Oddi and Smith, 1997]. In particular, we focus on assigning resources to activities, a distinguishing aspect of FJSSP and on establishing precedence constraints between pairs of activities that require the same resource, so as to eliminate all possible conflicts in the resource usage.

Let G(AG, J,X) be a graph where the set of vertices AG contains all the activities of the problem together with two dummy activities, a0 and an+1, respectively representing the beginning (reference) and the end (horizon) of the schedule. Each activity ai is labelled with the set of available resource choices Ri. J is a set of directed edges (ai, aj) representing the precedence constraints among the activities (job precedences constraints) and are labelled with the set of processing times pir (r ∈ Ri) of the edge's source activity ai. The set of undirected edges X represents the disjunctive constraints among the activities requiring the same resource r; there is an edge for each pair of activities ai and aj requiring the same resource r and the related label represents the set of possible ordering between ai and aj: ai ⪯ aj or aj ⪯ ai. Hence, in CSP terms, there are two sets of decision variables: (1) a variable xi is defined for each activity ai to select one resource for its execution, the domain of xi is the set of available resource Ri: (2) A variable oijr is defined for each pair of activities ai and aj requiring the same resource r (xi = xj = r), which can take one of two values ai ⪯ aj or aj ⪯ ai.

To support the search for a consistent assignment to the set of decision variables xi and oijr, for any FJSSP we define the directed graph Gd(V, E), called distance graph, which is an extended version of the graph G(AG, J,X). The set of nodes V represents time points, where tp0 is the origin time point (the reference point of the problem), while for each activity ai, si and ei represent its start and end time points respectively. The set of edges E represents all the imposed temporal constraints, i.e., precedences and durations. In particular, for each activity ai we impose the interval duration constraint ei - si ∈ [pmin i , pmax i ], such that pmin i (pmax i ) is the minimum (maximum) processing time according to the set of available resources Ri. Given two time points tpi and tpj, all the constraints have the form a ≤ tpj - tpi ≤ b, and for each constraint specified in the FJSSP instance there are two weighted edges in the graph Gd(V,E); the first one is directed from tpi to tpj with weight b and the second one is directed from tpj to tpi with weight -a. The graph Gd(V,E) corresponds to a Simple Temporal Problem (STP) and its consistency can be efficiently determined via shortest path computations; the problem is consistent if and only if no closed paths with negative length (or negative cycles) are contained in the graph Gd [Dechter et al., 1991]. Thus, a search for a solution to a FJSSP instance can proceed by repeatedly adding new precedence constraints into Gd(V,E) and recomputing shortest path lengths to confirm that Gd(V,E) remains consistent. A solution S is given as a affine graph GS(AG, J,XS), such that each undirected edge (ai, aj) in X is replaced with a directed edge representing one of the possible orderings between ai and aj: ai ⪯ aj or aj ⪯ ai. In general the directed graph GS represents a set of temporal solutions (S1, S2, . . . , Sn) that is, a set of assignments to the activities' start-times which are consistent with the set of imposed constraints XS. Let d(tpi, tpj) (d(tpj, tpi)) designate the shortest path length in graph Gd(V,E) from node tpi to node tpj (from node tpj to node tpi); then, the constraint -d(tpj, tpi) ≤ tpj - tpi ≤ d(tpi, tpj) is demonstrated to hold [Dechter et al., 1991]. Hence, the interval [lbi, ubi] of time values associated with a given time variable tpi respect to the reference point tp0 is computed on the graph Gd as the interval [-d(tpi, tp0), d(tp0, tpi)]. In particular, given a STP, the following two sets of value assignments Slb = {-d(tp1, tp0), -d(tp2, tp0), . . . , -d(tpn, tp0)} and Sub = {d(tp0, tp1), d(tp0, tp2), . . . , d(tp0, tpn)} to the STP variables tpi represent the so-called earliest-time solution and latest-time solution, respectively.

4 Basic Constraint-based Search

The proposed procedure for solving instances of FJSSP integrates a Precedence Constraint Posting (PCP) one-shot search for generating sample solutions and an Iterative Flattening meta-heuristic that pursues optimization. The one-shot step, similarly to the SP-PCP scheduling procedure (Shortest Pathbased Precedence Constraint Posting) proposed in [Oddi and Smith, 1997], utilizes shortest path information in Gd(V,E) to guide the search process. Shortest path information is used in a twofold fashion to enhance the search process: to propagate problem constraints and to define variable and value ordering heuristics.

4.1 Propagation Rules

The first way to exploit shortest path information is by introducing conditions to remove infeasible values from the domains of the decision variables xi, representing the assignment of resources to activities, similarly to what proposed in [Huguet and Lopez, 2000]. Namely, for each activity ai we relax the disjunctive duration constraint into the interval constraint ei - si ∈ [pmin i , pmax i ], such that pmin i

(pmax i ) is the minimum (maximum) processing time according to the set of available resources Ri (Ri is the domain of the decision variable xi). As soon as the search progresses and the interval of distance between the start-time and the end-time of ai [-d(si, ei), d(ei, si)] is updated, the duration pir ̸∈ [-d(si, ei), d(ei, si)] are removed from the domain of xi and a new interval [pmin i , pmax i ] is recomputed accordingly. In the case the domain of the decision variable xi becomes empty, then the search is reached a failure state.

The second way to exploit shortest path is by introducing Dominance Conditions, through which problem constraints are propagated and mandatory decisions for promoting early pruning of alternatives are identified. Given two activities ai, aj and the related interval of distances [-d(sj, ei), d(ei, sj)] 1 and [-d(si, ej), d(ej, si)] 2 on the graph Gd, they are defined as follows (see Figure 1).

We observe as d(ei, sj) is the maximal distance between ai and aj, it provides a measure of the degree of sequencing flexibility between ai and aj 3 . In addition, -d(sj, ei) is the minimum possible distance between ai and aj (see Figure 1), then there is no need to separate ai and aj when -d(sj, ei) ≥ 0. For any pair of activities ai and aj that can compete for the same resource r (Ri ∩Rj ̸= ∅), given the corresponding durations pir and pjr, the Dominance Conditions, describing the four main possible cases of conflict, are defined as follows:

1. d(ei, sj) < 0 ∧ d(ej, si) < 0
2. d(ei, sj) < 0 ∧ d(ej, si) ≥ 0 ∧-d(si, ej) < 0
3. d(ei, sj) ≥ 0 ∧ d(ej, si) < 0 ∧-d(sj, ei) < 0
4. d(ei, sj) ≥ 0 ∧ d(ej, si) ≥ 0

Condition 1 represents an unresolvable resource conflict. There is no way to order ai and aj when they require the same resource r without inducing a negative cycle in the graph Gd(V,E). When Condition 1 is verified there are four different interesting sub-cases generated on the basis of the cardinality of the domain sets Ri and Rj .

• removed from Rj ;

1 between the end-time ei of ai and the start-time sj of aj

2 between the end-time ej of aj and the start-time si of ai

3 Intuitively, the higher is the degree of sequencing flexibility, the larger is the set of feasible assignments to the start-times of ai and aj

1. |Ri| > 1 ∧ |Rj| = 1: the resource requirement r can be removed from Ri;
2. |Ri| > 1 ∧ |Rj| > 1: the activities ai and aj cannot use the same resource r.

Conditions 2, and 3, alternatively, distinguish uniquely resolvable conflicts, i.e., there is only one feasible ordering of ai and aj when both the activities require r. In the particular case where |Ri| = |Rj| = 1 the decision aj ⪯ ai is mandatory. In the case there is at least one activity with more than one resource option (|Ri| > 1 ∨ |Rj| > 1), it is still possible to choose different resource assignments for ai and aj, and avoid posting a precedence constraint. Condition 3 works similarly, and entails that only the ai ⪯ aj ordering is feasible when |Ri| = |Rj | = 1.

Condition 4 designates a class of resolvable conflicts with more search options; in this case when |Ri| = |Rj| = 1 both orderings of ai and aj remain feasible, and it is therefore necessary to perform a search decision. When there is at least one activity ai or aj with more than one resource option (|Ri| > 1 ∨ |Rj| > 1), then there is also the possibility of choosing different resource assignments to ai and aj, and avoid to post a precedence constraint.

4.2 Heuristic Analysis

Shortest path information in Gd can also be exploited to define variable and value ordering heuristics for the decision variables xi and oijr in all cases where no mandatory decisions are deduced from the propagation phase. The idea is to evaluate both types of decision variables (xi and oijr) and select the one (independently of type) with the minimum heuristic evaluation. The selection of the variables is based on the most constrained first (MCF) principle and the selection of values follows the least constraining value (LCV) heuristic.

Initially, all the pairs of activities (ai, aj), such that (|Ri| ≥ 1 ∨ |Rj| ≥ 1 and Ri ∩ Rj ̸= ∅)) undergo a doublekey sorting, where the primary key is a heuristic evaluation based on resource flexibility and computed as FRij = 2(|Ri| + |Rj|) - |Ri ∩ Rj|4 , and the secondary key is a heuristic evaluation based on temporal flexibility and computed as FTij = minr∈Ri∩Rj {V arEvalr(ai, aj)}, where the V arEvalr(ai, aj) heuristic is an extension to the FJSSP of the heuristic proposed in [Oddi and Smith, 1997], and it is computed as follows. As stated above, in this context d(ei, sj) and d(ej, si) provide measures of the degree of sequencing flexibility between ai and aj . More precisely, given an activity pair (ai, aj), both assigned to resource r, the related heuristic evaluation is V arEvalr(ai, aj) =

where S = min{d(ei ,sj ),d(ej ,si)} max{d(ei ,sj ),d(ej ,si)} 5 . The pair (a∗i , a∗j ) with the lowest value 〈FRij, FTij〉 (double-key sorting) is firstly selected and then it is associated to a resource decision variable

4 The resource flexibility FRij increases with the size of the domains Ri and Rj, and decreases with the size of the set Ri ∩ Rj, which is correlated to the possibility of creating resource conflicts.

5 The √S bias is introduced to take into account cases where a first conflict with the overall min{d(ei, sj), d(ej, si)} has a

PCP(Problem, Cmax)

1. S ← InitSolution(Problem, Cmax) 2. loop 3. Propagate(S) 4. if UnresolvableConflict(S) 5. then return(nil) 6. else 7. if UniquelyResolvableDecisions(S) 8. then PostUnconditionalConstraints(S) 9. else begin 10. C ←ChooseDecisionVariable(S) 11. if (C = nil) 12. then return(S) 13. else begin 14. vc ← ChooseValueConstraint(S, C) 15. PostConstraint(S, vc) 16. end 17. end 18. end-loop 19. return(S)

or to an ordering decision variable depending on the cardinalities |Ri| and |Rj|.

Resource decision variables. In case the condition |Ri| > 1 ∨ |Rj| > 1 holds for the selected (a∗i , a∗j ) pair, the chosen resource decision variable between x∗i and x∗j will be the one whose domain of values has the lowest cardinality (i.e., the MCF choice). As opposed to variable ordering, the value ordering heuristic is accomplished so as to retain the highest temporal flexibility. If Ri is the domain of the selected decision variable xi, then for each resource r ∈ Ri we consider the set of activities Ar already assigned to resource r and calculate the value Fmin(r) = minak∈Ar {V arEvalr(ai, ak)}. Hence, for each resource r we evaluate the flexibility associated with the most critical pair (ai, ak), under the hypothesis that the resource r is assigned to ai. The resource r∗ ∈ Ri which maximizes the value Fmin(r), and therefore allows ai to retain maximal flexibility, is selected.

Ordering decision variables. In case the condition |Ri| = 1 ∧ |Rj| = 1 holds, the (a∗i , a∗j ) pair is directly selected to be ordered, as it represents the conflict with the least amount of sequencing flexibility (i.e., the conflict that is closest to previous Condition 1 sub-case a). As in the previous case, the value ordering heuristic attempts to resolve the selected conflict (ai, aj ) by simply choosing the precedence constraint that retains the highest amount of sequencing flexibility (least constrained value). Specifically, ai ⪯ aj is selected if d(ei, sj) > d(ej , si) and aj ⪯ ai is selected otherwise.

4.3 The PCP Algorithm

Figure 2 gives the basic overall PCP solution procedure, which starts from an empty solution (Step 1) where the graphs Gd is initialized according to Section 3. Also, the procedure accepts a never-exceed value (Cmax) of the objective function of interest, used to impose an initial global makespan to

very large max{d(ei, sj), d(ej , si)}, and a second conflict has two shortest path values just slightly larger than this overall minimum. In such situations, it is not clear which conflict has the least sequencing flexibility.

IFS(S,MaxFail, γ) 1. Sbest ←S 2. counter ← 0 3. while (counter ≤MaxFail) do 4. RELAX(S, γ) 5. S ←PCP(S,Cmax(Sbest)) 6. if Cmax(S) < Cmax(Sbest) then 7. Sbest ← S 8. counter ← 0 9. else 10. counter ← counter + 1 11. return (Sbest)

all the jobs. The PCP algorithm shown in Figure 2 analyses the decision variables xi and oijr, and respectively decides their values in terms of imposing a duration constraint on a selected activity or a precedence constraint (i.e., ai ⪯ aj or aj ⪯ ai, see Section 3). In broad terms, the procedure in Figure 2 interleaves the application of Dominance Conditions (Steps 4 and 7) with variable and value ordering (Steps 10 and 14 respectively) and updating of the solution graph Gd (Steps 8 and 15) to conduct a single pass through the search tree. At each cycle, a propagation step is performed (Step 3) by the function Propagate(S), which propagates the effects of posting a new solving decision (i.e., a constraint) in the graph Gd. In particular, Propagate(S) updates the shortest path distances on the graph Gd. A solution S is found when the PCP algorithm finds a feasible assignment of resources ri ∈ Ri to activities ai (i = 1 . . . n}) and when none of the four dominance conditions is verified on S. In fact, when none of the four Dominance Conditions is verified (and the PCP procedure exits with success), for each resource r, the set of activities Ar assigned to r represents a total execution order. In addition, as the graph Gd represents a consistent Simple Temporal Problem (see Section 3), one possible solution of the problem is the earliest-time solution, such that S = {(-d(s1, tp0), r1), (- d(s2, tp0), r2), . . . , (-d(sn, tp0), rn)}.

5 The OptimizationMetaheuristic

Figure 3 introduces the generic IFS procedure. The algorithm basically alternates relaxation and flattening steps until a better solution is found or a maximal number of iterations is executed. The procedure takes three parameters as input: (1) an initial solution S; (2) a positive integer MaxFail, which specifies the maximum number of non-makespan improving moves that the algorithm will tolerate before terminating; (3) a parameter γ explained in Section 5.1. After the initialization (Steps 1-2), a solution is repeatedly modified within the while loop (Steps 3-10) by applying the RELAX procedure (as explained in the following section), and the PCP procedure shown in Figure 2 used as flattening step. At each iteration, the RELAX step reintroduces the possibility of resource contention, and the PCP step is called again to restore resource feasibility. In the case a better makespan solution is found (Step 6), the new solution is saved in Sbest and the counter is reset to 0. If no improvement is found within MaxFail moves, the algorithm terminates and returns the best solution found.

5.1 Relaxation Procedure

The first part of the IFS cycle is the relaxation step, wherein a feasible schedule is relaxed into a possibly resource infeasible, but precedence feasible, schedule by retracting some number of scheduling decisions. Here we use a strategy similar to the one in [Godard et al., 2005] and called chain-based relaxation. Given the graph representation described above, each scheduling decision is either a precedence constraint between a pair of activities that are competing for the same resource capacity and/or a resource assignment to one activity. The strategy starts from a solution S and randomly breaks some total orders (or chains) imposed on the subset of activities requiring the same resource r. The relaxation strategy requires an input solution as a graph GS(A, J,XS) which (Section 3) is a modification of the original precedence graph G that represents the input scheduling problem. GS contains a set of additional precedence constraints XS which can be seen as a set of chains. Each chain imposes a total order on a subset of problem activities requiring the same resource.

The chain-based relaxation proceeds in two steps. First, a subset of activities ai is randomly selected from the input solution S, with each activity having an uniform probability γ ∈ (0, 1) to be selected (γ is called the relaxing factor). For each selected activity, the resource assignment is removed and the original set of available options Ri is re-estabilished. Second, a procedure similar to CHAINING - used in [Policella et al., 2007] - is applied to the set of unselected activities. This operation is accomplished in three steps: (1) all previously posted precedence constraints XS are removed from the solution S; (2) the unselected activities are sorted by increasing earliest start times of the input solution S; (3) for each resource r and for each unselected activity ai assigned to r (according to the increasing order of start times), ai's predecessor p = pred(ai, r) is considered and a precedence constraint (p, ai) is posted (the dummy activity a0 is the first activity of all the chains). This last step is iterated until all the activities are linked by precedence constraints. Note that this set of unselected activities still represents a feasible solution to a scheduling sub-problem, which is represented as a graph GS in which the randomly selected activities float outside the solution and thus re-create conflict in resource usage.

6 Experimental Analysis

To empirically evaluate the IFS algorithm, we have considered a well known FJSSP benchmark set described in the literature and available on the Internet at http://www. idsia.ch/˜monaldo/fjsp.html. The set is composed of 21 instances initially provided by Barnes and Chambers (in the literature and in the rest of the paper this benchmark is referred to as BCdata), with the objective of minimizing the makespan. The benchmark is briefly described in the appendix of the work [Mastrolilli and Gambardella, 2000]. The IFS algorithm used for these experiments has been implemented in Java and run on a AMD Phenom II X4 Quad 3.5 Ghz under Linux Ubuntu 10.4.1. In our experiments the MaxFail parameter (see algorithm in Figure 3) was set to 100000; however, a maximum CPU time limit of 3200 seconds was set for each run.

Results. Table 1 shows the results obtained running our IFS algorithm on the BCdata set. The table is composed of eight columns and 24 rows, one row per instance plus 3 data wrap-up rows. The best column contains the best results known in current literature to the best of our knowledge; our results will therefore be compared against such values. In particular, each value in the best column represents the best makespan obtained with at least one of the approaches described in [Ben Hmida et al., 2010; Mastrolilli and Gambardella, 2000; Gao et al., 2008; Bozejko et al., 2010]. The columns labeled γ = 0.2 to γ = 0.7 (see Section 4) contain the results obtained running the IFS procedure with a different value for the relaxing factor γ. The bold values in Table 1 represent the best results known in literature for each instance; the underlined bold values indicate the most significant improvements obtained by our IFS procedure (the relative instances have also been underlined). For each γ run, the last three rows of the table show respectively: (1) the number B of best solutions found (and, between brackets, the number N of most recent best solutions found in [Bozejko et al., 2010]), (2) the average number of utilized solving cycles (Av.C.), and (3) the average mean relative error (Av.MRE) 6 respect to the lower bounds reported in [Mastrolilli and Gambardella, 2000]. The imposed CPU limit of 3200 seconds may appear very high, especially when compared with the limits imposed on some of the competing procedures; yet, the attention should be focused on the relatively low number of solving cycles our procedure requires to converge to a good solution. In fact, while the IFS metaheuristic generally requires a number of relaxation/solving cycles on the order of the tens of thousands, in our experimentation the best results were obtained with a number of cycles ranging from 6000 to 15000 (approximately), indicating the effectiveness of the inner PCP procedure.

6 the individual MRE of each solution is computed as follows: MRE = 100 × (Cmax - LB)/LB, where Cmax is the solution makespan and LB is the instance's lower bound As Table 1 shows, our procedure is competitive with the state of the art; more in detail, the three underlined instances in the table show exactly the same results recently obtained in [Bozejko et al., 2010] with a specialized tabu search algorithm using a high performance GPU with 128 processors, while 10 previously known bests on a total of 21 instances are confirmed. Analyzing the Av.MRE results, the best performances are obtained with γ values lying in the [0.5, 0.7] range, which is confirmed by the higher concentration of confirmed best solutions. It is interesting to notice how the average number of solving cycles exhibits a steadily decreasing trend as γ increases; the more the solution is disrupted at each cycle, the greater the effort to find an alternative solution and hence the smaller number of solving cycles within the same CPU time limit. Nevertheless, the results show that increasing the disruption level in the range [0.5, 0.7] helps in obtaining higher quality solutions, while increasing further triggers the opposite effect. As part of our ongoing work, we are testing our procedure on some of the biggest instances (i.e., la36-la40) of another well known FJSSP dataset, namely the Hurink edata dataset. This preliminary test is yielding promising results, as we improved two instances (namely, la36, from 1162 to 1160 and la38, from 1144 to 1143) w.r.t. the results published in [Mastrolilli and Gambardella, 2000].

7 Conclusions

In this paper we have proposed the use of Iterative Flattening Search (IFS) as a means of effectively solving the FJSSP. The proposed algorithm uses as its core solving procedure an extended version of the SP-PCP procedure originally proposed by [Oddi and Smith, 1997] and a new relaxation strategy targeted to the case of FJSSP. The effectiveness of the procedure was demonstrated on the BCdata benchmark set of FJSSPs. More specifically, the main contributions of this work are: (1) an extension of the slack-based value and variable ordering heuristics of [Oddi and Smith, 1997] for the FJSSP which, together with the propagation rules, constitute the basic components of the greedy PCP procedure; (2) a new relaxation strategy for the FJSSP; and (3) an evaluation of the full IFS algorithm against a challenging benchmark set for which many optimal solutions are still unknown. On average, the performance of IFS in this setting is found to be in line with the best-known algorithms published over the last 10 years. The fact that it was possible to adapt the original IFS procedure to the FJSSP problem without altering its core strategy, once again has proven the overall efficacy of the logic at the heart of IFS, as well as its versatility.

Further improvement of the current algorithmmay be possible by incorporating additional heuristic information and search mechanisms. This will be the focus of future work. One possible direction is analysis of the effects on performance produced by a randomized version of the PCP algorithm. Another is the study of landscape analysis methods to balance exploration and exploitation search phases.

Acknowledgments

CNR authors are partially supported by EU under the ULISSE project (Contract FP7.218815), and MIUR under the PRIN project 20089M932N (funds 2008). S.F. Smith is funded in part by DARPA (Contract W911NF-11-2-0009).