Lagrangian relaxation algorithms for hybrid flow-shop
scheduling problems
with limited buffers
Takashi Irohara
Faculty of Science and Technology
7-1 Kioi-cho, Chiyoda-ku,
E-mail:
irohara@sophia.ac.jp
Abstract: In this research, Lagrangian relaxation algorithms are proposed for Hybrid
Flow-Shop (HFS) scheduling problems. Conventional HFS consists of a series of production stages, each
of which has several identical parallel machines and no buffer spaces are
considered. Jobs are processed through all stages in the same direction. In the
previous researches, they are assumed that the capacity of buffer is infinite.
But in the actual manufacturing environment, the maximum capacity of buffer is
limited. That's why HFS with limited buffer is studied in this research.
Unrelated parallel machine is the general and important model of parallel machine,
because this is the model which can consider the difference of machining
performance with large flexibility. But most studies of HFS deal with identical
parallel machines which do not consider the machine abilities. These are the
motivation to study HFS scheduling problem with unrelated parallel machine in
this study. In this research, the objective function is to minimize the total
weighted tardiness and the earliness for each job. Three methods of Lagrangian
relaxation algorithms are proposed to solve the HFS scheduling problem with
limit buffers. In most studies about Lagrangian relaxation algorithm, the
machine capacity constraints are relaxed and each stage is scheduled
separately. But in this study, not only the machine capacity but also the
precedence constraints are relaxed to schedule all stages together. The results
of numerical experiments showed that the proposed methods perform very well
especially for large scale problems.
Keywords: Hybrid flow-shop scheduling,
Lagrangian relaxation algorithm, Combinatorial optimization
1. INTRODUCTION
We focus on a scheduling problem in a hybrid
flow shop (HFS), also called flexible flow shop with multiple processors. In a
typical HFS, there are several serial stages and there are one or more parallel
machines at each stage. HFS scheduling problems are quite common in practice,
especially in the process industry where multiple machines are available at
each stage as well as in certain flexible manufacturing environments (Gupta et
al. 1997).
The HFS considered here consists of a series of
production stages and each stage composed of several unrelated parallel machine
(UPM). Figure 1 illustrates a schematic view of HFS model. UPM can be characterized
as machines that perform the same function but have different capabilities or
capacities. A company may invest in similar machines that have different
capabilities, taking into consideration the capital cost, operation cost and
variability in demand. A fair amount of the research that has been performed on
UPM scheduling has focused on a variety of objectives, ranging from minimizing
the maximum completion time (Lamica 2000, Srivastava 1998), due date related
objective (Bank et al.2001, Kim et al.2002, Kim et al.2003).
As surveyed in Linn and Zhang (1999), there are
many studies on HFS scheduling problems. However, most of them deal with the
objective function to minimize makespan or mean flow time (Dessouky et al.1998,
Portman et al.1998, Kyparisis et al.2006, Jin et al.2006, Tang et al.2006). Despite
the importance of due dates in today's market environment, there are very
limited number of papers on the HFS scheduling problem with the performance
measures related to due dates (Tang et al.2002, Gupta et al.1998), to the best
of our knowledge. Generally, each job has a given due date. If it finishes too
late, it cannot be delivered on time. If it finishes too early, it has to be
stored as inventory. The objective of scheduling is to meet the products' due
dates just in time (Zhang et al. 2000).
A new solution methodology is developed for the
above-mentioned problem based on the Lagrangian Decomposition and Coordination
method (LDC). LDC has recently emerged as a promising method for solving
large-scale integer programming problems including complex scheduling problems.
It introduces the constraints into the objective function by using a vector of
Lagrangian multipliers to form a relaxed problem of the primal problem. For a
given value of the vector of Lagrangian multipliers, the relaxed problem is
usually much easier to solve than the original problem. The optimal values of
the Lagrangian multipliers are searched through solving the Lagrangian dual
problem by using a subgradient algorithm. The technique has successfully been
used to obtain near-optimal solutions for parallel machine scheduling problems
(Luh et al. 1993), flowshop scheduling (Tang et al.2002) and job shop
scheduling (Hoitmt et al. 1993, Luh et al. 1998).
The originality of this research is to consider
the new problem, which is a HFS scheduling problem with limited buffers in
which each stage contains UPM. The objective is to find a schedule, which
minimizes the sum of weighted earliness and tardiness penalty of the due date
for each job. A new solution methodology is developed for the above-mentioned
problem based on the LDC. We decompose our HFS with UPM scheduling problems
into smaller sub-problems at each stage, and we solve the subproblems by the
LDC.
The rest of the paper is organized as follows.
Section 2 first outlines the requirements on the scheduling model. An integer
programming formulation of the HFS scheduling problem with limited buffer is
then presented. Section 3 describes the solution methodology based on the LDC
algorithm. The proposed algorithms and other algorithms are tested on randomly
generated problems, and the results are given in section 4. Finally, section 5
concludes with a short summary.
Figure 1: A schematic view of HFS model
2. MATHEMATICAL FORMULATION
2.1 Problem description
The
problem considered in this paper is described as follows. There are N
jobs to be processed through S stages in series. Each stage j
(j=1,2,...,S)
has unrelated parallel machines. Each job i (i=1,2,...,N)
requires a processing time pij at stage j and
has a due date Di, tardiness penalty Wi, earliness
penalty Ui, all of which are assumed to be positive. Job
processing is assumed to be non-preemptive so that a contiguous block of time
of length pij is needed to process job i at stage j.
All jobs are considered available for processing at time zero and the
scheduling time horizon L is assumed to be long enough to complete
all the jobs. Each machine can handle at most one job at a time while a job can
be processed on at most one machine at any time. The maximum capacity of buffer between stage j and stage j+1 is limited to Vj. The objective is to find a schedule
that minimizes the sum of weighted earliness and tardiness penalty of the due
date for each job.
2.2 The model
Parameters:
S : the number of stages
N : the number of jobs
Di : the due date of job i
L : the planning horizon
Wi : the tardiness penalty of job i
Ui : the earliness penalty of job i
Pijk : the processing time of job i at stage j on machine type k
Mjk : the number of machine type k at stage j
Tj : the number of machine types at stage j
Vj
: the
maximum capacity of buffer between stage j and stage j+1
Decision variables:
ti : the tardiness of job i
ei : the earliness of job i
cij : the completion time of job i at stage j
bij : the beginning time of job i at stage j
pij
: the
processing time of job i at stage j
With the above notation the HFS
scheduling problem under consideration can be formulated as follows.
Note that 
in
the model is the final completion time of job i.
|
|
(1) |
|
subject to |
|
|
|
(2) |
|
|
(3) |
|
|
(4) |
|
|
(5) |
|
|
(6) |
|
|
(7) |
|
|
(8) |
|
|
(9) |
|
|
(10) |
|
|
(11) |
|
|
(12) |
|
|
(13) |
|
|
(14) |
|
|
(15) |
|
|
(16) |
Equation
(1) is used to minimize the total weighted tardiness and the total weighed
earliness for each job. Constraints (2) ~ (5) define ti and ei. Constraints (6)
are the machine capacity constraints. Constraints (7) define the completion
time of each job. Constraints (8), (9) define the processing time for each job.
Constraints (10) define that jobs are processed on one machine type in a stage.
(11), (12) define relationship between δijkl and zijk. Constraints (13)
guarantee that all jobs are completed in the planning horizon. Constraints (14)
are the precedence constraints. (15), (16) are the constraints of capacity of
the buffer.
3. SOLUTION METHODOLOGY
LDC
introduces the constraints into an objective function by using a vector of the
Lagrangian multipliers to form a relaxed problem for the original problem. The
optimal values of the Lagrangian multipliers are searched through solving the
Lagrangian dual problem by using a subgradient algorithm. The following three
methods (A, B and C) to relax the constraints are proposed in this paper.
For a given set of
multipliers, all the sub-problems of the relaxed problem are solved. Because
the resulting solution may be infeasible for the original problem, a heuristic
is applied to covert the infeasible schedule into a feasible schedule. The set
of multipliers is then adjusted based on the degree of constraints violation of
the relaxed solution. With the new set of multipliers, a new relaxed problem is
then formulated and solved. This process continues until the end criterion is
reached. The solution quality is measured by the relative duality gap(
).
The dual objective value provides a lower bound
ZLB
on the optimal value for the original problem while the objective value ZUB
of the feasible schedule is an upper bound for the problem. The details for the
solution of the sub-problems, the construction of feasible schedules, and
updating the Lagrangian multipliers are presented as follows.
3.1 Lagrangian relaxation
In the each proposed relaxation method, the objective function can be
formed as RA, RB and RC
by using a vector of the Lagrangian multipliers 
, which is non-negative value. For given values of, the relaxed problem can be decomposed into smaller
sub-problems, each for one job. The sub-problems for each job i
is given as LiA, LiB and LiC.
Method A: Relaxation of precedence constraints (14)
|
|
(17) |
This leads
to the following decomposed sub-problem for each job i (given 
)
|
|
(18) |
From the
(LiA)
in equation (18), the scheduling of job i becomes the selection of the
optimal beginning time bij*. To do this, (LiA)
is computed for each possible value of bij, and bij*
is the one yielding the lowest value of these (LiA).
The computational complexity of the problem (LiA)
is linear in L (planning horizon) since at most L times evaluations of (LiA)
is needed to determine bij*. This optimization
problem is solved from stage S and the biS* is
assumed to be the due date for stage S-1. Next, the optimization problem
at stage S-1 is solved and the biS-1* is assumed to be the due date for
stage S-2. These processes are repeated until we solve the first
stage and determine the bij*(j=1,2,...,S).
In the each stage, unrelated
parallel machine (UPM) scheduling problem is solved by the LDC based algorithm
proposed by (Watanabe et al.2006). In the UPM scheduling problem, a processing
time of a job is different from the machine type which the job processed. In
proposed method, this UPM scheduling problem is decomposed into two problems.
One is the assignment problem which is to assign jobs to machine types, the
other is scheduling problem on the machine to which jobs are assigned. That
enables to solve this problem as identical parallel machine (IPM) scheduling
problem.
The characteristic of proposed method based on LDC is to solve the
assignment problem efficiently by using the Lagrangian multiplier obtained the
LDC. The value of the Lagrangian multiplier obtained when the LDC is applied to
IPM scheduling problem has the feature that the value is small in the term when
production demand is small and vice versa. We solve the assignment problem by
using this feature to equalize the each machine type's operational rate.
These processes are also applied for the following relaxation method B and
C.
Method B: Relaxation of machine capacity constraints (6)
|
|
(19) |
|
|
(20) |
Method C: Relaxation of machine capacity constraints (6) and precedence
constraints (14)
|
|
(21) |
|
|
(22) |
3.2 Constructing a feasible solution
Because of
the stopping criterion used, the solution in the dual space is generally
associated with an infeasible schedule, because the capacity and/or precedence constraint
might be violated for a few time units. To construct a feasible schedule, a
heuristic approach based on the "list scheduling" concept is developed as
follows.
In the optimal dual solution, each job is
uniquely associated with a beginning time bij*. A list is created
by arranging jobs in the descending order of their respective completion times,
and jobs are scheduled on machines according to this list as machines become
available from the due date of each job. This backward scheduling mechanism is
applied to satisfy the just-in-time requirement of the completion of jobs.
After that, a forward scheduling mechanism is also applied after the backward
scheduling, when the schedule violates the release time constraint. Besides
that, if the completion times of more than two jobs are the same, we consider
the amount of slack to the due date, job weight and expected processing time and
decide the priority in that list. Once a feasible schedule is obtained, the
corresponding value of the objective function is an upper bound on the optimal
objective function value.
3.3 Updating Lagrangian multipliers
In order to
solve the dual problem, the subgradient method (Luh et al.1993) is adopted for
updating the Lagrangian multipliers. In this way, the vectors of Lagrangian multipliers
are updated by (23) and (24).
|
|
(23) |
|
|
(24) |
where 
are the step size at the n the iteration and given by (25)
and (26).
|
|
(25) |
|
|
(26) |
where 
is an upper bound value of the optimal value R
obtained from the best feasible solution found so far and 
is an
lower bound value of R at the nth iteration.
are the subgradient of the Lagrangian
multipliers and calculated in (27) and (28).
|
|
(27) |
|
|
(28) |
4. COMPUTATIONL EXPERIMENTS
To test the
performance of the method and to study the characteristics of the solutions, a
computational experiment has been carried out on randomly generated problem
instances. In this experiment, proposed three relaxation methods are compared.
4.1 Generation of problem instance
For each
data set, ten instances are randomly generated, therefore resulting in a total
of 230 test problems used in this experiment. Here, [x, y] indicates the
uniform distributions with range [x, y]. Table 1 shows the input data summary.
Table1. Parameters for each data set
4.2 Computational results
The performance of each proposed algorithm was examined for small
scale and large scale problems. All the objective function values and CPU time shown in the Table 2 and 3
represent the average performance measures for the ten instances of the
corresponding data set.
4.2.1 Experiment 1
In the small size problem shown in Table 2, all three proposed relaxation algorithm
(Precedence, Capacity and Both constraints relaxation) could find optimal solutions for all the data set (1 through 11). The optimal solutions were
confirmed by solving the integer programming formulation of HFS scheduling
problem by using mathematical programming software (GLPK). The computation time
of proposed algorithm is less than 1 second but the time of GLPK increase
exponentially with the increase of number of jobs.
Table
2. Experimental results for small size problem
4.2.2 Experiment 2
In the large size problems shown in Table3, it is impossible to use the GLPK to
find optimal solution because of too much time consuming. Then we compare the
performance among those proposed algorithms. The second
method, relaxation of
capacity constraints, was the best among them when the
number of stage is small, such as data set 12, 13, 16 and 20. The reason would be that it is more important to consider the relationship between machines
in each stage than the relationship between stages. However, if the
number of stage becomes larger, such as data set 14,15, 18,19,22 and 23, the
third method,
relaxation of both capacity and precedence constraints,
performs very well. Because it would be more important to consider not only the
relationship between machines in each stage, but also the
relationship between stages to optimize all stages together in the large number of stages problems. The computation time of those
methods are also different as shown in Table 3. However, even the longest time
is about 700 seconds for 100 jobs. Such a calculation time is acceptable for
real world use.
Table
3. Experimental results for large size problem
5. CONCLUSION
In this paper, hybrid flow shop scheduling
problem with limited buffer was studied to minimize the total weighted
tardiness and earliness for all jobs. The problem was formulated as an integer
programming model and three Lagrangian relaxation methods were proposed. Results
of numerical experiment for small size problem showed that all of three
proposed methods could find optimal solutions in just a second. Large size
problem experiment showed that the performances of those methods depend on the
problem characteristics, such as number of jobs and stages. If the number of
stage is relatively small, the relaxation of capacity constraints performs
well. However if the number of stage increase, the relaxation of both capacity
and precedence constraints is the best among them. For further research, setup
time between jobs should be considered in the HFS scheduling model.
ACKNOWLEDGMENT
The author
would like to thank Mr. Koji Watanabe who was the master course student in my
research laboratory for conducting the numerical experiments.
REFERENCES
1. Bank, J. and Werner, F., (2001), Heuristic Algorithms for Unrelated Parallel Machine Scheduling with a Common Due Date, Release Dates, and Liner Earliness and Tardiness Penalties, Mathematical and Computer Modelling, 33, 363-383
2. Dessouky, M.M., Dessouky, M.I., and Verma, S.K., (1998) Flowshop scheduling with identical jobs and uniform parallel machines, European Journal of Operational Research, 109, 620-631
3. Gupta, J.D.D., Hariri, A.M.A., and Potts, (1997), Scheduling a two-stage hybrid flow shop with parallel machines at the first stage, Annals of Operations Research, 69, 171-191
4. Gupta, J.N.D., and Tunc, E.A. , (1998), Minimizing tardy jobs in a two-stage hybrid flowshop, International Journal of Production Research, 36, 2397-2417
5. Hoitmt, D.J., Luh, P.B., Max, E. and Patipati, K., (1993), A practical approach to job shop scheduling, IEEE Transactions on Robotics and Automation, 9,1-13.
6. Jin, Z., Yang, Z. and Ito, T.(2006). Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem.
International Journal of Production
Economics, 100: 322 - 334
7. Kim, D.W., Kim, K.H., Jang, W., and Chen, F.F., (2002), Unrelated parallel machine scheduling with setup times using simulated annealing, Robotics and Computer Integrated Manufacturing, 18, 223-231
8. Kim, D.W., Na, D.G., and Chen, F.F., (2003), Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective, Robotics and Computer Integrated Manufacturing, 19, 173-181
9. Kyparisis, G.J., and Koulamas, C. (2006), Flexible flow shop scheduling with uniform parallel machines", European journal of operational research, Vol.168/, pp.985-997
10. Lamica, G., (2000), Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan, European Journal of Operational Research, 120, 277-288
11. Linn, R. and Zhang, W., (1999), Hybrid flow shop scheduling: a survey, Computers and Industrial Engineering, 37, 57-61.
12. Luh, P.B., and Hoitomt, D.J., (1993), Scheduling of Manufacturing Systems Using the Lagrangian Relaxation Technique, IEEE Transactions on automatic control, 38, 1066-1079
13. Luh, P.B., Gou, L., Zhang, Y., Nagahora, T., Tsuji, M., Yoneda, K., Hasegawa,T., Kyoya, Y., and Kano, T., (1998), Job shop scheduling with group-dependent setups, finite buffers and long time horizon, Annals of Operations Research, 76, 233-259
14. Portmann, M.C., Vignier, A., Dardilhac, D., and Dezalay, D., (1998), Branch and bound crossed with GA to solve hybrid flowshops, European Journal of Operational Research, 107, 389-400
15. Srivastava, B., (1998), An effective heuristic for minimizing makespan on unrelated parallel machines, Journal of the Operational Research Society, 49, 886-894
16. Tang, L., Luh, P.B., Liu, J., and Fang, L. (2002), Steel-making process scheduling using Lagrangian relaxation, International Journal of Production Research, 40, 55-70
17. Tang, L., Xuan, H. and Liu, J.(2006). A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time. Computers & Operations Research, 33: 3344 - 3359.
18. Watanabe, K., Toizumi, K. and Irohara, T.(2006). Lagrangian Decomposition and Coordination based Algorithm to Solve an Unrelated Parallel Machine Scheduling Problem, International Symposium on Flexible Automation, Osaka, Japan, July 10-12
Zhang, Y., Luh, P.B., Yondeda, K., Kano, T., and Kyoya, Y., (2000), Mixed-model assembly line scheduling using the Lagrangian relaxation technique, IIE Transactions, 32, 125-1
Leave a comment