Discrete Lotsizing and Scheduling by Batch Sequencing.
The discrete lotsizing and scheduling problem for one machine with sequence-dependent setup times and setup costs is solved as a single machine scheduling problem, which we term the batch sequencing problem. The relationship between the lotsizing problem and the batch sequencing problem is analyzed. The batch sequencing problem is solved with a branch & bound algorithm which is accelerated by bounding and dominance rules. The algorithm is compared with recently published procedures for solving variants of the DLSP and is found to be more efficient if the number of items is not large.
Introduction
In certain manufacturing systems a significant amount of setup is required to change production from
one type of products to another, such as in the scheduling of production lines or in chemical engineering.
Productivity can then be increased by batching in order to avoid setups. However, demand for different
products arises at different points in time within the planning horizon. To satisfy dynamic demand, either
large inventories must be kept if production is run with large batches or frequent setups are required if
inventory levels are kept low. Significant setup times, which consume scarce production capacity, tend
to further complicate the scheduling problem. The discrete lotsizing and scheduling problem (DLSP) is a
well-known model for this situation.
In the DLSP, demand for each item is dynamic and back-logging is not allowed. Prior to each production
run a setup is required. Setup costs and setup times depend on either the next item only (sequence
independent), or on the sequence of items (sequence dependent). Production has to meet the present or
future demand, and the latter case also incurs holding costs. The planning horizon is divided into a finite
number of (short) periods. In each period at most one item can be produced, or a setup is made ("all
or nothing production"). An optimal production schedule for the DLSP minimizes the sum of setup and
holding costs.
The relationship between the DLSP and scheduling models in general motivated us to solve the DLSP as a
batch sequencing problem (BSP). We derive BSP instances from DLSP instances and solve the DLSP as a
BSP. Demand for an item is interpreted as a job with a deadline and a processing time. Jobs corresponding
to demand for the same item are grouped into one family. Items in the DLSP are families in the BSP.
All jobs must be processed on a single machine between time zero and their respective deadlines, while
switching from a job in one family to a job in another family incurs (sequence dependent) setup times and
setup costs. Early completion of jobs is penalized by earliness costs which correspond to holding costs.
As for the DLSP, an optimal schedule for the BSP minimizes the sum of setup costs and earliness costs.
The DLSP was first introduced by Lasdon and Terjung [10] with an application to production scheduling
in a tire company. Complexity results for the DLSP and its extensions are examined in Salomon et al. [14],
where the close relationship of the DLSP to job (class) scheduling problems is emphasized. A broader view
on lotsizing and scheduling problems is given in Potts and Van Wassenhove [13]. An approach based on
lagrangean relaxation is proposed by Fleischmann [6] for the DLSP without setup times. Fleischmann [7]
utilizes ideas from solution procedures for vehicle routing problems to solve the DLSP with sequence
dependent setup costs. The DLSP with sequence independent setup times and setup costs is examined
by Cattrysse et al. [4]. In a recent work, Salomon et al. [15] propose a dynamic programming based
approach for solving the DLSP with sequence dependent setup times and setup costs to optimality. The
results of [4], [7] and [15] will serve as a benchmark for our approach for solving the BSP.
The complexity of scheduling problems with batch setup times is investigated by Bruno and Downey [2]
and Monma and Potts [12]. Bruno and Downey show the feasibility problem to be NP-hard if setup times
are nonzero. Solution procedures for scheduling problems with batch setup times are studied in Unal and
Kiran [17], Ahn and Hyun [1] and Mason and Anderson [11]. In [17] the feasibility problem of the BSP is
addressed and an effective heuristic is proposed. In [1] and [11], algorithms to minimize mean flow time
are proposed. Webster and Baker [20] survey recent results and derive properties of optimal schedules for
various batching problems.
The contribution of the paper is twofold. First, we solve the DLSP as a BSP and state the equivalence
between both models such that we can solve either the DLSP or the BSP. Second, we present an algorithm
that solves the BSP faster than known procedures solving the DLSP.
The paper is organized as follows: we present the DLSP and the BSP in Section 2 and provide a numerical
example in Section 3. The relationship of both models is analyzed in Section 4. Section 5 presents a
timetabling procedure to convert a sequence into a minimum cost schedule, and in Section 6 we describe a
branch & bound algorithm for solving the BSP. A comparison of our algorithm with solution procedures
solving variants of the DLSP is found in Section 7. Summary and conclusions follow in Section 8.
Model Formulations
The DLSP is presented with sequence dependent setup times and setup costs, we refer to this problem as
SDSTSC. SDSTSC includes the DLSP with sequence independent setups (SISTSC), sequence dependent
setup costs but zero setup times (SDSC), and the generic DLSP with sequence independent setup costs
and zero setup times (cf. Fleischmann [6]) as special cases.

Table

1: Parameters of the DLSP
i index of item (=family), denotes the idle machine
t index of periods,
q i;t demand of item i in period t
holding costs per unit and period of item i
st g;i setup time from item g to item i,
g;i setup costs per setup period from item g to item i,
sc g;i setup costs from item g to item i,
st g;i g

Table

2: Decision Variables of the DLSP
Y i;t 1, if item i is produced in period t, and 0 otherwise. Y
time in period t
if the machine is setup for item i in period t, while the previous item
was item g, and 0 otherwise
I i;t inventory of item i at the end of period t
The DLSP parameters are given in Table 1. Items (families) in the DLSP (BSP) are indexed by i, and
holding costs per unit of item i and period. Production has to fulfill the demand q i;t for item i
in period t. Setup costs sc g;i are "distributed" over maxf1; st g;i g setup periods by defining per-period
setup costs sc p
g;i . The decision variables are given in Table 2: we set Y production takes place
for item i in period t. V a setup from item g to item i in period t, and I i;t denotes the
inventory of item i at the end of period t.
In the mixed binary formulation of Table 3, the objective (1) minimizes the sum of setup costs sc p
(per
setup period st g;i ) and inventory holding costs. Constraints (2) express the inventory balance. The "all or
nothing production" is enforced by constraints (3): in each period, the machine either produces at full unit
capacity, undergoes setup for an item, or is idle, i.e. Y for an idle period. For st
instantiate V g;i;t appropriately. Constraints (5) couple setup and production whenever st g;i ? 0: if item i is
produced in period t and item g in period t\Gamma- \Gamma1 then the decision variable V st g;i .
Constraints (6) enforce the correct length of the string of setup variables V g;i;t\Gamma- for st g;i ? 1. However,
for st g;i ? 0 we have to exclude the case Y setting any V this is done
by constraints (7). Constraints (8) prevent any back-logging. Finally, the variables I i;- , V g;i;- , and Y i;-
are initialized for - 0, by constraints (11). Due to the "all or nothing production", we can write down
a DLSP schedule in terms of a period-item assignment in a string - specifies the
action in each period, i.e. - st g;i ? 0).
The BSP is a family scheduling problem (cf. e.g. Webster and Baker [20]). Parameters (cf. Table related
to the N families are the index i, the number of jobs n i in each family, and the total number of jobs J .

Table

3: Model of the DLSP
Min
(1)
subject to
I
st
st
st g;i
st g;i ?
st g;i
st g;i ? 0;
I
I

Table

4: Parameters of the BSP
number of jobs of family i,
number of jobs
denotes the j-th job of family
processing time for the j-th job of family i
d (i;j) deadline for the j-th job of family i
w (i;j) earliness weight per unit time for the j-th job of family i
number

Table

5: Decision variables of the BSP
- sequence of all jobs,
denotes the job at position k
C (i;j) completion time of job (i;
there is idle time between the jobs (i
and 0, otherwise

Table

Model of the BSP
Min ZBSP
subject to
st i [k\Gamma1] ;i [k]
(st 0;i [k]
st i [k\Gamma1] ;i [k]
st i [k\Gamma1] ;i [k]
one unit of family i in inventory for one period of time. Setup times st g;i and setup costs sc g;i are given
for each pair of families g and i. The set of jobs is partitioned into families i, the j-th job of family i is
indexed by the tuple (i; j). Associated with each job (i; are a processing time p (i;j) , a deadline d (i;j) ,
and a weight w (i;j) . Job weights w (i;j) are proportional to the quantity (=processing time) of the job
(proportional weights), they are derived from h i and p (i;j) . We put the tuple in brackets to index the job
attributes because the tuple denotes a job as one entity.
The decision variables are given in Table 5. The sequence - denotes the processing order of the jobs,
denotes the job at position k; together with completion times C (i;j) of each job we obtain the
schedule oe. A conceptual model formulation for the BSP is presented in Table 6. ZBSP (oe) denotes the
sum of earliness and setup costs for a schedule oe, which is minimized by the objective (12). The earliness
weighted by w (i;j) , and setup costs sc i [k\Gamma1] ;i [k]
are incurred between jobs of different
families. Each job is to be scheduled between time zero and its deadline, while respecting the sequence
on the machine as well as the setup times. This is done by constraints (13). Constraints
to one if there is idle time between two consecutive jobs. We then have a setup time st 0;i [k]
from the idle
machine rather than a sequence dependent setup time st i [k\Gamma1] ;i [k]
. Initializations of beginning and end of
the schedule are given in (16) and (17), respectively.
Remark 1 For the BSP and DLSP parameters we assume that:
1. setup times and setup costs satisfy the triangle inequality, i.e. st g;i - st g;l st l;i and sc g;i -
2. there are no setups within a family, i.e. st no tear-down times and costs, i.e.
st
3. there is binary demand in the DLSP, i.e. q i;t 2 f0; 1g.
4. jobs of one family are labeled in order of increasing deadlines, and deadlines do not interfere, i.e.
Remark 1 states in (1.) that it is not beneficial to perform two setups in order to accomplish one. Mason
and Anderson [11] show that problems with nonzero tear-downs can easily be converted into problems
with sequence dependent setups and zero tear-downs, which motivates (2. With (1.) and (2.) we have
st 0;i - st g;i analogously for setup costs. Thus, the third term in the
objective (12) is always nonnegative. Assumption (3.) anticipates the "all or nothing production" for
each item i (cf. also Salomon et al. [14]) and is basically the same assumption as (4.): if only jobs of one
family i are considered, they can be scheduled with C
The main observation that motivated us to consider the DLSP as a special case of the BSP is that the
(q i;t )-matrix is sparse, especially if setup times are significant. The basic idea is to interpret items in
the DLSP as families in the BSP and to regard nonzero demand in the DLSP as jobs with a deadline
and a processing time in the BSP. In order to solve the DLSP as a special case of the BSP we derive
BSP instances from DLSP instances in the following way: setup times and setup costs in the BSP and
Comparison
Equivalence
BSP solution procedure
DLSP instances
DLSP solution procedures
BSP(DLSP) or BSPUT(DLSP)
Solution
Transformation

Figure

1: Comparison of DLSP and BSP
DLSP are identical, and the job attributes of the BSP instances are derived from the (q i;t )-matrix by
Definitions 1 and 2.
defined as a BSP instance with unit time jobs derived from a DLSP
instance. For each family i there are n
jobs. An entry q
denotes a job (i;
defined as a BSP instance derived from a DLSP instance. A sequence of
consecutive "ones" in the (q i;t )-matrix, i.e. q
. The number of times that a sequence of
consecutive ones appears for an item i defines n i .

Figure

1 provides the framework for the BSP-DLSP comparison: after transforming DLSP instances
into BSP instances, we compare the performance of solution procedures and the quality of the solutions.
The difference between the approaches is as follows: in the DLSP, decisions are made anew in each
individual period t, represented by decision variables Y i;t and V g;i;t (cf. Table 2). In the BSP, we decide
how to schedule jobs, i.e. we decide about the completion times of the jobs. BSP and DLSP address
the same underlying planning problem, but use different decision variables. Br-uggemann and Jahnke [3]
make another observation which concerns the transformation of instances: a DLSP instance may be not
polynomially bounded in size while the size of the BSP(DLSP) instance is polynomially bounded. On that
account, in [3] it is argued, that the (q i;t )-matrix is not a "reasonable" encoding for a DLSP instance in
the sense of Garey and Johnson [9] because BSP(DLSP) describes a problem instance in a more concise
way.
3 Numerical Example
In this section, we provide an example illustrating the generation of BSPUT(DLSP) and BSP(DLSP). We
will also refer to this example to demonstrate certain properties of the BSP.
In

Figure

2 we illustrate the equivalence between both models. The corresponding parameters setup times,
setup costs and holding costs are given in Table 7. Figure 2 shows the demand matrix (q i;t ) of DLSP and
the jobs at their respective deadlines of BSPUT(DLSP) and BSP(DLSP).

Table

7: Numerical Example: Setup and Holding Costs
st
a 3 a 3 3 3 a 2
1 a
a
a 1 a 2
BSPUT(DLSP), oe ut
a
BSPUT(DLSP), oe ut
BSP(DLSP), oe d

Figure

2: DLSP, BSPUT(DLSP) and BSP(DLSP)

Table

8: BSPUT(DLSP) Instance and Solution
a
For BSPUT(DLSP), we interpret each entry of "one" as a job (i; j) with a deadline d (i;j) . Processing
times p (i;j) are equal to one for all jobs. We summarize the BSPUT(DLSP) parameters in Table 8. An
optimal DLSP schedule with h is the string - a in Figure 2 (with entries f0; a; 1; 2; 3g for idle or
time or for production of the different items, respectively). This schedule is represented by oe ut
a for
BSPUT(DLSP), and is displayed in Table 8. Both schedules have an optimal objective function value
of ZBSP (oe ut
a
In BSP(DLSP), consecutive "ones" in the demand matrix (q i;t ) are linked to one job. The number of jobs is
thus smaller in BSP(DLSP) than in BSPUT(DLSP). For instance, jobs (1; 2) and (1; 3) in BSPUT(DLSP)
are linked to one job (1; 2) in BSP(DLSP), compare oe ut
b and oe b . However, a BSP(DLSP) schedule cannot
a in

Figure

2 since there we need unit time jobs. For BSP(DLSP) we now let the cost
parameters costs for all families) and sc is the
optimal DLSP schedule and oe b the optimal BSP(DLSP) schedule. Again, the optimal objective function
value is ZBSP (oe b
The example shows that the same schedules can be obtained from different models. In the next section
we formally analyze the equivalence between the DLSP and the BSP.
4 Relationship Between BSPUT(DLSP), BSP(DLSP) and DLSP
In the BSP we distinguish between sequence and schedule. A BSP schedule may have inserted idle
time so that the processing order does not (fully) describe a schedule. In the following we will say that
consecutively sequenced before job (i is sequenced at the next position. If
we consecutively schedule job (i there is no idle time between both jobs, i.e. the term
in brackets in constraints (14) equals zero. A sequence - for the BSP consists of groups, where a group is
an (ordered) set of consecutively sequenced jobs which belong to the same family. On the other hand, a
schedule consists of (one or several) blocks. Jobs in one block are consecutively scheduled, different blocks
are separated by idle time (to distinguish from setup time). Jobs in one block may belong to different
families, and both block and group may consist of a single job. As an example refer to Figure 2 where
both oe c and oe d consist of five groups, oe c forms two blocks, and oe d is only one block.
For a given sequence -, a BSP schedule - oe is called semiactive if C (i;j) is constrained by either d (i;j) or
the start of the next job; no job can be scheduled later or rightshifted in a semiactive schedule - oe. We can
derive - oe from a sequence - if constraints (13) are equalities and P k is set to zero. The costs ZBSP (-oe) are
a lower bound for costs ZBSP (oe) of a BSP schedule oe because -
oe is the optimal schedule of the relaxed
BSP in which constraints (14) are omitted. However, in the semiactive schedule there may be idle time
and it may be beneficial to schedule some jobs earlier, i.e. to leftshift some jobs to save setups (which will
be our concern in the timetabling procedure in Section 5).
In both models we save setups by batching jobs. In the DLSP, a batch is a non-interrupted sequence of
periods where production takes place for the same item i 6= 0, i.e. Y . In the BSP, jobs
of one group which are consecutively scheduled without a setup are in the same batch. A batch must not
be preempted by idle time. In Figure 2, the group of family 3 forms two batches in schedule oe c whereas
this group is one batch in oe b .
We will call a sequence - (schedule oe) an EDDWF sequence (schedule) if jobs of one family are sequenced
(scheduled) in nondecreasing order of their deadlines (where EDDWF abbreviates earliest deadline
within families). Ordering the jobs in EDDWF is called ordered batch scheduling problem in Monma
and Potts [12]. By considering only EDDWF sequences, we reduce the search space for the branch & bound
algorithm described in Section 6.
We first consider BSPUT(DLSP) instances. The following theorem states, that for BSPUT(DLSP) we
can restrict ourselves to EDDWF sequences.
Theorem 1 Any BSPUT(DLSP) schedule oe can be converted into an EDDWF schedule ~ oe with the same
cost.
Proof: Recall that jobs of one family all have the same weights and processing times. In a schedule
oe, let A; B; C represent parts of oe (consisting of several jobs), and
(processing) times of the parts. Consider a schedule where jobs are not ordered in EDDWF,
i.e. . The schedule ~
has the same objective function value
because w (i;j 1 . The completion times of the parts A; B; C do not change because
Interchanging jobs can be repeated until oe is an EDDWF schedule, completing
the proof. 2
A DLSP schedule - and a BSPUT(DLSP) schedule oe are called corresponding solutions if they define the
same decision. A schedule schedule oe are corresponding solutions if for each
point in time the following holds: (i) - in oe the job being processed at t belongs to
family a and a setup is performed in oe, and (iii) - and the machine is idle in oe.

Figure

2 gives an example for corresponding solutions: - a corresponds to oe ut
a , and - b corresponds to oe ut
b .
We can always derive entries in - from oe, and completion times in oe can always be derived from - if oe
is an EDDWF schedule.
Theorem 2 A schedule oe is feasible for BSPUT(DLSP) if and only if the corresponding solution - is
feasible for DLSP, and - and oe have the same objective function value.
Proof: We first prove that the constraints of DLSP and BSPUT(DLSP) define the same solution space.
In the DLSP, constraints (2) and (8) stipulate that
. For each q i;t ? 0
(2) and (8) enforce a Y t. The sequence on the machine - the sequence dependent
setup times taken into account - is described by constraints (3) to (7). In the BSP this is achieved by
constraints (13). We schedule each job between time zero and its deadline. All jobs are processed on a
single machine, taking into account sequence dependent setup times.
Second, we prove that the objective functions (1) and (12) assign the same objective function value to
corresponding solutions - and oe: the cumulated inventory for an item i (over the planning horizon
equals the cumulated earliness of family i, and job weights equal the holding costs, i.e. h
for BSPUT(DLSP). Thus, the terms
I i;t and
are equal for corresponding
solutions - and oe.
Some more explanation is necessary to show that corresponding solutions - and oe have the same setup
costs. Consider a setup from family g to i (g; i 6= 0) without idle time in oe: we then have sc
st g;i g and we have st g;i consecutive "ones" in V g;i;t , which is enforced by (6). On the other
hand, in the case of inserted idle time we have a setup from the idle machine (enforced by the decision
variable P k of the BSP) and there are st 0;i consecutive "ones" in V 0;i;t . Thus, the terms
and
are equal for corresponding solutions - and oe. Therefore,
corresponding solutions - and oe incur the same holding and the same setup costs, which proves the
theorem. 2
As a consequence of Theorem 2, a schedule oe is optimal for BSPUT(DLSP) if and only if the corresponding
solution - is optimal for DLSP, which constitutes the equivalence between DLSP and BSP for BSP-
UT(DLSP) instances. We can thus solve DLSP by solving BSPUT(DLSP).
In general, however, the more attractive option will be to solve BSP(DLSP) because the number of jobs
is smaller.
Definition 3 In a schedule oe, let a production start of family i be the start time of the first job in a
batch. Let inventory for family i build between C (i;j) and d (i;j) . The schedule oe is called regenerative if
there is no production start for a family i as long as there is still inventory for family i.
The term "regenerative" stems from the regeneration property found by Wagner and Whitin [19] (for
similar ideas cf. e.g. Vickson et al. [18]). Each regenerative schedule is also an EDDWF schedule, but
the reverse is not true. If a schedule oe is regenerative, jobs (i; are in the same batch if
holds. Furthermore, in a regenerative BSPUT(DLSP) schedule oe, jobs from
consecutive "ones" in (q i;t ) are scheduled consecutively (recall for instance oe ut
b and oe b in Figure 2); hence a
regenerative BSPUT(DLSP) schedule represents a BSP(DLSP) schedule as well. In Figure 2, schedule oe d
is not regenerative: a batch for family is started at there is still inventory for
We first show that we do not lose feasibility when restricting ourselves to regenerative schedules only.
Theorem 3 If oe is a feasible BSPUT(DLSP) or BSP(DLSP) schedule then there is also a feasible regenerative
schedule ~ oe.
A
oe
~
oe
A

Figure

3: Regenerative Schedule
Proof: In a schedule oe, let i B (i A ) be the family to which the first (last) job in part B (A) belongs.
Consider a non-regenerative schedule oe, i.e. are not
in one batch though C
Consider schedule ~
where (i; are interchanged and (i; are in one batch. ~ oe is feasible because
~
leftshifting B we do not violate feasibility. Furthermore, due to the triangle inequality
we have st i A ;i B - st i A ;i st i;i B . Thus, B can be leftshifted by p (i;j) time units without affecting CA .
Interchanging jobs can be repeated until oe is regenerative which proves the theorem. 2
An illustration for the construction of regenerative schedules is depicted in Figure 3. Interchanging (i;
and B, we obtain from oe the regenerative schedule ~
oe.
Unit processing times are not needed for the proof of Theorem 3, so we have in fact two results: first, to
find a feasible schedule we may consider BSP(DLSP) instead of BSPUT(DLSP). Second, for BSP(DLSP)
we only need to search over regenerative schedules to find a feasible schedule. Theorem 3 is a stronger
result than the one found by Salomon et al. [14] and Unal and Kiran [17] who only state the first result.
Moreover, if holding costs are equal, the next theorem extends this result to optimal schedules.
Theorem 4 If oe is an optimal BSPUT(DLSP) or BSP(DLSP) schedule and h i is constant 8i, then there
is also an optimal regenerative schedule ~ oe.
Proof: Analogous to the proof of Theorem 3 we now must consider the change of the objective function
value if (i; are interchanged. Without loss of generality, let h
ZBSP (oe) (ZBSP (~oe)) denote the objective function value of oe (~oe).
For part B, which is leftshifted, we have wB - pB because processing time in part B is at most pB , but B
may contain setups as well. Interchanging B and (i; j), the objective changes as follows:
Due to the triangle inequality, setup costs and setup times in oe are not larger than in ~
oe, i.e. \Gammasc i A ;i \Gamma
explains (i). We leftshift B by p (i;j) and rightshift (i; j) by pB with wB - pB ,
which explains (ii). Thus ZBSP (~oe) - ZBSP (oe), which proves the theorem. 2
Considering regenerative schedules, we again achieve a considerable reduction of the search space. To
summarize we have so far obtained the following results:
1. DLSP and BSP are equivalent for BSPUT(DLSP).
2. Feasibility of BSP(DLSP) implies feasibility of DLSP.
3. For equal holding costs an optimal BSP(DLSP) schedule is optimal for DLSP.
When instances with unequal holding costs are solved, the theoretical difference between BSP(DLSP) and
DLSP in 3. has only a small effect: computational results in Section 7.3 will show that there is almost
always an optimal regenerative BSPUT(DLSP) schedule to be found by solving BSP(DLSP).
5 A Timetabling Procedure for a Given Sequence
For a given sequence - the following timetabling procedure decides how to partition - into blocks, or
equivalently, which consecutively sequenced jobs should be consecutively scheduled. In the BSP model
formulation of Table 6, we have the job at position k starts a new block, or P
blocked with the preceding job. By starting a new block at position k, we save earliness costs at the
expense of additional setup costs. In Figure 2, earliness costs of oe b are higher than for oe c but we save
one setup in oe b .
In the timetabling procedure, we start with the semiactive schedule and leftshift some of the jobs to find a
minimum cost schedule. Consider the example in Figure 2: for the sequence
(3; 3); (2; 2); (1; 2)) the semiactive schedule -
oe is given in Figure 4. We first consider two special cases.
If we omit constraints (14) of the BSP (so that each group is a batch and idle time may preempt the
batch) timetabling is trivial: the semiactive schedule is optimal for a given sequence because no job can
be rightshifted to decrease earliness costs (and because setup costs are determined by - and not by oe).
Timetabling is also trivial if earliness weights are zero (i.e. h
case, we can leftshift each job (without increasing earliness costs) until the resulting schedule is one block
(e.g. schedule oe d in Figure 2 is one block and no job can be leftshifted). We have sc g;i - sc i;0 +sc
setup costs are minimized if jobs are scheduled in a block, and there is an optimal schedule which consists
of one block.
In the general case, we need some definitions: block costs bc k1;k2 are the cost contribution of a block from
position k 1 to k 2 , i.e.
bc k1
The block size bs k is the number of jobs which are consecutively scheduled after job (i
included). For instance, in Figure 4 we have bs
Let denote f k (b) the costs of a schedule from position k to J if bs
k the costs of the
minimum cost schedule and bs
k the corresponding block size at position k. The recurrence equation for
determining f
k and bs
f
b=1;:::;bs
oe
Position k

Figure

4: Semiactive Schedule

Table

9: Computations of Equation (18) for the Example in Figure 4
f
In equation (18) we take the minimum cost for bs
is the maximum
block size at position k (and a new block starts at k+bs
1). For a given block size b, f k (b) is the sum
of block costs from position k to position k
to the next block and the minimum
cost f
k+b . Basically, equation (18) must be computed for every sequence. However, some simplifications
are possible:
if two jobs can be consecutively scheduled in the semiactive schedule, it is optimal to increment bs
bs
so that equation (18) needs not to be evaluated. Consequently, if the
semiactive schedule is one block, timetabling is again trivial: each group in - oe equals one batch, the whole
schedule forms a block, and -
If setups are sequence independent, a minimum cost schedule can be derived with less effort as follows: let
the group size gs k at position k denote the number of consecutively sequenced jobs at positions r ? k that
belong to the same family as job (i [k] ; j [k] ). Then, for sequence independent setups, equation (18) must
be evaluated only for gs k . The reasoning is as follows: jobs of different groups are leftshifted
to be blocked only if we can save setup cost. Then, for consecutive groups of families g and i we would
need sc which does not hold for sequence independent setups; therefore, we only
need to decide about the leftshift within a group.
An example for the computations of equation (18) is given in Table 9 for the semiactive schedule in

Figure

4 (see the cost parameters in Table 7). The schedule - oe contains idle time, and we determine f
and bs
k for each position k, k - J .
Consider jobs (2,2), (3,3) and (3,2) at positions 6,5 and 4 in Figure 4. Up to position 4 the semiactive
schedule is one block, and we increment bs
k , which is denoted by entries (-) in Table 9. After job (3,1),
oe has inserted idle time between positions 3 and 4 (d different block sizes must be
considered to find the minimum cost schedule. In Table 9, we find f
i.e. we start a new block
after position split the group into two batches, as done for oe c in Figure 2. For the objective
function value, we add sc 0;2 to f
1 and obtain a cost of ZBSP (oe c
6 Sequencing Algorithm
In this section we present a branch & bound algorithm for solving the BSP to optimality, denoted as
SABSP. Jobs are sequenced backwards, i.e. at stage 1 a job is assigned to position J , at stage 2 to
position stage s to position assigns s jobs to the last
s positions of sequence -, in addition to that an s-partial schedule oe s also assigns completion times to
each job in - s . A partial schedule ! s is called completion of oe s if ! s extends oe s to a schedule oe which
schedules all jobs, and we write
We only examine EDDWF sequences, as if there were precedence constraints between the jobs. The
precedence graph for the example in Figure 2 is shown in Figure 5. Using the EDDWF ordering, we

Figure

5: EDDWF Precedence Graph for Backward Sequencing

Table

10: Attributes of Partial Schedules
under consideration at stage s
UB upper bound, objective function value of the current best schedule
c(oe s ) cost of oe s without the setup for (i s
AS s (US s ) set of jobs already scheduled (unscheduled) in the s-partial schedule oe s
UI s set of families to which jobs in US s belong to
of jobs which form the first block of oe s
of earliness weights of jobs in G 1 (oe s ), i.e.
decide in fact at each stage s which family to schedule. A job is eligible at stage s if all its (precedence
related) predecessors are scheduled. An s-partial schedule (corresponding to a node in the search tree) is
extended by scheduling an eligible job at stage s + 1. We apply depth-first search in our enumeration and
use the bounding, branching, and dominance rules described in Sections 6.1 and 6.2 to prune the search
tree.
Each (s-partial) sequence - s uniquely defines a minimum cost (s-partial) schedule oe s by the timetabling
procedure. Enumeration is done over all sequences and stops after all sequences have been (implicitly)
examined; the best solution found is optimal. The implementation of SABSP takes advantage of the fact
that equation (18) needs not be recalculated for every oe s and, in the case of backtracking, the computation
of equation (18) has already been accomplished for the partial schedule to which we backtrack.

Table

lists attributes of s-partial schedules. For each scheduling stage s we identify the job (i s
under consideration, and the start time t(oe s ) and costs c(oe s ) of the s-partial schedule. The set of currently
scheduled (unscheduled) jobs is denoted by AS s (US s ). UI s denotes to which families the jobs in US s
belong; UB is the current upper bound.
6.1 Bounding and Branching Rules
The feasibility bound states that for a given oe s , all currently unscheduled jobs in US s must be scheduled
between time zero and t(oe s ) and, furthermore, we need a setup time for each family in UI s . More formally,
define
min
fst
(i;j)2US s
Then, oe s has no feasible completion ! s if t(oe s
The cost bound states that costs c(oe s ) of an s-partial schedule are a lower bound for all extensions of oe s ,
and for any completion ! s at least one setup for each family in UI s must be performed. We define
min
fsc g;i g:
Then, oe s cannot be extended to a schedule improves UB if C s
Both bounds are checked for each s-partial schedule oe s . Clearly, T s and C s can be easily updated during
the search. We also tested a more sophisticated lower bound where all unscheduled jobs were scheduled
in EDD order without setups. In this way we were able to derive a lower bound on the earliness costs as
well and check feasibility more carefully, but computation times did not decrease.
If only regenerative schedules need to be considered to find the optimal schedule (cf. Theorem 4), we
employ a branching rule as follows: scheduling (i s
eligible in the EDDWF precedence graph. If t(oe s
we batch (i s and do not consider any other job as an extension of oe s . We need not
enumerate partial schedules where oe s is extended by a job (g; because then the resulting
schedule is non-regenerative.
6.2 Dominance Rules
The most remarkable reduction of computation times comes as a result of the dominance rules. The
dominance rules of SABSP compare two s-partial schedules oe s and oe s , which schedule the same set of
jobs, so that AS
s
. In this notation, schedule oe s denotes the s-partial schedule currently under
consideration, while oe s denotes a previously enumerated schedule which may dominate oe s . A partial
schedule oe s dominates oe s if it is more efficient in terms of time and cost: oe s starts later to schedule the
job-set, i.e. t(oe s incurs less cost, i.e. c(oe s ) - c(oe s ). If the family i s of the job scheduled
at stage s differs in oe s and oe s we make both partial schedules "comparable" with a setup from i s to
we compare time and cost but subtract setup times and setup costs appropriately.
If a schedule oe s is not dominated, we store for the job set AS s and family i s the pair t(oe s ) and c(oe s )
which is "most likely" to dominate other s-partial schedules. Note that the number of partial schedules is
exponential in the number of items N so that storage requirements for the dominance rules grow rapidly
if N increases.
For a formal description of the dominance rules we need several definitions (cf. Table 10): all jobs
which form a block with (i s belong to the set G 1 (oe s ), and the sum of earliness weights in G 1 (oe s ) is
denoted as w 1 (oe s ). The dominance rules take into account the block costs for all extensions of oe s and oe s :
we consider for oe s the maximum, for oe s the minimum costs incurred by blocking; oe s then dominates oe s
if c(oe s ) plus an upper bound on block costs is less or equal c(oe s ) plus a lower bound on block costs.
An upper bound on the block costs for oe s is given by sc 0;i s (recall that sc 0;i - sc g;i ). Then, oe s starts a
new block. But a tighter upper bound can be found for start times close to t(oe s in order to save costs
we can leftshift all the jobs in G 1 (oe s ) (but only these), because after G 1 (oe s ) we perform a new setup from
the idle machine. G 1 (oe s ) is the largest block which may be leftshifted. Let pbt(oe s ) denote the time where
the cost increase due to a leftshift of G 1 (oe s ) exceeds sc 0;i s . We then have w 1 (oe s )(t(oe s
and define the pull-back-time pbt(oe s ) of an s-partial schedule oe s as follows:
Consequently, for time t, pbt(oe s an upper bound on block costs is given by leftshifting G 1 (oe s );
are bounded by sc 0;i s .
A lower bound on the block costs for oe s is given in the same way as for oe s , but now we consider the
smallest block that can be leftshifted, which is simply job (i s
We can now state the dominance rule: we differentiate between i (Theorem 5) and i s
orem 6).
Theorem 5 Consider two s-partial schedules oe s and oe s with AS
Proof: Any completion ! s of oe s is also a feasible completion of oe s because of (i); if (! s ; oe s ) is feasible,
too. Due to (ii), for any ! s , the schedule (! s ; oe s ) has lower costs than (! s ; oe s ).
In the following we consider the cost contributions of oe s and oe s due to leftshifting, when we extend oe s
and oe s . Consider Figure 6 for an illustration of the situation in a time-cost diagram. We have
due to EDDWF also (i s line represents the upper bound on block costs for oe s .
For pbt(oe s expensive to leftshift G 1 (oe s ), while for t ! pbt(oe s ) a setup from the
idle machine to i s is performed. The broken line represents the lower bound on block costs for oe s . The
smallest block that can be leftshifted is the job (i s
In order to prove that oe s will never have less costs than oe s due to blocking, we check the costs at points (ii)
and (iii): at (ii) we compare the costs at t(oe s ) while at (iii) we compare them at pbt(oe s ). Between (ii)
and (iii) costs increase linearly, and for t ! pbt(oe s ) we know that there is a monotonous cost increase
for oe s , while costs of oe s no longer increase. Thus, if (ii) and (iii) are fulfilled, cost contributions of oe s are
less than those of oe s , i.e. there is no completion ! s such that ZBSP (! s ; oe s completing
the proof. 2
For the example in Figure 2, Figures 7 and 8 illustrate Theorem 5 with 3-partial schedules oe 3 and oe 3 . In

Figure

7, we have G 1 (oe 3
cost
oe s
oe s

Figure

Illustration of Theorem 5
oe 3t

Figure

7: Theorem 5: oe 3 dominates oe 3
Checking (ii), we have 22 - while for (iii) we have 22
so that oe 3 is dominated. Figure 8 illustrates the effect of block costs, but with modified data as follows:
10=3. Checking Theorem 5, we have (ii)
not fulfilled. Thus, oe 3 does not
dominate oe 3 , though c(oe 3 Figure 8 shows that c(oe 4
leftshifted.
In the second dominance rule for the case i s must consider sc 0;i instead of sc g;i to take block
costs into account.
Theorem 6 Given two s-partial schedules oe s and oe s with AS
st
denote the family of the (last) job in a completion ! s of oe s . Then st st st
analogously for setup costs due to the triangle inequality. Thus any completion ! s of oe s is also a feasible
completion of oe s because of (i); if (! s ; oe s ) is feasible, (! s ; oe s ) is feasible, too. Due to (ii), for any ! s , the
schedule (! s ; oe s ) has lower costs than (! s ; oe s ).

Figure

8: Theorem 5: oe 3 does not dominate oe 3
The difference is that now also block costs are taken into account in (ii): when leftshifting G 1 (oe s ) in an
extension of oe s , we have c(oe s as an upper bound for the cost contribution. A trivial lower bound
for the cost contribution of oe s is c(oe s ). Thus oe s dominates oe s as any ! s completes oe s at lower costs,
completing the proof. 2
Finally, an alternative way to solve the BSP is a dynamic programming approach. We define the job-sets
as states and apply the dominance rules in the same way. An implementation of this approach was less
efficient and is described in Jordan [8].
7 Comparison with Procedures to solve Variants of the DLSP
From the analysis in Section 4 we know that we address the same planning problem in BSP and DLSP,
and that we find corresponding solutions. Consequently, in this section we compare the performance of
algorithms solving the BSP with procedures for solving variants of the DLSP. The comparison is made
on the DLSP instances used to test the DLSP procedures; we take the instances provided by the cited
authors and solve them as BSP(DLSP) or BSPUT(DLSP) instances (cf. Figure 1). An exception is made
for reference [7] where we use randomly generated instances.
The different DLSP variants are summarized in Table 11. For the DLSP, in the first column the reference,
in the second the DLSP variant is displayed. The fourth column denotes the proposed algorithm, the third
column shows whether computational results for the proposed algorithm are reported for equal or unequal
holding costs. Depending on the holding costs, the different DLSP variants are solved as BSP(DLSP)
or BSPUT(DLSP) instances. With the exception of reference [15], the DLSP procedures are tested with
equal holding costs, so that regenerative schedules are optimal in [4] and [7].
7.1 Sequence Independent Setup Times and Setup Costs (SISTSC)
In Cattrysse et al. [4], a mathematical programming based procedure to solve SISTSC is proposed.
Cattrysse et al. [4] refer to their procedure as dual ascent and column generation procedure (DACGP).
The DLSP is first formulated as a set partitioning problem (SPP) where the columns represent the
production schedule for one item i; the costs of each column can be calculated separately because setups
are sequence independent. DACGP then computes a lower bound for the SPP by column generation, new

Table

Solving Different DLSP Variants as a BSP
Author Variant Holding Costs Algorithm Instances Properties of
Schedules
Cattrysse
et al. [4]
regenerative
Fleisch-
mann
regenerative
Salomon
et al. [15]
one block
columns can be generated solving a single item subproblem by a (polynomial) DP recursion. In DACGP
a feasible schedule, i.e. an upper bound, may be found in the column generation step, or is calculated
by an enumerative algorithm with the columns generated so far. If in neither case a feasible schedule is
found, an attempt is made with a simplex based procedure.
The (heuristic) DACGP generates an upper and a lower bound, SABSP solves BSP(DLSP) to optimality.
DACGP is coded in FORTRAN, SABSP is coded in C. DACGP was run on an IBM-PS2 Model 80
PC (80386 processor) with a 80387 mathematical coprocessor, we implemented SABSP on the same
machine to make computation times comparable.
Computational results for the DACGP are reported only for identical holding costs
items. Consequently, we solve DLSP as BSP(DLSP) and only need to consider regenerative schedules,
Theorem 4. Furthermore, the timetabling procedure requires fewer computations in equation (18) as
setups are sequence independent.
The DLSP instances with nonzero setup times are provided by the authors of [4]. They generated instances
for item-period combinations f(N; T 60)g. We refer only to
instances with smaller instances are solved much faster by SABSP than by DACGP.
The DLSP instances have setup times st g;i of either 0, 1 or 2 periods. The average setup-time per
item (over all instances) is (approximately) 0.5, making setup times not very significant. For each item-
period combination instances with different (approximate) capacity utilizations ae were generated: low (L)
capacitated (ae ! 0:55), medium (M) (0:55 - ae ! 0:75) and high (H) capacitated instances (ae - 0:75).
Approximate capacity utilization is defined as ae = 1=T
were generated for each
combination, amounting to 3 instances in total.
In

Table

12, we use #J to denote the average number of jobs in BSP(DLSP) for the instance size (N; T )
of the DLSP. For DACGP we use 4 avg to denote the average gap (in percent) between upper and lower
bound. # inf is the number of instances found infeasible by the different procedures and R avg denotes the
average time (in seconds) needed for the instances in each class. For DACGP, all values in Table 12
are taken from [4].

Table

12: Comparison of DLSP and BSP Algorithms for SISTSC
DACGP SABSP
(4;
(386 PC with coprocessor)
In the comparison between DACGP and SABSP, the B&B algorithm solves problems with
much faster; the number of sequences to examine is relatively small. For computation times
of SABSP are in the same order of magnitude than for DACGP. In (6; 60;M) the simplex based procedure
in DACGP finds a feasible integer solution for one of the 10 instances claimed infeasible by DACGP.
Thus, in (6; 60;M), 9 instances remain unsolved by DACGP, whereas SABSP finds only 7 infeasible
instances. DACGP also fails to find existing feasible schedules for (N; T; ae) =(2,60,H), (4,60,M). Recall
that SABSP takes advantage of a small solution space, keeping the enumeration tree small and thus
detecting infeasibility or a feasible schedule quite quickly. DACGP tries to improve the lower and upper
bound, which is difficult without an initial feasible schedule. Therefore the (heuristic solution procedure)
DACGP may fail to detect feasible schedules if the solution space is small.
For the same problem size (N; T ) in DLSP, the number of jobs J in BSP(DLSP) may be very different.
Therefore, solution times differ considerably for SABSP. Table 13 presents the frequency distribution of
solution times. In every problem class the majority of instances is solved in less than the average time for
DACGP.
7.2 Sequence Dependent Setup Costs (SDSC)
An algorithm for solving SDSC is proposed by Fleischmann [7]. Fleischmann transforms the DLSP into
a traveling salesman problem with time windows (TSPTW), where a tour corresponds to a production
schedule in SDSC. Fleischmann calculates a lower bound by lagrangean relaxation; the condition that
each node is to be visited exactly once, is relaxed. An upper bound is calculated by a heuristic, that first
constructs a tour for the TSPTW and then tries to improve the schedule using an Or-opt operation. In
Or-opt, pieces of the initial tour are exchanged to obtain an improved schedule. Or-opt is repeated until
no more improvements are found. We refer to Fleischmann's algorithm as TSPOROPT. TSPOROPT

Table

13: Frequency Distribution of Solution Times of SABSP
Number of instances solved faster than
(4;
28
(386 PC with coprocessor)
was coded in Fortran, experiments were performed on a 486DX2/66 PC with the original code provided
by Fleischmann.
Fleischmann divides the time axis into micro and macro periods. Holding costs arise only between macro
periods, and demand occurs only at the end of macro periods. Thus a direct comparison of TSPOROPT
and SABSP using Fleischmann's instances is not viable; instead, we use randomly generated BSP instances
which are then transformed into DLSP instances. We generated instances for
low (L) (ae - 0:75) or high (H)(ae - 0:97) capacity utilization. Note that for zero setup times, ae does
not depend on the schedule; the feasibility problem is polynomially solvable. In BSP, we have an average
number of jobs with a processing time out of the interval [1; 4]. In DLSP, we have an average
for high (H) and low (L) capacitated instances. Holding costs are identical, and
we solve BSP(DLSP). From [7] we select the 2 setup cost matrices S4 and S6 which satisfy the triangle
inequality: in S4 costs equal 100 for g ! i and 500 for g ? i. For S6 we have only two kinds of setups:
items f1; 2; 3g and f4; 5g form two setup-groups, with minor setup costs of 100 within the setup-groups
and major setup costs of 500 from one setup-group to the other.
In

Table

14 results are aggregated over the instances in each class. We use 4 avg to denote the average
gap between lower and upper bound in % for TSPOROPT and R avg ( ~
R avg ) to denote the average time
for TSPOROPT (SABSP) in seconds. We denote by 4Z best the average deviation in % of the objective
function value of the heuristic TSPOROPT from the optimal one found by SABSP. Table 14 shows
that 4 avg can be quite large for TSPOROPT. Solution times of SABSP are short for high capacitated
instances and long for low ones. For S4, TSPOROPT generates a very good lower bound, we have
best and the deviation from the optimal objective is due to the poor heuristic upper bound.
On the other hand, for S6 both the lower and the upper bound are not very close to the optimum. It is
well to note that SABSP does not solve large instances of SDSC with 8 or 10 items whereas Fleischmann
reports computational experience for instances of this size as well. The feasibility bound is much weaker
for zero setup times, or, equivalently, the solution space is much larger, making SABSP less effective. For

Table

14: Comparison of DLSP and BSP Algorithms for SDSC
setup cost TSPOROPT SABSP
best R avg ~
R avg
the instances in Table 14, however, SABSP yields a better performance.
7.3 Sequence Dependent Setup Times and Setup Costs (SDSTSC)
In Salomon et al. [15], Fleischmann's transformation of the DLSP into a TSP with time windows (TSPTW)
is extended for nonzero setup times in order to solve SDSTSC. Nodes in the TSP network represent positive
demands, and all nodes must be visited within a certain time window. The transformed DLSP is solved
by a dynamic programming approach designed for TSPTW problems (cf. Dumas et al. [5]), we refer to
the procedure in [15] as TSPTWA. Paths in the TSP network correspond to partial schedules. Similar to
the dominance rule for SABSP, in TSPTWA paths may dominate other paths via a cost dominance, or
they may be eliminated because they cannot be extended, which corresponds to the feasibility bound.
TSPTWA is coded in C and run on a HP9000/730 workstation (76 mips, 22 M flops). SABSP runs on a
486DX2/66 PC.
In order to test TSPTWA Salomon et al. [15] use randomly generated instances, in which, similar to [4],
setup times st g;i 2 f0; 2g. Unfortunately, the setup times do not satisfy the triangle inequality. A
"triangularization" (e.g. with the Floyd/Warshall algorithm) often results in setup times equal to zero.
So we adjusted the setup times "upwards" (which is possible in this case because st g;i 2 f0; 1; 2g) and
as a result, setup times are rarely zero. We added 4 (8) units to the planning horizon for
in order to obtain the same (medium) capacity utilization as in [15]. In this way, instances
are supposed to have the same degree of difficulty for TSPTWA and SABSP: the smaller solution space
due to correcting st g;i upwards is compensated by a longer planning horizon.
In [15] instances are generated for and we take the (largest) instances for the item-period
combination f(N; T 60)g. The instances have a medium (M) capacity
utilization 0:5 - ae - 0:75 because setup times are nonzero. For each (N; T ) combination,
with and without holding costs are generated. Holding costs differ among the items. Consequently, we
solve BSPUT(DLSP) if Furthermore, we need not apply the timetabling
procedure in the latter case because the optimal schedule is one block. In Table 15, #F (# ~
the number of problems solved by TSPTWA (SABSP) within a time limit of 1200 sec (1200 sec) and
a memory limit of 20 MB (10 MB). #J denotes the average number of jobs for the BSP. ~
R avg ( ~

Table

15: Comparison of DLSP and BSP Algorithms for SDSTSC
F ~
R avg ~
denotes the average time SABSP requires to solve the instances (considering only regenerative schedules).
The average time is calculated over all instances which are solved within the time limit, ~
R avg is put in
brackets if not all instances are solved. The last column shows the results if we consider only regenerative
schedules during enumeration for
provides the maximal deviation in % from the optimal
schedule (which may be non-regenerative).

Table

15 demonstrates that SABSP succeeds in solving some of the problems which remained unsolved
by TSPTWA. Solution times of SABSP are relatively short compared with TSPTWA for
5. Solution times increase for and instances can only be solved if the number of jobs is
relatively small. Instances become difficult for nonzero, especially for unequal holding costs. If we only
enumerate over regenerative schedules, solution times for SABSP decrease. Moreover, only one instance
is not solved to optimality for (N; T Thus, even for unequal holding costs optimal schedules
are regenerative in most cases. Furthermore, for (N; T instances would have
been solved within the time limit of 1200 sec if only regenerative schedules would have been considered.
8 Summary and Conclusions
In this paper, we examined both the discrete lotsizing and scheduling problem (DLSP) and the batch
sequencing problem (BSP).
We presented model formulations for the DLSP and for the BSP. In the DLSP, decisions regarding what
is to be done are made in each individual period, while in the BSP, we decide how to schedule jobs. The
DLSP can be solved as a BSP if the DLSP instances are transformed. For each schedule of one model there
is a corresponding solution for the other model. We proved the equivalence of both models, meaning that
for an optimal schedule of the BSP the corresponding solution of the DLSP is also an optimal schedule,
and vice versa.
In order to solve the BSP effectively, we tried to restrict the search to only a subset of all possible schedules.
We found out that jobs of one family can be preordered according to their deadlines. Furthermore, for
equal holding costs, it is optimal to start production for a family only if there is no inventory of this
family.
When solving the BSP with a branch & bound algorithm to optimality, we face the difficulty that already
the feasibility problem is difficult. We must maintain feasibility and minimize costs at the same time.
Compared with other scheduling models, the objective function is rather difficult for the BSP. A tight lower
bound could thus not be developed. We therefore used dominance rules to prune the search tree. Again,
the difficult objective function complicates the dominance rules and forces us to distinguish different cases.
In order to evaluate our approach, we tested it against (specialized) procedures for solving variants of the
DLSP. Despite the fact that we have no effective lower bound, our approach proved to be more efficient if
(i) the number of items is small, and (ii) instances are hard to solve, i.e. capacity utilization is high and
setup times are significant. It is then "more appropriate" to schedule jobs than to decide what to do in
each individual period.
In the DLSP, the time horizon is divided into small periods and all parameters are based on the period
length. In the BSP, all parameters can also be real numbers: setup times, in particular, are not restricted
to being multiples of a period length. The different models also result in different problem sizes for DLSP
and BSP: the problem size for DLSP is essentially the number of items N and periods T while the problem
size for the BSP depends on the number of families and jobs.
We conjecture that our approach is advantageous for instances with few items and a small solution space
(i.e. long setup times and high capacity utilization), where the job sequence is the main characteristic
of a solution. In such cases we managed to solve instances with 10 (5) families and jobs on a
PC. DLSP solution procedures are thought to be better suited for lower capacitated instances with many
items, setup times that are not very significant, and parameters which differ among the periods. It is then
appropriate to decide anew for each individual period.
In the future we will extend the BSP to multilevel structures and multiple machines.

Acknowledgments

We are indebted to Dirk Cattrysse and Marc Solomon who made available their instances, and to
Bernhard Fleischmann who made available his code. Furthermore, we would like to thank three anonymous
referees for their valuable comments on earlier versions of this paper.



--R

Single facility multi-class job scheduling
Complexity of task sequencing with deadlines
"Some extensions of the discrete lotsizing and scheduling problem"
A dual ascent and column generation heuristic for the discrete lotsizing and scheduling problem with setup-times
Technical Note: An optimal algorithm for the traveling salesman problem with time windows.
The discrete lot-sizing and scheduling problem
The discrete lot-sizing and scheduling problem with sequence-dependent setup-costs
Batching and Scheduling - Models and Methods for Several Problem Classes
Computers and intractability - a guide to the theory of NP-completeness

Minimizing flow time on a single machine with job classes and setup times.
On the complexity of scheduling with batch setup-times
Integrating scheduling with batching and lot- sizing: a review of algorithms and complexity
Some extensions of the discrete lotsizing and scheduling problem.
Discrete lotsizing and scheduling with sequence dependent setup times and costs.
Batching in single operation manufacturing systems.
Batch sequencing.
Batching and sequencing of components at a single facility.
Dynamic version of the economic lot size model.
Scheduling groups of jobs on a single machine.
--TR

--CTR
C. K. Y. Lin , C. L. Wong , Y. C. Yeung, Heuristic Approaches for a Scheduling Problem in the Plastic Molding Department of an Audio Company, Journal of Heuristics, v.8 n.5, p.515-540, September 2002
Satyaki Ghosh Dastidar , Rakesh Nagi, Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs, Computers and Operations Research, v.32 n.11, p.2987-3005, November 2005
batch sequencing;Sequence-Dependent Setup Times and Setup Costs;Bounding/Dominance Rule;Discrete Lotsizing and Scheduling;Branch-and-Bound Algorithm