Content area
The generic hoist scheduling problem is NP-hard and arises from automated manufacturing lines. In recent work using the constraint logic programming (CLP) formalism, a unified model has been developed with the problem description and solution method separated. We provide an improved model and new preprocessing stages where, as before, solutions and proof of optimality are provided by a hybrid CLP-MIP algorithm. The new algorithm is more scalable and robust. We give empirical results for a range of problem classes on benchmark problems from several sources. [PUBLICATION ABSTRACT]
Abstract. The generic hoist scheduling problem is NP-hard and arises from automated manufacturing lines. In recent work using the constraint logic programming (CLP) formalism, a unified model has been developed with the problem description and solution method separated. We provide an improved model and new preprocessing stages where, as before, solutions and proof of optimality are provided by a hybrid CLP-MIP algorithm. The new algorithm is more scalable and robust. We give empirical results for a range of problem classes on benchmark problems from several sources.
Keywords: hoist scheduling, hybrid methods, modelling, benchmarks
(ProQuest Information and Learning: ... denotes formulae omitted.)
1. Introduction
Hoist scheduling is an abstraction of a common industrial problem. Computer-controlled hoists (or transport robots) are used in PCB electroplating and other sectors to move material through some fixed sequence of operations. The importance of optimising the hoist movements is that the same procedure is performed continuously for many weeks, and a change in the production run may require several weeks of downtime [33].
The first solutions to the hoist scheduling problem used mathematical programming [30]. Later, artificial intelligence techniques in the forms of local search and constraint logic programming (CLP) were applied [3,16]. More recently, a hybrid technique that combines MIP and CLP has been developed [31]. In this paper, we elaborate and generalise the hybrid approach, presenting a revised CLP model and new preprocessing stages.
Below we introduce and classify the hoist scheduling problem (HSP) in more detail, and, in section 2, present the new model. Section 3 discusses the solvers used and the hybridization between them, and section 4 gives our results for a number of benchmark problems. Finally, we draw some conclusions in section 5.
1.1. Hoist scheduling
The simplest case of the hoist scheduling problem is the basic problem introduced by Phillips and Unger [30]. A single computer-controlled hoist operates on a single track above a sequential line of tanks. A large number of identical jobs are placed at the initial stage of the line. Each job is to be processed through the tanks and placed at the far end.
Hoist scheduling is distinguished from classical scheduling problems, such as flowshop or jobshop, in that, first, no waiting of jobs during an operation is permissible, second, travel times of an operation are not negligible, and third, there is no intermediate storage between tanks. In addition, to reflect the industrial situation, the prescribed processing times in the tanks are bounded in a time window but need not be fixed.
Jobs are assumed to be identical in the basic problem. If the jobs differ or fall into multiple types, the nature of the HSP changes and the algorithms are quite different. The same occurs if the arrival of jobs is not known in advance (the dynamic hoist scheduling problem [17]).
In the cyclic hoist scheduling problem (CHSP), the same sequence of operations is repeated. One complete sequence is a cycle, and the length of time required for one cycle is the period (or cycle time or makespan). In a single part problem, one job enters and one job leaves the system in every cycle. In a multi-part or r-part system, r jobs enter and leave in every cycle [15]. Generalising the CHSP, the n-periodic hoist scheduling problem [22] has a cycle composed of n smaller repeated sequences. The most common case in industry is the cyclic hoist scheduling problem with homogeneous jobs [33].
The basic problem does not account for all of industrial practice. The most notable extension is to multiple hoists, which may share one track or have one track each. If the number of hoists is greater than the number of tracks, collisions must be avoided, which necessitates hoist assignment (how hoists are assigned to tanks). Other variations from the basic problem include a single load/unload stage rather than one stage at each end, and multi-function tanks, those visited by a job more than once. Either of these possibilities entails bidirectional hoist movement while carrying a job. Some tanks may be duplicated or have a capacity greater than one, in order to reduce a bottleneck in the line.
Varnier et al. [36] give a partial survey of the literature on the forms of the HSP. To further aid in the classification, we propose a notation for the problem classes similar to that used in queueing theory. Denote a class of the HSP as F/H/T/A/r to indicate:
- F: zero or more of the flags:
* C: cyclic,
* D: dynamic,
* H: heterogeneous jobs,
* N: non-sequential;
- H: the number of hoists, 1 (single) or M (multiple);
- T: the number of tracks, 1 (single) or M (multiple);
- A: hoist assignment1, one of:
* D (determined, i.e. partitioned),
* C (collision-based),
* O (optimal);
- r: the number of parts, 1 or an integer r.
Terms may be omitted where implied or irrelevant: for instance, we consider only single-part problems so will omit the r term. Phillips and Unger's problem PU12, introduced below, is classified as C/1/1, for example, whereas the most general problem considered by Rodosek and Wallace [31] is C/M/M/C. The notation is easily extensible.
1.2. Previous work
1.2.1. MIP approaches
Phillips and Unger [30] introduced the HSP and provided the now-famous benchmark problem, PU12. They used a MIP model to find the minimum cycle time for this realworld twelve-tank problem2.
Shapiro and Nuttle [33] introduced a revised branch-and-bound procedure and used MIP on different sub-problems to bound the search space. Levner et al. [22] improved the upper bound for the period.
Lei and Wang [19] solved the HSP for two hoists on the same track. They introduced a new heuristic algorithm which partitions the line of tanks into two contiguous sets and assigns to each hoist one set. Lei et al. [18] gave an improved heuristic, where the hoists must be scheduled to avoid traffic collisions (no partitioning is used). They were not able to guarantee the optimal solution.
There have been a number of works presenting progressively better or broader MIP models [1,5,21,37] and branch-and-bound procedures [20,28]. Bidirectional multiple hoists were considered first by Manier [26].
1.2.2. CP approaches
The first approach to exploit constraint programming was by Baptiste et al. [4]. They demonstrated that the versatility of CLP allowed the rapid development of computational models for different classes of hoist scheduling problems. Their results showed that CLP with a linear solver is more effective than constraint propagation over finite domains. They were able to produce an optimal schedule for the problem PU12, with a revised model, in less than one minute.
Varnier and others [27,36] extended this work to model multiple hoists and nonsequential treatment, including multi-function and duplicated tanks but not higher capacity tanks. They resolved the hoist assignment in only a restricted form using heuristics.
Cheng and Smith [6] considered a multi-product single-hoist HSP where each job may require treatment in a subset of the tanks (tank skipping). Mak et al. [25] used constraint satisfaction to solve the single-hoist CHSP with multi-function and duplicated tanks and a single load/unload stage.
1.2.3. Hybridization and hybrid approaches
Tsang et al. [35] document a range of difficult combinatorial problems solved by exploiting integer programming (IP) and constraint programming (CP) together in hybrid approaches. Hooker et al. [12] provide a generic scheme for hybridization between optimisation and constraint satisfaction methods, emphasising the complementary strengths of the two methods respectively in search and relaxation and in inference and strengthening. Several researchers report on problems not solvable in reasonable time by either IP or CP alone, but which fall to a combined approach [2].
A hybrid model was first applied to the HSP by Rodosek and Wallace [31]. Their model was resolved using propagation and search in the CLP platform ECL^sup i^PS^sup e^ and linear solving in an external package. The advantage of hybridization for the HSP has been to extend the class of problems that can be handled by a single model, to allow a single solver algorithm to work across these classes, and to provide proof of optimality in cases which are beyond traditional methods.
Rodosek and Wallace [31] consider a generic class of CHSP with single or multiple hoists, tracks, and tank capacities. In their hybrid, every constraint is passed to a CLP solver and a MIP solver. They introduced a harder thirteen-tank variant, PU13, of the Phillips and Unger problem, in which jobs are moved from the load stage to the first tank by a separate mechanism. To be able to compare results, we will consider PU13 rather than PU12.
Other algorithmic approaches to the problem were partially surveyed in Hall et al. [9]. For example, Petri-nets [7], genetic algorithms for the single-hoist instance [24], and local search, notably simulated annealing [16]. With the exception of certain restricted or simplified cases, all the hoist scheduling problems introduced above have been shown to be NP-hard [10].
This paper contributes a more scalable and robust hybrid model, improving the work of Rodosek and Wallace [31]. We provide results analysing the performance of the three main approaches to the HSP on known benchmark problems, and point out future enhancements for the hybridization.
2. The model
The expressiveness of CLP allows the easy modelling of both the linear and disjunctive constraints in the HSP. We exploit the automatic translation of Rodosek et al. [32] to produce from the declarative CLP model one suitable for a MIP solver.
2.1. Variables and notation
The following are all integers, with the decision variables in bold face:
N number of tanks,
R number of tracks,
H number of hoists,
J number of simultaneous jobs,
T number of treatments,
S(i) tank for ith treatment,
C(j) capacity of tank j,
m(j) minimum treatment time in tank j,
M(j) maximum treatment time3 in tank j,
E(j, k) time to move empty hoist from tank j to tank k,
F(j, k) time to move full hoist from tank j to tank k,
T (i) actual time of ith treatment,
R(i) removal time upon completion of ith treatment,
B(i) number of the hoist that performs the ith transfer operation,
P cycle period.
The hoists and tanks are numbered from left to right; the load and unload tanks are considered to be tanks 0 and N + 1, respectively4. We take the ith transfer operation as being from tank S(i) to tank S(i + 1); hence T > or = N + 1 if every tank is used (strict inequality is possible in the case of multi-function tanks).
For all tanks, E(j,k) = E(k,j). For non-duplicated tanks, E(j,j) = 0, while for duplicated tanks, following Shapiro and Nuttle [33], E(j,j) [not =] 0 and we take E(j,k) = max^sub l^(E^sup (l)^(j,k)), where E^sup (l)^(j,[middot]) denotes the lth duplicated tank at position j.
For those variables which relate to tanks by absolute index rather than by treatment sequence, we write C^sub i^ for C(S(i)), F^sub i^ for F(S(i), S(i + 1)), etc. For the other variables, R^sub i^ = R(i), etc.We will consider later only sequential treatments, that is when T = N+1 and S(i) = i.
In an industrial setting, the time to perform a transfer operation is greater than the time to move the hoist between two tanks: we must raise the job, allow it to drip off above the tank, move, stabilise and lower. Without loss of generality, we include all this in the full times.
Our model differs from previous CLP approaches in that we optimise using the removal times. Previous authors used both entry and removal times [31], entry and treatment times [36] or treatment and removal times [25]. A single variable per treatment yields a smaller search space and simplified constraints; the treatment times can be derived by
T^sub i^ = R^sub i^ - (R^sub i-1^ + F^sub i-1^). (1)
Given a single-part cycle, we suppose the system is in steady state; thus exactly one job enters and one job leaves the system in every cycle. We seek values for the unknowns R(i), B(i), and P; the period will be integral since the data is integral.
2.2. Constraints
The constraints for a simple single-part cyclic HSP with time windows and tank capacities fall into four categories: the treatment sequence, the 1-part cycle, the tanks, and the hoists.
First, the cyclic structure and tank capacities are linked. If a tank is full to its capacity, the first job that entered (we assume first-in, first-out) must be removed before the arrival of the next job. Hence, considering tank i with tank capacity C(i), a job must be removed before the arrival of the job which is C(i) cycles behind it in the production sequence. We derive:
R^sub 1^ < P [middot] C^sub 1^,
R^sub i^ < P [middot] C^sub i^ + R^sub i-1^ + F^sub i-1^. (2)
In the case of simple capacities, the same holds with C^sub i^ = 1.
The cyclic structure leads to a second constraint, since in every cycle all T operations must be performed once. It follows that the process time for a job cannot be greater than the product of the number of jobs and the period:
R^sub T^ + F^sub T^ < or = J [middot] P. (3)
Third, the treatment time for every tank must be bounded by the given data. Using (1), we have:
m^sub i^ < or = R^sub i^ - (R^sub i-1^ + F^sub i-1^) < or = M^sub i^. (4)
Finally, we have constraints on the hoists. Since each hoist can perform only one action at a time, we must avoid: removal of jobs from multiple tanks at once, removal of a job from a tank while the hoist is transporting another job, and the movement of the hoist faster or slower than the specified translation times.
Assuming a 1-part system, more subtly, a resource clash on a hoist will occur if we ask it to perform a task on a job at time [tau], and a task is being performed on another job at time [tau] + P. Here, the clash will be between the first task on one job and the second task on the following job. Generalising, we must rule out two tasks for any pair of times [tau] and [tau] + kP, where 0 < k < J.
It follows that at the centre of the HSP model is a three-variable disjunctive constraint: exactly one of
R^sub i^ + F^sub i^ + E^sub i+1,j^ < or = R^sub j^ + k [middot] P (5)
or
R^sub j^ + F^sub j^ + E^sub j+1,i^ + k [middot] P < or = R^sub i^ (6)
must hold, for all k = 1, . . . , J - 1; i, j = 1, . . . , T; j < i.
2.3. Boolean variables and preprocessing
We use a boolean variable to denote, given any two tanks i > j, whether the hoist either goes first to i (when (5) applies) or to j (when (6) applies). For each pair of tanks i > j and distance k between jobs in the production sequence, let B^sub i,j,k^ be a boolean variable such that (5) holds iff B^sub i,j,k^ = 1. Then constraint (5) becomes (with (6) similarly):
R^sub i^ + F^sub i^ + E^sub i+1,j^ < or = R^sub j^ + kP + (1 - B^sub i,j,k^) [middot] [Omega] (7)
where [Omega] is an integer that dominates the expression (a 'big-M' term).
Let us now assume sequential treatment. It is possible to eliminate certain contradictory situations in advance by a preprocessing step, initialising some of the B^sub i,j,k^. Consider a job m in tank i and a job m + k, 1 < or = k < J, in tank j = i - 1. With unit tank capacities it is trivially not possible to move job m + k before m; that is, the hoist must visit i before j, or equivalently, B^sub i,j,k^ = 1.
More generally, for 2 < or = i < or = T and 1 < or = j,k,m < T,
(j = i - m [logical or] k > or = m) [implies] B^sub i,j,k^ = 1. (8)
The reduction in boolean variables reduces the search space and the number of active constraints, and sharpens the relaxation bounds. With four-job PU13, for example, the reduction is from 234 to 98 variables.
2.4. Further HSP classes
2.4.1. Multiple hoists, multiple tracks
The same model applies for C/M/M as C/1/1 but with some constraints removed. We assume that each treatment tank S(i) is assigned to one hoist B(S(i)) which will handle the tank for the ith transfer. Since each hoist has a dedicated track, collisions are not possible. Hence, if two tanks are handled by different hoists, neither (5) nor (6) applies.
As before, we explicitly unfold the disjunction with an auxiliary boolean, in order to be able to perform some preprocessing. For each pair of tanks i > j, introduce C^sub i,j^ such that the disjunction applies only if both tanks are handled by the same hoist:
B^sub i^ [not =] B^sub j^ [if and only if] C^sub i,j^ = 1. (9)
Hence, (5) becomes:
R^sub i^ + F^sub i^ + E^sub i+1,j^ < or = R^sub j^ + kP + (1 - B^sub i,j,k^ + C^sub i,j^) [middot] [Omega]. (10)
Without loss of generality, we assign B(1) = 1 to remove symmetries. It is not possible to similarly set R^sub 1^ = m^sub 1^; this may prevent the optimal period from being found.
2.4.2. Hoist assignment
Before we can present the model for C/M/1/x, we must discuss the problem of hoist assignment. Varnier et al. [36] describe the three possibilities in the literature. In order of generality:
1. Disjoint zones [19]. Each hoist is assigned a contiguous set (or zone) of tanks, and moves only within this set. Sets are disjoint between hoists except for boundary tanks.
2. Collision-based [11,20,26]. The sets for each hoist need not be disjoint, nor even contiguous. The hoists must be managed to avoid collisions.
3. Optimal [14,22]. Rather than fixing the number of hoists then assigning tanks, find the minimal number of hoists that can achieve a given period, or the minimal period.
The third class, C/M/1/O, is a very difficult problem. It has been solved by non-CP methods only when other restrictions have been placed on the HSP [14,18], such as fixed processing times rather than time windows. With CP, we can find the number of hoists that minimises P, by labelling H upwards from the lowest value in its domain, until the period found with H + 1 hoists is the same as that with H hoists.
Varnier et al. [36] consider the second class, C/M/1/C, but with some restrictions. They assume, reasonably, that overlap tanks are accessed only by adjacent hoists, and, more restrictively, that each hoist has at least one tank that it alone accesses. Their solution uses heuristics and is not guaranteed to be optimal. Below, we make the first assumption but not the second, thus giving the optimal collision-based hoist assignment.
2.4.3. Multiple hoists, single track
We assume again sequential treatment. First, the additions to the basic model for C/M/1/D. Every hoist has a set of tanks that it handles, and the intersection with the other zones is null except for boundary tanks. To achieve this, a system of constraints related with the B(i) variables is added:
B(i - 1) + 1 > or = B(i) > or = B(i - 1) (i = 2, . . . , T - 1). (11)
The domains of the B(i) can be reduced by eliminating unreachable tanks (since hoists may not pass each other). Observe that the first tank can be reached by the first hoist alone, the second tank by the first and the second hoists only, etc. By symmetry, B(1) [is an element of] {1}, B(2) [is an element of] {1, 2}, . . . ,B(N - 1) [is an element of] {H - 1,H}, B(N) [is an element of] {H}. Further, as in C/M/M, we need no constraint for those tanks handled by different hoists, but now the relation for the C^sub i,j^ is linear: C^sub i,j^ = B^sub i^ - B^sub j^.
Second, collision-based hoist assignment, C/M/1/C. We must consider three new possibilities:
- B(i) = B(j): tanks i and j are handled by the same hoist; the disjunctive constraint remains unchanged.
- B(i) > B(j): the disjunctive constraint is unnecessary, because tanks i and j are handled by hoists which will never meet.
- B(i) < B(j): the disjunctive constraint must be modified to ensure the first hoist to move retires in time for the second.
Introducing additional boolean variables D^sub i,j^, we obtain:
B^sub i^ > B^sub j^ [if and only if] C^sub i,j^ = 1, B^sub i^ < B^sub j^ [if and only if] D^sub i,j^ = 1 (12)
and constraint (5) now becomes, for i > j and [delta]^sub 1^ = E^sub i+1,j-1^ - E^sub i+1,j^:
R^sub i^ + F^sub i^ + E^sub i+1,j^ < or = R^sub j^ + kP + ((1 - B^sub i,j,k^) + C^sub ij^) [middot] [Omega] - [delta]^sub 1^ [middot] D^sub i,j^. (13)
2.4.4. Duplicated and multi-function tanks
Duplicated tanks are often used in industry to remove a bottleneck on the line: for instance for a drying stage that takes 10 times longer than any other stage. We have instead considered higher capacity tanks.
Multi-function tanks are those that are visited more than once by the same job. From such a non-monotonic treatment sequence, it follows that jobs will have to be transported both right and left, which adds considerably to the complexity of the problem, particularly in hoist assignment. Combining load and unload stages also introduces bidirectional hoist movement; Mak et al. [25] examine this case and show a small change in the constraint model they give is sufficient.
3. The solvers
To find solutions to the constraint model given in the previous sections, we implemented solvers for the three main approaches to the HSP - pure CP, pure MIP and hybrid - using the Prolog-based ECL^sup i^PS^sup e^ platform [13]. ECL^sup i^PS^sup e^ implements a number of CLP schemes and provides an interface to internal and commercial solvers. For the constraint propagation, we used the fd finite domain solver built-in to ECL^sup i^PS^sup e^. For the MIP solving, we used the CPLEX package.
Initial bounds for the unknowns, the period P and removal times R(i), are crucial to the MIP solver (constraint propagation will infer the bounds in the CP solver). For the period, the bounds are:
... (14)
and
... (15)
The second inequality (15) is obtained by supposing we process one job at a time, but is not the tightest known; Levner et al. [22] give an algorithm based on a merge-sort of interval sets. For PU13, for example, the bound is 933 rather than 1472 [25]. However, since the CP search begins from the lower bound of the period, the upper bound is of little relevance to the CP solver.
For the removal times, the bounds are:
... (16)
The final sum is only to T - 1 because the time to move the job from the last treatment tank to the unload station is irrelevant to the removal times.
3.1. CP solver
The constraints, those described in section 2, are considered only by the fd solver; propagation is performed over finite domains. Heuristics can be applied easily in CP to decisions such as the order of labelling of the variables and the order of value selection. We evaluated various possibilities before settling on that which performed best overall.
First we label the period, P, starting from the lowest value in its domain. If constraint propagation yields a consistent situation from the candidate value of P, we attempt to label the other variables. By labelling P from the lowest value, the first solution found will be the optimal solution; no separate proof of optimality is necessary.
After P, we label the assignment of hoists to transfer operations (in multi-hoist problems), then the removal times, R(i), and finally the auxiliary booleans. This order gives maximum constraint propagation and search tree pruning. We used no in-search symmetry breaking.
For the problem C/M/1/D, we applied a redundant constraint: at most T - H + 1 treatments can be handled by a single hoist (since each hoist must perform at least one treatment not to be redundant). This constraint furthers propagation a little, and is also applied to the CP component of the hybrid solver.
3.2. MIP solver
The constraints are passed to the MIP solver via the eplex interface of ECL^sup i^PS^sup e^. Search is performed within the MIP package, by the default linear solving algorithm chosen by the CPLEX heuristics.
MIP performance is very dependent on the number of variables and on the bounds for the objective. The preprocessing steps of boolean variable reduction, symmetry removal and hoist assignment domain reduction give a marked improvement, examined in section 4. The optimal period and whole solution is returned to ECL^sup i^PS^sup e^.
For the problem C/M/1/C, we performed a two-stage solution. The first solves the same problem but with partitioned hoist assignment. This is much simpler than collision-based assignment but - since the period for the latter, being less constrained, cannot be larger than the former - this first step provides a greatly improved upper bound on the period. With this upper bound, we then solve the full problem. This technique was also used for the hybrid solver.
3.3. Hybrid solver
The constraints here are considered by both solvers, with search control handled by ECL^sup i^PS^sup e^. Information obtained by one solver is immediately available to the other via shared bounds and variable domains.
We first perform constraint propagation on finite domains, potentially yielding new upper and lower bounds on the variables. Second, the LP solver is invoked on the continuous relaxation (integer conditions omitted). When the relaxed problem is solved, control returns to ECL^sup i^PS^sup e^ with the lower bound on P improved.
Third, we label the period P, as in section 3.1. If a candidate value is acceptable after propagation, we attempt to label the other variables (hoist assignment and then removal times) by domain splitting. Should this succeed, we have the optimal solution; should it fail, we backtrack to label P further.
In the previous hybrid method [31], the LP solver was invoked on the relaxed problem each time the bounds on P changed. Our experimentation showed that the information gained by subsequent invocations did not outweigh the cost overhead of the LP solver runs. While the simpler hybrid performs better overall, the argument can be made for a greater LP involvement in some cases.
Indeed, Rodosek and Wallace [31] show that both finite domain and LP failures are necessary to prune the search space, and that there is a certain amount of orthogonality between the two methods. The hybrid algorithm gains from the LP solver global consistency of the continuous relaxation, an improved lower bound on the period, and (although we do not make use of them) suggested values for the other variables.
Most important to the hybrid is the quality of the bound provided by the relaxation. We discuss in section 5 the formulation of the hybrid, co-operation between the solvers, and quality of the relaxed bound.
4. Results and analysis
4.1. Empirical results
We give the results of the three solvers, pure CP, pure MIP and hybrid, for a range of data sets and problem parameters. The results were obtained on a 450 MHz Pentium II with 384 MB memory, using ECL^sup i^PS^sup e^ version 5.1. The times given below are in seconds to find the optimum and prove optimality. CPLEX version 7.0 was the LP solver used, with default settings and propagation.
The first results are those for variants of the PU13 problem. Table 1 shows the four benchmark problems considered in [31], and in our results, given in table 2, these correspond to the lines with four jobs. The other lines in table 2 give the number of jobs for which the minimal period is first achieved; * denotes more than 18,000 seconds (five hours) of CPU time.
Figure 1 shows our results for PU13 with four hoists and four tracks. An extended timeout of 40,000 seconds was used. The hardest instances are with 9 and 10 jobs, when only hybrid finds a solution. It appears that 7 jobs is easier than 6 or 8, but the general trend is that the problem moves from easy to hard to easier again.
Our results for optimal period agree with previous work where the problems have been considered before. To find the number of jobs for which the period is minimal has not been previously done using a hybrid method, and to our knowledge not been done by any method for C/M/1/C. Three tracks, one hoist appears the hardest class of those we examined and, for large numbers of jobs, all of the solvers struggle.
In the question of hoist assignment, partitioning the line simplifies the situation greatly. We found that every instance of C/M/1/D could be consistently solved by MIP, for example, in less than one minute, and often in a few seconds with any solver. C/M/1/C is a much harder problem but gives correspondingly lower cycle times - for instance, with three hoists and ten jobs, 196 compared to 217.
We examined our results in light of those reported by Rodos ek and Wallace. A closer consideration of their constraint model reveals a flaw: the following illegal possibility is permitted. A hoist carrying a job j descends to a tank containing some other job k, releases j and picks up k in the same instant. Clearly this is not possible unless there is some intermediate storage. This possibility cannot occur in our model because the inequality in (2) is strict5.
We produced benchmarks with the three solvers on other problems. Firstly, we used three data sets appearing in the literature: SZS5, LKS9 and DEGEM. None of these presented any hard problem instances for the HSP classes we consider. Were, for instance, the multi-part HSP to be considered, then these production lines with fewer tanks may become interesting. Details and timings obtained are given in the appendix.
Secondly, we introduced a new problem, RYS16, with sixteen tanks, and tested the solver performance. The size of the new problem gave many hard instances. The results, broadly, are in accordance with those for PU13. For simpler instances, there is little to choose between the solvers. For harder instances, the hybrid is often at an advantage. For example, with four hoists and tracks, four jobs is solved quickly by all solvers but five jobs proves difficult for MIP. We do not give detailed timings here.
Thirdly, we used a randomly generated problem following Lei and Wang [19]. Minimal and maximal processing times are generated for each tank by m^sub rand^(i) = m(i)-10+20r^sub 1^ and M^sub rand^(i) = M(i)-10+20r^sub 2^, and the full travel times are F^sub rand^(i,i+1) = E(i,i + 1) + 15 + 10r^sub 3^, where r^sub 1^,r^sub 2^,r^sub 3^ are U[0, 1] random variables.
Table 3 compares the results given in [31] with our hybrid solver, for 100 random instances with two hoists, two tracks and four jobs. The times given are to prove optimality; the literature results were obtained on a Sun Sparc/20. The results indicate the robustness of the hybrid approach.
For the problems C/1/1 and C/M/M, our solver proved to be approximately 2-5 times faster than that of Rodosek and Wallace, supposing identical hardware. For instance, to prove optimality with four jobs, two hoists and two tracks took 11.4 s compared to 289 s, and four jobs, two hoists and one track took 90 s compared to 2105 s. This may be attributed to the simplified constraint model and the improved hybridization.
4.2. Analysis
There are two key factors in the HSP: the combinatorial complexity and the constrainedness. We consider an instance of the HSP to be easy if the number of jobs is at most twice the number of hoists; otherwise, we consider the instance to be hard.
For easy problems, the fastest solutions are found using pure CP, although the difference with the other solvers is not notable. Using fd only, most of the search tree is pruned. For hard problems, the fastest solutions are usually found using the hybrid solver: with occasional exceptions, the hybridization avoids the prohibitive CPU time the other solvers may require.
Multiple-capacity tanks are handled far better by MIP than CP or hybrid. However, we found no interesting instances among the data sets where the extra capacity improved the solution, most likely because the limiting resource in the long PU13 production line is not the tank capacities but the hoists.
Secondly, there is a distinction between highly constrained and weakly constrained problems, by which we mean constrainedness in the classical CP sense, not in terms of feasible set. C/M/1 is more constrained, for example, than C/M/M.
We observe that highly constrained problems are solved quickly by CP (if they are not hard problems). A large number of constraints ensures rapid fd propagation, which is the main element of the CP solver. In contrast, weakly constrained problems are solved more quickly byMIP, because its effort is dominated by the size of the branch-and-bound search tree, which depends on the number of integer variables rather than the number of constraints. The hybrid method, therefore, gives at least reasonable performance provided the orthogonality of the hybridization is effective.
5. Conclusion
In this work, we considered a revised hybrid approach to the hoist scheduling problem. The new model is more robust and scalable than the old, performing well across a range of problem classes and benchmark data. We used new preprocessing steps, in the case of sequential treatment, to reduce the search space, and we suggested a novel notation for the classes of the HSP.
5.1. Hybridization and the hoist scheduling problem
In some instances of the HSP, the pure CP solver works well; in others, the pure MIP solver. Neither is able to perform consistently across the range of problems we examined. Our MIP solver provides better performance than our CP solver for weakly constrained hoist problems, and overall, the results showed it handles more problem classes in reasonable time. Figure 2 summarises our comparison of the solvers. We have seen that CLP is easily adapted to the different HSP classes, with changes in the constraints only, and has a search procedure that is straight-forward to describe and easy to modify.
The performance of the hybrid approach can be attributed to two factors. First, the early detection of different failures by the component solvers (for which CP and linear solvers are orthogonal), and second, the complementary strength of LP in guiding search towards the global optimum and of CP in handling disjunctions. Thus our experience in the HSP is in line with the theory given by Hooker et al. [12].
In the previous hybrid formulation, the linear solver was invoked at each node in the CP search. We found that, overall, the cost of these invocations outweighed their usefulness, and that a simpler hybrid with single LP invocation gave better performance.
In sequencing problems, to which HSP is related, it is common for boolean formulations to have weak relaxations. If it were possible to find simple cutting inequalities, some of the auxiliary boolean variables we use could be omitted - an approach that has worked in other applications of hybrid methods. The correspondingly smaller relaxation then could be solved at more nodes in the search for both hybrid and MIP approaches6.
We have seen that hybridization retains the modelling advantage of CP while leading to a more robust solver. For larger problems, in particular, the hybrid solver can often find solutions and prove optimality when neither our CP or MIP solvers can do so. In almost every case, the hybrid solver is better than the previous hybrid approach, and our results overall are competitive with the best of those obtained so far by any approach in the literature.
5.2. Further work
Three areas appear promising for future work on hybrid HSP. First, improving the existing hybrid solver. It may be appropriate to invoke the LP solver subsequently once fd has progressed by some degree. It is the case that more symmetries could be removed than at present.
In the class C/M/1, the problem can be decomposed into two parts: hoist-tank assignment as a master problem and hoist scheduling as a subproblem. When the subproblems are independent, a tighter form of hybridization than we have used, notably Benders decomposition [8], may give better results; this independence is so for C/M/1/D but not for collision-based assignment.
Our combined use of explicit and automated constraint linearization, choice of problem variables and presolving of the partitioned problem have together yielded an efficient MIP model. Even so, there is room for improvement. For instance, using the better upper bound of Levner et al. [22] for C/M/1/D should yield the solution more quickly (and would give some aid to the hybrid, too). In addition, the automated translator of Rodosek et al. [32] has been recently extended [29]; this may allow us to exploit more of the modelling features of CLP and to tighten the linear relaxation.
Second, the model given in section 2 holds for multi-function tanks and nonsequential treatment, although as noted, some of the preprocessing steps do not (it would be necessary to relax expressions in which S(i) occurs as a subscript). Constraint-based solutions to the HSP with these extensions have already been demonstrated [25,36], but a hybrid solver not yet applied.
Other possible extensions include a single load/unload stage (which would be straight-forward), multi-part cycles (challenging, but permits better solutions) and C/M/1/O optimal hoist allocation (very challenging, perhaps heuristics would be necessary).
Third, there appears to have been no work to date on the HSP with H hoists and R tracks where 1 < R < H and H > or = 3. This increases the complexity, with the new problem of how to assign hoists to tracks as well as to transfer operations. To refine and apply the CLP-MIP hybrid to such problems seems a natural step.
Acknowledgments
We are grateful to Mark Wallace for many wise insights, and thank Andrew Eremin and the anonymous reviewers for their suggestions.
1 In the case of multiple hoists on a single track.
2 In fact, the solution they published is not optimal. Phillips and Unger found the optimum for three simultaneous components (jobs), but a solution of lower period exists with four jobs.
3 It is permissible for this value to be unbounded.
4 It may be that the two physically coincide, that is, a single load/unload stage.
5 A further consequence of this is that the time for the hoist to return to the load stage, having deposited a finished job at the unload stage, cannot be zero. For PU13, which would otherwise permit this possibility, the period could therefore be one second shorter in certain cases, namely 11 jobs with 3 or 4 hoists and tracks.
6 We are grateful to an anonymous reviewer for this observation.
References
[1] R. Armstrong, L. Lei and S. Gu, A bounding scheme for deriving the minimal cycle time of a single-transporter N-stage process with time-window constraints, GSM Working Paper 92-07, Rutgers University (1992).
[2] P. Baptiste, Y. Caseau, T. Kokeny, C. Le Pape and R. Rodosek, Creating and evaluating hybrid algorithms for inventory management problems, Journees Nationales sur la Resolution Pratique de Problemes NP-Complets (1998).
[3] P. Baptiste, B. Legeard, M. Manier and C. Varnier, A scheduling problem optimisation solved with constraint logic programming, in: Proc. of the International Conference on Parallel Architectures and Compilation Techniques (1994) pp. 47-66.
[4] P. Baptiste, B. Legeard and C. Varnier, Hoist scheduling problem: an approach based on constraints logic programming, in: Proc. of the 1992 IEEE International Conference on Robotics and Automation (ICRA'92) (1992) pp. 1139-1144.
[5] C. Chen, C. Chu and J.-M. Proth, Cyclic sheduling of a hoist with time window constraints, IEEE Transactions on Robotic Automation 14 (1998) 144-152.
[6] C. Cheng and S. Smith, A constraint satisfaction approach to makespan scheduling, in: Proc. of the 4th International Conference on Artificial Intelligence Planning Systems (AIPS'96) (1996) pp. 45-54.
[7] J.-P. Denat, S. Collart Dutilleul and S. Marteau, A static robust control of an electroplating line with a periodic output objective, in: 2nd International Conference on Management and Control of Production and Logistics (MCPL'00) (2000).
[8] A. Eremin and M. Wallace, Hybrid benders decomposition algorithms in constraint logic programming, in: Proc. of the 7th International Conference on Principles and Practices of Constraint Programming (CP'01), Cyprus (2001) pp. 1-15.
[9] N. Hall, H. Kamoun and C. Sriskandarajah, Scheduling in robotic cells: classification, two and three machine cells, Operations Research 45 (1997) 421-439.
[10] C. Hanen, Study of a NP-hard cyclic scheduling problem: the recurrent job-shop, European Journal of Operations Research 72 (1994) 82-101.
[11] C. Hanen and A. Munier, Pilotage periodique d'une ligne de galvanoplastie a plusieurs robots, Research report, LITP (1994).
[12] J. Hooker, G. Ottosson, E. Thorsteinsson and H.-J. Kim, A scheme for unifying optimization and constraint satisfaction methods, Knowledge Engineering Review, Special issue on AI/OR 15(1) (2000) 11-30.
[13] IC-Parc, ECL^sup i^PS^sup e^ User Manual Version 5.1, www.icparc.ic.ac.uk (2001).
[14] V. Kats and E. Levner, Minimizing the number of robots to meet a given cyclic structure, Annals of Operations Research 69 (1997) 209-226.
[15] V. Kats, E. Levner and L. Meyzin, Multiple-part cyclic hoist scheduling using a sieve method, IEEE Transactions on Robotics and Automation 15(4) (1999) 704-713.
[16] K. Lam, A heuristic method for multiple hoist scheduling problems by using simulated annealing and local search, Working Paper, Management Science Department, City University of Hong Kong (1997).
[17] J. Lamothe, M. Correge and J. Delmas, Hoist scheduling problem in a real time context, in: 11ieme conference internationale sur l'analyse et l'optimisation des systemes (1994).
[18] L. Lei, R. Armstrong and S. Gu, Minimizing the fleet size with dependent time-window and singletrack constraints, Operations Research Letters 14 (1993) 91-98.
[19] L. Lei and T. Wang, The minimum common-cycle algorithm for cycle scheduling of two material handling hoists with time window constraints, Management Science 37(12) (1991) 1629-1639.
[20] L. Lei and T. Wang, Determining optimal cyclic hoist schedules in a single hoist electroplating line, IEE Transactions 26(2) (1994) 25-33.
[21] J. Leung, X. Yang, R. Mak and K. Lam, Hoist scheduling for a circuit board manufacturing line - a mixed integer programming approach, in: 16th International Symposium on Mathematical Programming (1997).
[22] E. Levner, V. Kats and V. Levit, An improved algorithm for a cyclic robot scheduling problem, in: Intelligent Scheduling of Robots and Flexible Manufacturing Systems, ed. E. Levner, CTEH (1995) pp. 129-141.
[23] E. Levner, V. Kats and C. Sriskandarajah, A geometric algorithm for finding two-unit cyclic schedules in a no-wait robotic flowshop, in: Intelligent Scheduling of Robots and Flexible Manufacturing Systems II, ed. E. Levner, CTEH (1996) pp. 101-112.
[24] J.-M. Lim, A genetic algorithm for a single hoist scheduling in the printed circuit board electroplating line, Computers in Industrial Engineering 33(3-4) (1997) 789-792.
[25] R. Mak, K. Lam and S.M. Gupta, A practical algorithm for cyclic hoist scheduling in a PCB manufacturing facility, Journal of Electronics Manufacturing 8(3/4) (1998) 193-207.
[26] M. Manier, Contribution a l'ordonnanement cyclique du systeme de manutention d'une ligne de galvanosplastie, Ph.D. Thesis, Franche-Comte University (1994).
[27] M. Manier, C. Varnier and P. Baptiste, Constraint based model for cyclic multi-hoist scheduling problem, Production Planning and Control 11(3) (2000) 244-257.
[28] W. Ng and J. Leung, Determining the optimal move times for a given cyclic schedule of a material handling hoist, Computers in Industrial Engineering 32(3) (1997) 595-606.
[29] G. Ottosson and E. Thorsteinsson, Linear relaxations and reduced-cost based propagation of continuous variable subscripts, in: Proc. of the 2nd International Workshop CP-AI-OR'00 (2000) pp. 129-138.
[30] L. Phillips and P. Unger, Mathematical programming solution of a hoist scheduling problem, AIIE Transactions 8(2) (1976) 219-255.
[31] R. Rodosek and M. Wallace, A generic model and hybrid algorithm for hoist scheduling problems, in: Proc. of the 4th International Conference on Principles and Practice of Constraint Programming (CP'98) (1998) pp. 385-399.
[32] R. Rodosek, M. Wallace and M. Hajian, A new approach to integrating mixed integer programming with constraint logic programming, Annals of Operations Research 86 (1997) 63-87.
[33] G. Shapiro and H. Nuttle, Hoist scheduling for a PCB electroplating facility, IIE Transactions 20(2) (1988) 157-167.
[34] W. Song, Z.-B. Zabinsky and R.-L. Storch, An algorithm for scheduling a chemical processing tank time, Production Planning and Control 4(4) (1993) 323-332.
[35] E. Tsang, C. Voudouris, J. Ford and P. Mills, Operations research meets constraint programming: some achievements so far, in: Proc. of the 15th National Conference of the Australian Society for Operations Research (ASOR'99) (1999) pp. 872-883.
[36] C. Varnier, A. Bachelu and P. Baptiste, Resolution of the cyclic multi-hoists scheduling problem with overlapping partitions, INFOR, Special Issue on Intelligent Scheduling of Robots 35(4) (1997) 309-324.
[37] Y. Yih, T. Liang and H. Moskowitz, Robot scheduling in a circuit board production line, an OR/ANN approach, IIE Transactions 25(2) (1993) 26-33.
DANIEL RIERA*
Universitat Autonoma de Barcelona, Spain
NEIL YORKE-SMITH
IC-Parc, Imperial College, London, United Kingdom
DANIEL RIERA*
* Supported by CICYT grant TAP98-0364.
Appendix
As discussed in section 1.2, PU13 is a variant of the classic benchmark problem PU12 in which the tanks are thought of as arranged in a circle. Specifically, an extra tank is added at the front of the line, with minimal treatment time 120 and maximal treatment time unbounded. Jobs are automatically entered into this first tank, and travel times from it to the others are as from the load stage to the tanks in PU12.
We considered three other previously known data sets:
- SZS5: five tank test problem from Song et al. [34],
- LKS9: nine tank problem from Levner et al. [23],
- DEGEM: seven tank real-world process from Kats et al. [15].
We did not use the ten tank benchmark problem 'SSZ' quoted in [15] because it contained non-integer travel times. As discussed in section 4, none of these data sets were challenging. For instance, table 4 gives the results for the problem DEGEM.
RYS16 is a sixteen tank problem of our construction, based loosely on PU13. The data for the problem is as follows, with the empty travel times given in table 5:
m(i) = [0, 120, 150, 100, 120, 90, 200, 25, 60, 0, 60, 45, 130, 120, 90, 30, 30],
M(i) = [0, [infinity], 200, 120, 195, 125, 200, 40, 120, [infinity], 120, 75, [infinity], [infinity], 120, 60, 60],
F(i,i + 1) = [0, 31, 22, 22, 20, 25, 10, 23, 22, 50, 22, 22, 46, 27, 22, 30, 30].
Copyright Kluwer Academic Publishers Sep 2002