)
machines; setup (S) or non-setup (
) machines.
Therefore there are four generic classes of machine types denoted
as 
, 
, 
and 
, representing respectively non-batch
without setup, non-batch with setup, batch without setup, and
batch with setup.
Paper: O/6
Abstract
Scheduling is a key factor for manufacturing
productivity. Effective scheduling can improve on-time delivery,
reduce inventory, cut lead time, and improve machine utilization.
This study was motivated by the design and implementation of
a scheduling system for a helicopter part production cell. The
manufacturing is characterized by the presence of batch machines
that can process multiple parts simultaneously, and the presence
of machines requiring significant setup times. A novel mathematical
optimization model with a separable structure is presented, and
a solution methodology based on a combination of Lagrangian relaxation,
dynamic programming, and heuristics is developed. Numerical results
demonstrate that the method can generate near optimal schedules
with quantifiable quality within a reasonable amount of computation
time on a personal computer.
Keywords: Scheduling, Batch processing, Setup
requirement
1. Introduction
Scheduling is a key factor for manufacturing
productivity. Effective scheduling can improve on-time delivery,
reduce inventory, cut lead time, and improve the utilization of
bottleneck resources. This study was motivated by the design
and implementation of a scheduling system for a helicopter part
production cell. The cell is essentially a job shop, a typical
environment for the manufacture of low-volume and high-variety
parts. The manufacturing is characterized by the presence of
batch machines (e.g., multi-axle NC machines, heat treat ovens)
that can simultaneously process multiple parts with the
same processing requirement, and the presence of certain machines
requiring significant setup times. Operations on the parts are
to be performed on various types of machines according to specific
process plans. The scheduling is to select the machines and beginning
times for individual operations to achieve certain objective(s).
The scheduling problem is believed to be NP
hard where the computational requirements for obtaining an optimal
solution grow exponentially as the problem size increases. Our
goal is therefore to obtain near optimal schedules with quantifiable
quality in a computationally efficient manner. This paper presents
a novel integer optimization formulation, and a methodology based
on a synergistic combination of Lagrangian relaxation (LR), dynamic
programming (DP), and heuristics.
General Description.
Unlike most machines that can process one part at a time, a batch
machine can simultaneously process multiple parts with
the same processing requirement in a "batch," subject
to the physical limitation of the machine (batch volume, or the
maximum number of parts a batch can hold). Parts are thus divided
into "groups" based on their processing requirements
on the specific machine.
Machine setup is another complicating factor
in this study. For some machines, setup times are either negligible
or can be lumped with processing times of individual operations
for scheduling purpose. For other machines, the setup time is
sequence dependent with the following characteristics. Two parts
with the same setup requirement can be processed back to back
on such a machine with negligible adjustment time in-between.
Significant time, however, is needed in-between processing two
parts with different setup requirements. Parts are thus also
divided into "groups" for these "setup machines,"
where the grouping depends on the specific machine under consideration.
Since a setup may take significant amount
of time, it is desirable to cluster operations of the same group
into "runs" to reduce the number of setups, and to improve
machine utilization. This clustering, however, may cause delay
of operations not belonging to this group, resulting in poor scheduling
performance. A trade-off between efficiency and due date performance
has been observed to be a major difficulty for many factories
(Zijm et al., 1995). A similar comment applies to batch machines.
Literature Review.
With the increasing use of batch and setup machines in industry,
scheduling problems considering these special characteristics
attract many researchers. In both literature and practice, heuristics
are the most popular approaches. The scheduling of a batch machine
with a single group of parts was presented in
Ikura and Gimple (1986). The scheduling
of a two- or three-machine flow shop with one batch machine was
examined in Ahmadi et al. (1992). A two-stage heuristic method
for batch machine scheduling was developed in Uzsoy (1995). Optimization-based
approaches are also observed in some literature. A combined Lagrangian
relaxation and linear network flow algorithm was presented in
Liao et al. (1993) to schedule a flow shop with batch machines.
In Wang and Luh (1996), a combined Lagrangian relaxation and
dynamic programming algorithm was developed for scheduling job
shops with batch machines. Scheduling of job shops with group-dependent
setups was addressed in Luh et al (1995).
Overview of the Paper.
A novel "separable" problem formulation is presented
in Section 2. In Section 3, a solution methodology based on a
synergistic combination of Lagrangian relaxation (LR), dynamic
programming (DP), and heuristics is developed. Five test cases
are presented in Section 4 to demonstrate the performance of the
method developed. Numerical results show that the method can
generate near optimal schedules with quantifiable quality within
reasonable amount of computation times.
2. Problem Modeling
Assume that there are H machine types,
and each machine type has several identical machines. Machines
may be classified as batch (B) or non-batch ()
machines; setup (S) or non-setup () machines.
Therefore there are four generic classes of machine types denoted
as , ,
and , representing respectively non-batch
without setup, non-batch with setup, batch without setup, and
batch with setup.
For a 
machine type,
individual operations directly occupy machine capacity as in Hoitomt
et al. (1993). For a 
machine type, since
operations are performed in batches, batches occupy machine capacity,
and serve as virtual facilities to host operations on parts.
For a 
machine type, operations with the
same setup requirements are performed in "runs." Each
run starts with a setup followed by operations assigned to the
run, and these operations share the same setup. The runs thus
occupy machine capacity, and serve as virtual facilities to host
operations on parts. The similarity of runs and batches results
in a symmetric modeling of 
and 
machine types.
A 
machine type can
be considered as an extension of a 
or
a 
type. In a 
machine type, operations form batches, batches form runs, and
runs in turn occupy machine capacity. A hierarchical structure
can thus be created for operations, batches, and runs on a 
machine type. As will be shown later, this symmetric and hierarchical
structure facilitates the step-by-step modeling and resolution
of the problem, and can be easily extended to other similar problems.
Suppose there are I parts to be scheduled.
Part i (i=0,…I-1) consists of Ji sequential
operations, and operation j (j=0,…,Ji-1)
of part i is denoted as (i,j). An operation requires
a specific type of machines to process for Pij amount of
time. For a batch or setup machine type h, operations
are classified as Gh groups. Operations in group g
of a batch machine type h, denoted as (h,g), are
processed in 
batches. Batch n
of group (h,g) is denoted as batch (h,g,n). Similarly,
for a setup machine type h, the number of runs is denoted
as 
, and (h,g,r) denotes run r
of group (h,g).
In the following, an optimization model for
the scheduling problem is presented building on what was presented
in Hoitomt et al. (1993) where only 
machine
types are considered.
Batch Constraints.
As mentioned earlier, operations of the same group may be simultaneously
processed in a batch subject to the finite volume of the batch
machine (a physical limitation). A key to obtain a separable
formulation is the using of batches as virtual facilities to host
the operations. The batch processing capability can thus be translated
into an equivalent one: "The number of group g operations
beginning at time k on batch machine type h may
not exceed the batch capacity beginning at that time," i.e.,
(1)
In the above, Vhg represents the batch
volume, and 
is a 0-1 operation-level
variable that equals 1 if operation (i,j) starts at k
on machine type h, and 0 otherwise. Similarly, 
is a 0-1 batch-level variable, which equals 1 if batch (h,g,n)
starts at k, and 0 otherwise.
Machine Capacity Constraints for Batch
Machine Types. The number
of batches being processed on a machine type h at time
k may not exceed Mh, the number of type h
machines, i.e.,
(2)
where hgnk is a 0-1 batch-level variable,
which equals 1 if batch (h,g,n) is being processed at time
k, and 0 otherwise.
Operation Precedence.
An operation cannot be started until its preceding operation
is finished, i.e.,
, (3)
where cij and bi,j+1 are the
completion time of operation (i,j), and the beginning time
of operation (i,j+1), respectively.
Batch Precedence.
Batch precedence is defined within each group in the ascending
order of batch index, and can be specified by a set of constraints
similar to (3).
Processing Time Requirements.
Each operation must be assigned the required amount of time for
processing on the selected machine type, i.e.,
. (4)
Because of the symmetry between 
and 
, the above constraints can be easily
extended to handle 
machine types by replacing
batch-level variables with run-level variables, and modifying
batch constraints accordingly. Constraints for BS machine types
can then be derived following the hierarchy of operations, batches
and runs.
Objective.
The goal of on-time delivery and low work-in-process inventory
is modeled as a weighted tardiness and earliness penalties, i.e.,
, (5)
where wi and i are the tardiness and
earliness weights of part i, respectively. The tardiness
Ti is defined as the amount the part completion time passes
its due date. The earliness Ei is similarly defined as
the amount the part beginning time (beginning time of the part's
first operation) leads the desired part release time.
The overall problem is to minimize the penalty
function (5) subject to the above constraints by selecting appropriate
machine types for individual operations, operation beginning times
bij, batch beginning time bhgn and run beginning
time bhgr. Since all the constraints are linear and the
objective function is additive, the model is "separable,"
which is essential for Lagrangian relaxation to be effective.
3. Solution Methodology
Lagrangian Relaxation Framework.
Similar to the pricing concept of
a market economy, the Lagrangian relaxation method replaces ìhardî
coupling constraints (e.g., machine capacity and batch constraints)
by the "soft" ìpricesî (i.e., Lagrange
multipliers) for the use of a machine, a batch, or a run at each
time unit. The "relaxed problem" can then be decomposed
into many smaller and easier subproblems. The solutions of individual
subproblems, when put together, may not constitute a feasible
schedule since coupling constraints have been relaxed by the multipliers.
These multipliers are thus iteratively adjusted based on the
degree of constraint violations, following again the market economy
mechanism. Subproblems are then re-solved based on the new set
of multipliers. In mathematical terms, a ìdual functionî
is maximized in the multiplier updating process, and values of
the dual function serve as lower bounds to the optimal feasible
cost.
Subproblem solutions, when put together,
may not constitute a feasible schedule. A simple heuristic is
thus used based on subproblem solutions to provide a feasible
schedule satisfying all the constraints. Optimization and heuristics
thus operate in a synergistic fashion to generate effective schedules.
The quality of the feasible schedule can be quantitatively evaluated
by comparing its cost to the largest lower bound provided by the
dual function. The steps are highlighted next.
Problem Decomposition.
By using Lagrange multipliers hk, hgk and hgk to relax machine
capacity, batch, and run constraints, respectively, the relaxed
problem is obtained. By regrouping relevant terms, the relaxed
problem can be decomposed into part, batch and run subproblems.
Part subproblem:
A part subproblem reflects the needs to balance tardiness
penalty, earliness penalty, and the costs for using 
machines, runs and batches, i.e.,
. (6)
Batch subproblem:
A batch subproblem is similar to (6), and reflects a balance
between the costs for using the batch machine type and/or runs,
and the value for providing the volume to host operations.
Run subproblem:
A run subproblem is also similar to (6), and reflects a balance
between the costs for using the setup machine type and the value
for host operations and/or batches.
DP for Subproblems.
Dynamic Programming (DP) is an effective method for solving multistage
optimization problems. Each subproblem presented above can be
viewed as a multistage optimization problem with each stage corresponding
to an operation, a batch or a run. A forward DP for solving part
subproblems is presented in Chen et al. (1995). In this paper,
the backward DP presented in Luh et al. (1997) is used for solving
the subproblems.
Considering a part subproblem for example,
the backward DP algorithm starts with the last stage, and computes
the tardiness penalty and the operation costs. As the algorithm
moves backwards, the cumulative costs of other stages are recursively
computed subject to the operation precedence defined by (3).
Finally, the subproblem cost is obtained as the minimal of the
cumulative costs at the first stage, and the optimal beginning
times and machine types for individual operations are obtained
by tracing forwards the stages.
Batch and run subproblems can be similarly
solved by extending the above DP algorithm.
Dual Problem.
With optimal subproblem costs denoted by 
and 
, the dual problem is:
(7)
An interleaved subgradient method (Kaskavelis
and Caramanis, 1995) is used to solve
the dual problem.
Obtaining a Feasible Schedule.
As mentioned earlier, a heuristic is used
to adjust subproblem solutions to obtain a feasible schedule.
Operations assigned to a batch machine are first arranged in
the ascending order of their beginning times. Batches are formed
based on this list subject to the volume of the batch machine.
If the batch machine requires setups, runs are in turn formed
by those batches. For a non-batch setup machine, runs are formed
directly by operations assigned to the machine. A list of the
resulting batches and runs together with standard operations is
created in the ascending order of their beginning times. Operations,
batches and runs are then scheduled on the required machine types
according to this list as machines become available. If a machine
capacity constraint is violated at time k, a greedy heuristic
determines which operations, batches, or runs should begin at
that time, and which ones are to be delayed by one time unit.
The process repeats until all operations are scheduled.
The cost J of the feasible schedule is an
upper bound on the optimal cost J*. The optimal dual
value D*, on the other hand, is a lower bound on J*.
Since it is usually difficult to find J* and D*,
the (relative) duality gap (J-D)/D is often used as a measure
of the quality of the feasible schedule.
4. Numerical Results
The method presented above has been implemented
using the object-oriented programming language C++, and testing
is performed on a Pentium Pro200 personal computer. Five cases
are presented here to demonstrate the performance of the algorithm
implemented (denoted as A1). To illustrate the advantage of explicit
modeling batch processing and machine setup, the first two cases
are re-tested with a simplified algorithm (denoted as A2). In
A2, all the machines are treated as 
during
optimization, with setup times lumped with operation processing
times. The same heuristic considering batch processing and setups
is then used to obtain feasible schedules.
To demonstrate the consistency of algorithm
A1 in generating high quality schedules, the first two cases are
also tested by using a heuristic method (denoted as A3) that combines
the "earliest due date (EDD)" and "shortest processing
time (SPT)" rules. In A3, a list of unassigned operations
is created and initialized with the first operations of all parts.
The operations are then scheduled as the required machines become
available. Once an operation is scheduled, it is removed from
the list with its subsequent operation added in. The process
repeats until all the operations are scheduled.
Case 1.
This case is to demonstrate the ability of the method to generate
near optimal schedule for a job shop with batch machines. There
are two 
machine types (h=1,2) each with
two machines, and one 
machine (h=3).
Ten parts are to be scheduled, and each part consists of one
or two standard operations and a batch operation. Batch operations
are classified as two groups, with batch volumes 2 and 3, respectively.
The group id (G), operation processing times (P), and part due
dates (D) are shown in Table 1. The tardiness and earliness weights
for each part are 1 and 0, respectively. The scheduling horizon
is 50, and the total number of multipliers is 250.
By running algorithm A1 for 17 seconds,
a feasible schedule as shown in Table 1 is obtained with a cost
561, and the corresponding dual cost 555.44. If the algorithm
is kept on running to 60 seconds, the feasible cost remains unchanged,
and the dual cost is improved to 560.98. Since the dual cost
is a lower bound to the optimal cost, and the feasible cost should
be integer for this case, the schedule obtained is actually optimal.
To illustrate the advantage of explicit
modeling batch machines, the problem is re-solved by treating
the batch machine as a 
machine in the optimization model, but considering batch processing
characteristics in the heuristics. The resulting schedule for
this simplified model has a cost 585, which is 4% higher.
The problem is also solved by using the
combined EDD and SPT method (A3). The resulting schedule with
the same cost as obtained by A1 is also presented in Table 1.
The method thus also generates an optimal schedule for this case.
Table 1. Data and Schedules for Case 1
| i, j | h | G | P | D | Schedules (b - c)* by using
A1 A2 A3 | ||
| 0,0 | 1 | 2 | 2 | 0 - 1 | 0 - 1 | 0 - 1 | |
| 0,1 | 2 | 2 | 3 - 4 | 3 - 4 | 3 - 4 | ||
| 0,2 | 3 | 1 | 4 | 5 - 8 | 5 - 8 | 5 - 8 | |
| 1,0 | 2 | 3 | 2 | 0 - 2 | 0 - 2 | 0 - 2 | |
| 1,1 | 1 | 1 | 3 - 3 | 3 - 3 | 4 - 4 | ||
| 1,2 | 3 | 1 | 4 | 5 - 8 | 5 - 8 | 5 - 8 | |
| 2,0 | 2 | 1 | 4 | 0 - 0 | 0 - 0 | 0 - 0 | |
| 2,1 | 3 | 1 | 4 | 1 - 4 | 1 - 4 | 1 - 4 | |
| 2,2 | 1 | 1 | 5 - 5 | 9 - 9 | 5 - 5 | ||
| 3,0 | 1 | 1 | 4 | 0 - 0 | 0 - 0 | 0 - 0 | |
| 3,1 | 3 | 1 | 4 | 1 - 4 | 1 - 4 | 1 - 4 | |
| 3,2 | 2 | 3 | 5 - 7 | 5 - 7 | 5 - 7 | ||
| 4,0 | 1 | 2 | 6 | 1 - 2 | 1 - 2 | 2 - 3 | |
| 4,1 | 3 | 2 | 5 | 9 - 13 | 9 - 13 | 9 - 13 | |
| 5,0 | 1 | 1 | 6 | 2 - 2 | 2 - 2 | 1 - 1 | |
| 5,1 | 3 | 2 | 5 | 9 - 13 | 9 - 13 | 9 - 13 | |
| 5,2 | 2 | 2 | 14 - 15 | 14 - 15 | 14 - 15 | ||
| 6,0 | 2 | 3 | 6 | 3 - 5 | 3 - 5 | 1 - 3 | |
| 6,1 | 3 | 2 | 5 | 9 - 13 | 9 - 13 | 9 - 13 | |
| 7,0 | 1 | 4 | 8 | 6 - 9 | 6 - 9 | 2 - 5 | |
| 7,1 | 3 | 2 | 5 | 14 - 18 | 14 - 18 | 14 - 18 | |
| 8,0 | 2 | 2 | 8 | 1 - 2 | 1 - 2 | 4 - 5 | |
| 8,1 | 3 | 2 | 5 | 14 - 18 | 14 - 18 | 14 - 18 | |
| 9,0 | 1 | 4 | 8 | 3 - 6 | 5 - 8 | 6 - 9 | |
| 9,1 | 3 | 2 | 5 | 14 - 18 | 14 - 18 | 14 - 18 | |
* operation beginning and completion times
Case 2.
This case is to demonstrate the effects of explicit modeling
setup machines. There are two 
machine
types each with a single machine, and one 
machine. Ten parts, each with due date 0 or 2 are scheduled.
Each part has two operations on 
machine
types, and one operation on the 
machine.
The operations on the 
machine belong
to three groups with setup times 4, 2, and 1, respectively. The
time horizon is 66, and the number of multipliers is 390.
By running algorithm A1 for 14 seconds,
a feasible schedule as shown in Table 2 is obtained with a cost
5946 and a dual cost 5658. In this
schedule, the ten operations on the 
machine
are clustered into four runs. Excessive setups are thus avoided.
To illustrate the advantage of explicit modeling
setups, the problem is re-solved by treating the 
machine as a 
machine with setup times
lumped into individual processing times in the optimization model,
but considering setups in the heuristics. The schedule obtained
based on the simplified model is also presented in Table 2. The
schedule requires one more setup than the schedule by A1, and
has a cost 6512, which is 10% higher than the cost obtained by
A1.
The problem is also solved by using a combined
EDD and SPT approach (A3). The resulting schedule requires eight
setups, and has a cost 9668, which is 63% higher than the cost
by A1.
Table 2. Data and Schedules for Case 2
| i, j | h | G | P | D | Schedules (b - c) by using
A1 A2 A3 | ||
| 0,0 | 1 | 2 | 0 | 2 - 3 | 8 - 9 | 0 - 1 | |
| 0,1 | 2 | 1 | 1 | 4 - 4* | 14 - 14* | 4 - 4* | |
| 0,2 | 3 | 1 | 5 - 5 | 15 - 15 | 5 - 5 | ||
| 1,0 | 1 | 2 | 0 | 10 - 11 | 0 - 1 | 2 - 3 | |
| 1,1 | 2 | 2 | 3 | 14 - 16* | 2 - 4* | 7 - 9* | |
| 1,2 | 3 | 3 | 17 - 19 | 5 - 7 | 10 - 12 | ||
| 2,0 | 1 | 4 | 0 | 18 - 21 | 14 - 17 | 7 - 10 | |
| 2,1 | 2 | 2 | 4 | 24 - 27 | 21 - 24 | 15 - 18* | |
| 2,2 | 3 | 41 | 28 - 31 | 25 - 28 | 19 - 22 | ||
| 3,0 | 1 | 7 | 0 | 22 - 28 | 22 - 28 | 11 - 17 | |
| 3,1 | 2 | 1 | 5 | 29 - 33 | 33 - 37* | 23 - 27* | |
| 3,2 | 3 | 5 | 34 - 38 | 38 - 42 | 28 - 32 | ||
| 4,0 | 1 | 3 | 0 | 4 - 6 | 2 - 4 | 4 - 6 | |
| 4,1 | 2 | 3 | 2 | 7 - 8* | 6 - 7* | 11 - 12* | |
| 4,2 | 3 | 15 | 9 - 9 | 8 - 8 | 13 - 13 | ||
| 5,0 | 1 | 2 | 2 | 0 - 1 | 12 - 13 | 18 - 19 | |
| 5,1 | 2 | 1 | 1 | 5 - 5 | 15 - 15 | 28 - 28 | |
| 5,2 | 3 | 1 | 6 - 6 | 16 - 16 | 33 - 33 | ||
| 6,0 | 1 | 2 | 2 | 16 - 17 | 10 - 11 | 20 - 21 | |
| 6,1 | 2 | 2 | 3 | 21 - 23 | 18 - 20* | 34 - 36* | |
| 6,2 | 3 | 3 | 25 - 27 | 21 - 23 | 37 - 39 | ||
| 7,0 | 1 | 4 | 2 | 12 - 15 | 18 - 21 | 25 - 28 | |
| 7,1 | 2 | 2 | 4 | 17 - 20 | 25 - 28 | 37 - 40 | |
| 7,2 | 3 | 4 | 21 - 24 | 29 - 32 | 41 - 44 | ||
| 8,0 | 1 | 7 | 2 | 29 - 35 | 29 - 35 | 29 - 35 | |
| 8,1 | 2 | 1 | 5 | 36 - 40 | 38 - 41 | 45 - 49* | |
| 8,2 | 3 | 5 | 41 - 45 | 43 - 47 | 50 - 54 | ||
| 9,0 | 1 | 3 | 2 | 7 - 9 | 5 - 7 | 22 - 24 | |
| 9,1 | 2 | 3 | 2 | 10 - 11 | 8 - 9 | 30 - 31* | |
| 9,2 | 3 | 1 | 12 - 12 | 10 - 10 | 34 - 34 | ||
* A setup is needed before the operation.
The above numerical results show that the
schedules generated by algorithm A1 are close to an optimal schedule.
By comparing results of A1 and A2, it can be seen that the schedule
quality is significantly improved by the explicit modeling of
batch machines and setup requirements. The combined EDD and SPT
approach (A3) generates an optimal schedule in case 1, but a very
poor schedule in case 2 as compared to the schedule obtained by
A1. Algorithm A1 thus outperforms the other two methods, and
can consistently generate high quality schedules.
The following two cases are to demonstrate
the performance of the method for larger data sets.
Case 3.
The machines are the same as for Case 1. Forty
parts with a total of 100 operations are to be scheduled. The
scheduling horizon is 210, and the total number of multipliers
is 1050. The feasible schedule has a cost of 212,842 with a lower
bound of 200,632, and is obtained within 245 seconds.
By doubling the processing times of all
operations on the batch machine, the time horizon and the number
of multipliers are increased to 420 and 2100, respectively. The
schedule obtained has a cost of 261,834 with a lower bound of
224,096, and is obtained within 305 seconds. If the algorithm
is kept on running to 1200 seconds, a feasible cost 253,971 is
obtained, and the dual cost is improved to 224,485.
With the above change in operation processing
times, the feasible cost increases significantly. It indicates
that the batch machine is now the bottleneck, and is critical
for scheduling performance.
Case 4.
The machines are the same as for Case 2. Forty
parts with a total of 120 operations are to be scheduled. The
scheduling horizon is 205, and the total number of multipliers
is 1230. The resulting feasible schedule has a cost of 213,856
with a lower bound of 208,733, and is obtained in 178 seconds.
By adding setup requirements to one of
the 
machines,
the time horizon and the number of multipliers are increased to
243 and 1944, respectively. The feasible schedule has a cost
of 256,072 with a lower bound of 220,486, and is obtained within
226 seconds. The additional setup times on the machine cause
the increase of the feasible cost.
The results of Case 3 and Case 4 demonstrate
that the method can generate high quality schedules for large
problems.
Case 5.
This case draws data from the helicopter part production cell.
There are eight machine types with
three 
, two 
,
two 
and one BS. Each machine type may
have one or two identical machines, and the total number of machines
is 14. Twenty parts with a total of 160 operations are to be
scheduled. The scheduling horizon is 360, and the total number
of multipliers is 3800.
The problem is solved by using the method
developed (A1). Results at selected iterations are summarized
in Table 3 to show the improvement on both feasible schedule and
lower bound as the number of iterations increases.
Table 3. Testing Results for Case 5
| # Iterations | Feasible Cost | Dual Cost | Sec* |
| 20 | 333299 | 12613 | 11 |
| 100 | 22752 | 15160 | 53 |
| 200 | 22546 | 15733 | 102 |
| 500 | 22546 | 15893 | 248 |
* computation times in seconds
Results in Table 3 show that the method developed
keeps on improving schedule quality by reducing the feasible cost
and improving the lower bound by maximizing the dual function.
A good schedule is obtained within 100 iterations or one minute
of computation time.
Because of the large number of multipliers
involved in this case, the slow increase of the dual cost is observed.
Also, a relatively large gap exists between feasible cost and
dual cost within the given number of iterations. Research on
these two issues is currently underway.
5. Conclusions
In this paper, the scheduling of manufacturing
systems with batch and/or setup machines is addressed. A novel
integer programming formulation is presented, where the separable
modeling with manageable numbers of variables and constraints
is of particular significance. A method based on a synergistic
combination of LR, DP, and heuristics is developed to generate
near-optimal solutions with quantifiable quality. Five test cases
demonstrate that the method is effective and computationally efficient.
Acknowledgments.
This work was supported in part by the National Science Foundation
under Grant DMI-9500037, United Technologies Research Center,
and the Advanced Technology Center for Precision Manufacturing,
the University of Connecticut.
References
(1) Ahmadi, J.H., Ahmadi, R.H., Dasu, S., Tang, C.S., 1992, Batching and Scheduling Jobs on Batch and Discrete Processors, Operations Research, 40:750-763