J Sched (2011) 14:541–555 DOI 10.1007/s10951-011-0229-x
Integrated batch sizing and scheduling on a single machine Philippe Chrétienne · Öncü Hazır · Safia Kedad-Sidhoum
Published online: 24 March 2011 © Springer Science+Business Media, LLC 2011
Abstract In this paper, we address the integrated batch sizing and scheduling problem. We consider a single machine which can handle at most one customer order at a time and for which the nominal production rate is the same for all the customer orders. Demand is deterministic, and all the orders are ready to be processed at time zero and must be delivered at a given due date. Each order can be satisfied from different batches. Upper and lower bounds on the size of the batches are considered. We seek a feasible schedule that minimizes the sum of the tardiness costs and the setup costs incurred by creating a new batch. We present some structural properties of the optimal schedules for both single-order and multipleorder problems and then propose dynamic programming algorithms based on these properties. Computational results that show the efficiency of the method are reported. Keywords Batch sizing · Scheduling · Setup cost · Tardiness · Single machine · Dynamic programming Notation K N b B Bi dk
Number of customer orders Total number of batches Lower bound on batch size Upper bound on batch size ith batch of schedule Ψ Due date for customer order k
P. Chrétienne · Ö. Hazır · S. Kedad-Sidhoum () LIP6, Université Pierre et Marie Curie, 4 place Jussieu, 75252 Paris Cedex 05, France e-mail:
[email protected] P. Chrétienne e-mail:
[email protected] Ö. Hazır e-mail:
[email protected]
rk Rk βk π Si Ci qik qi fI (Ψ ) T (n, r) f (n, r)
Total number units required by customer k Cumulative requirement of the first k orders Unit tardiness penalty for customer order k Cost of creating a new batch (setup cost) Starting time of batch Bi Completion time of batch Bi Quantity processed for order k in batch Bi Length of batch Bi Total cost of schedule Ψ for instance I Tardiness cost of processing r units of a single order in n batches after its due date Total cost of processing r units of a single order in n batches after its due date
1 Introduction Batch scheduling models with setup times and costs have been investigated by various researchers (Allahverdi et al. 2008). In these models, either job processing times are usually assumed to be fixed, or in some cases they are assumed to be controllable. When splitting is allowed, batch sizes are decision variables, and early completion of the batches is possible. There exist various scheduling studies assuming batch availability (Potts and Kovalyov 2000), that is, when a product cannot be released before its batch is completely processed. Two classes of batching problems are modeled (Potts and Kovalyov 2000): parallel batching and serial batching. In parallel batching, the jobs of a batch may be processed in parallel, hence the completion time of a batch corresponds to the maximum processing time of the jobs in the batch. Conversely, in serial batching, the jobs of a batch are executed serially, hence the processing time of a batch is the sum of the processing times of the jobs in the batch. In this paper, we assume batch availability and
542
serial batching. We also consider lower and upper bounds on the batch processing time. Cheng and Kovalyov (2001) examined various single-machine scheduling problems under batch availability and limited batch sizes. They assumed fixed job processing times and an upper bound on the number of jobs in a batch. Sung and Joo (1997) also investigated batch size restrictions for a batching problem on a single machine to minimize the weighted mean flow time. For single machine batch sizing and scheduling problems where lot splitting is possible, we refer the readers to the works of Santos and Magazine (1985) and Coffman et al. (1990). Both studies minimize total flow time without considering batch size constraints. For some complexity results for scheduling jobs on a single machine under batch availability, we refer the readers to the works of Albers and Brucker (1993) and Baptiste (2000). A relevant research is family scheduling, in which jobs are partitioned into families according to their similarities. There exists no setup for a job if it belongs to the same family as the previously processed job. Webster and Baker (1995) addressed family scheduling models to minimize total weighted flow time and maximum lateness considering both item and batch availability, while Azizoglu and Webster (1997) investigated the common due date problem by minimizing the total weighted earliness, and tardiness cost. The problem addressed in this paper occurs when scheduling, batching, and delivery decisions are considered in a two-level supply chain. The main objective is to minimize the overall scheduling and delivery cost which is achieved by forming batches of orders each of which is delivered in a single shipment. More precisely, a set of products is to be scheduled on a single machine by a supplier to be delivered to a manufacturer. The jobs are delivered in batches. If we assume that each batch is delivered by a vehicle, a fixed setup cost is then assumed. Moreover, if we assume that there is always a vehicle ready to deliver the product, then it is useless to consider setup times in the model. Hall and Potts (2003, 2005) addressed an integrated scheduling and batching problem where jobs are delivered to the customer in a single shipment. They considered various delivery time based objective functions. Recently, Selvarajah and Steiner (2006) have addressed a batch scheduling problem that aims at finding the number and sizes of the batches in an optimal schedule that minimizes the total inventory holding and delivery cost. Robert (2007) has studied an integrated lot-streaming and pegging problem that minimizes the sum of the batch creation costs and the weighted tardiness penalties and has proposed a dynamic programming algorithm. In this paper, we first address the single-order integrated batch sizing and scheduling problem and derive new structural properties of an optimal solution. These properties are then used to address the multiple-order problem with both common and distinct due dates. These dominance properties allow us to develop an efficient dynamic programming
J Sched (2011) 14:541–555
algorithm solving the multiple-order problem with common due date. Some polynomial cases are also discussed. The main contribution of the paper regarding previous works is to propose a new efficient dynamic programming algorithm solving the multiple-order problem with common due date that outperforms the one proposed by Robert (2007). It is based on new structural properties as well as extended ones from the work of Selvarajah and Steiner (2006) to handle the batch size restrictions. The structure of the paper is as follows. Section 2 describes the problem and introduces some definitions. The single-order problem is addressed in Sect. 3 (resp. Sect. 4) when setup costs are (resp. are not) considered. The multiple-order problem with common due date and distinct due dates, respectively, is investigated in Sects. 5 and 6. Computational experiments that show the efficiency of the developed dynamic programming algorithm are reported in Sect. 7. Finally, we discuss some possible extensions and future research issues in Sect. 8.
2 Problem definition We consider a single machine which can handle at most one customer order at a time and for which the nominal production rate is the same for all orders. Demand is deterministic and all orders are ready to be processed at time zero. K customer orders must be performed. Customer order k requires rk units to be delivered at due date dk . If order k is delivered after dk , a penalty βk , is paid for each unit of order k produced in a batch completing after dk . Creating a new batch incurs a setup cost π , independent of the size of the batch. There are two possible ways to meet the demand of the customers. When mono-pegging is assumed, it is required that each customer order be met from a single batch; conversely, multi-pegging allows orders to be satisfied from different batches. In this paper, we consider the multi-pegging case and we assume batch availability. If Si (resp. Ci ) denotes the starting time (resp. the completion) time of the ith batch (denoted by Bi ), then we must have b ≤ Ci − Si ≤ B where b (resp. B) is the minimum (resp. maximum) processing time of a batch. The tardiness cost of producing qik units of order k in batch Bi is βk qik Tik where Tik is the tardiness of batch Bi with respect to due date dk . Finally, it is assumed that all the data, rk , dk , b, B are integers. An instance I of the Integrated Batch Sizing and Scheduling problem with K orders (the K-IBS problem) can be deˆ rˆ , β, ˆ π, b, B) where dˆ = (d1 , . . . , dK ), fined by a 6-tuple (d, rˆ = (r1 , . . . , rK ) and βˆ = (β1 , . . . , βK ). A schedule Ψ of I is a triple (N, q, S) where N is the total number of batches, q = (qik ) are the batch production values and S = (S1 , . . . , SN ) are the starting times of the batches in Ψ . The cost of schedule Ψ is denoted fI (Ψ ). Since we will only
J Sched (2011) 14:541–555
be concerned with schedules with no idle time, Ψ may also be defined by a triple (N, o, S), where o(u) is the customer order produced at time unit u for u = 0, . . . , K k=1 rk − 1. We assume that N is an integer. A schedule is feasible if the batch size constraints are satisfied and all the customer orders are met. The objective is to find a feasible schedule that achieves the best compromise between two contradictory criteria, the customer service delivery time and the minimization of the setup costs. Indeed, early deliveries improve the customer service and hence decrease the tardiness cost while increasing the setup costs because they induce small batches. Here, partial deliveries of orders are possible; products might be delivered partially when the batch completes processing to prevent the customer stock out and improve the customer service. Figure 1 shows two schedules Ψ1 and Ψ2 for the problem that consists in processing Q units of a single order (K = 1) with due date d. Ψ1 has one more batch than Ψ2 , but all the production units are tardy in Ψ2 while q1 production units are delivered before d in Ψ1 . The length of batch Bi is denoted by qi and we have qi = K k k=1 qi . In the sequel, as the production rate is the same for all the orders, without loss of generality, we may assume that the nominal unit production time is equal to one so that the production quantity qik also refers to the time required to process customer order k in batch Bi . We mention that, in a typical production system, production rates are product dependent. However, in a group technology environment, similar products, based on geometry or manufacturing specificities, are grouped together, and it is rational to assume uniform processing rate for the products in the group.
Fig. 1 Tardiness vs. setup costs
Fig. 2 An illustrative example
543
ˆ rˆ , β, ˆ π, b, B), the descriptive For an instance I = (d, statement of the problem is as follows: min
N K
βk qik (Si + qi − dk )+ + πN
(1)
i=1 k=1
b≤
K
qik ≤ B
∀i ∈ I
(2)
k=1 N
qik = rk
∀k ∈ K
(3)
i=1
Si + qi ≤ Si+1 K
qik = qi
∀i ∈ I\{N }
∀i ∈ I
(4) (5)
k=1
Si , qik ≥ 0 ∀i ∈ I, k ∈ K
(6)
where (Si + qi − dk )+ = max{0, Si + qi − dk }, I = {1, . . . , N }, and K = {1, . . . , K}. The quadratic objective function (1) which defines fI (Ψ ) addresses the trade-off between the tardiness and setup costs. Constraints (2), (3), and (4) impose respectively that the batch size constraints must be met, the demand must be fully satisfied, and no overlapping of the batch processing time intervals must occur. Constraint (5) imposes that the size of a batch is equal to the sum of the demand fractions processed in the batch. We notice that minimizing fI (Ψ ) is a new criterion recently introduced by Robert (2007). Indeed, each tardy unit of an order is penalized, whereas in the classical weighted tardiness problem, each tardy job is penalized. In order to illustrate the problem, the following example shows a feasible schedule of an instance of K-IBS. Example 1 We consider an instance I of K-IBS where K = 4, b = 3, B = 5, rˆ = (10, 15, 1, 9), dˆ = (10, 18, 20, 24), π = 10, and βˆ = (1, 1, 1, 1). A feasible schedule Ψ is illustrated in Fig. 2. Each rounded rectangle (resp. color) represents a batch (resp. a customer order). The orders processed are illustrated with numbers inside the rectangles, and the completion time of each batch is given below the time axis. We have fI (Ψ ) = 209, which consists of 80 cost units to create 8 batches and of 129 cost units for tardiness penalties. The decomposition of the total tardiness cost with respect to
544
the customer orders is as follows: 0 for order 1, 44 for order 2, 6 for order 3, and 79 for order 4. Let us now give some preliminary definitions. Definition 1 A batch Bi is tardy if Ci > dk for all orders k such that qik > 0. Similarly, Bi is early (resp. on time) if Ci < dk (resp. Ci = dk ) for all orders k such that qik > 0. Definition 2 A batch is uniform if it processes only units from a single order. Otherwise, it is mixed. Definition 3 Bi is a straddling batch if there exists an order k such that qik > 0 and Si < dk < Ci . Definition 4 Bi and Bj are linked batches if they process at least one customer order in common. For the batches depicted in Fig. 2, B1 , B3 and B4 are early and uniform, whereas B2 is on-time and uniform. B5 , B7 and B8 are tardy and uniform, whereas B6 is tardy and mixed. B5 is straddling. B5 and B6 are linked batches. In the rest of the paper, it will be convenient to denote by Rk the cumulative requirement ki=1 ri of the first k orders. Moreover, it is easy to see that, given any schedule with a start time t > 0, a new schedule can be constructed by moving the start times of all the batches earlier by t. Because no earliness penalties are considered, the objective value of the new schedule will not be worse than that of the original schedule. The study of IBS problems may be limited to the instances where the starting time of the schedule is set to t = 0.
3 Single-order batch sizing and scheduling with setup costs In this section, we investigate the single-order case (K = 1). We first consider the special case of 1-IBS when d = 0 and when the batch size constraints are relaxed, i.e., b = 1 and B = r. To simplify the notation, this special case will be denoted by 1-IBS(U, d = 0) (for 1-IBS with Unconstrained Batch Sizes and d = 0) and an instance of 1-IBS(U, d = 0) will be a 3-tuple (r, β, π). 3.1 Unconstrained batch sizes Selvarajah and Steiner (2006) study the n-batching problem where the total holding and setup cost is minimized. No due dates, tardiness penalties, and batch size constraints are taken into account. A holding cost, equal to the product of the batch completion time by the unit holding cost, is charged for each unit until delivery. The n-batching problem
J Sched (2011) 14:541–555
is then clearly a special case of 1-IBS(U, d = 0) when N = n and n is a parameter of the problem. This special case will be denoted by 1-IBS(U, d = 0, n). Let us first recall the main dominance properties for 1-IBS(U, d = 0, n) (Selvarajah and Steiner 2006). Property 1 (Order independence) Given the sizes of the n batches, their order does not affect the objective function value. The policy of evenly assigning units to the batches is called Almost Equal Batch Size Policy (AEBSP). More precisely, a schedule satisfies the AEBS property (in short, is an AEBS-schedule) if the sizes of any two batches differ by at most one. The next property shows that the AEBS-schedules are dominant. Property 2 (AEBS) A schedule of an instance of 1IBS(U, d = 0, n) is optimal if and only if it is an AEBSschedule. The structure of an optimal schedule of an instance of 1IBS(U, d = 0, n) is then derived from Property 2. Let I = (r, β, π) be an instance of 1-IBS(U, d = 0, n). Lemma 1 The schedule such that the first nr n − r batches have size nr − 1 and the remaining batches have size nr is an optimal schedule of I . Figure 3, where n1 = nr n − r, n2 = n − n1 , m1 = nr − 1 and m2 = m1 + 1, illustrates the structure of an optimal solution. Example 2 Consider the instance (17, β, π) of 1-IBS(U, d = 0, 4). An optimal schedule of such an instance satisfies n1 = 3, n2 = 1, m1 = 4, and m2 = 5. B1 , B2 and B3 have size 4, whereas B4 has size 5. It comes from Lemma 1 that the minimum cost of instance (r, β, π) of 1-IBS(U, d = 0, n) is f (n, r) = πn + β r r 2 r 2 2 (2r n − n n + n n + r − r). So, if we denote the tardiness cost by T (n, r), we have f (n, r) = πn + T (n, r). The following properties finally allow us to derive a binary search algorithm solving 1IBS(U, d = 0) in O(log(r)) time to compute n. Property 3 (Monotonicity) T (n, r) is a decreasing function of n. Property 4 (Convexity) f (n, r) is a discrete convex function of n. Let us prove an additional technical property of T (n, r) that will be useful later in the paper.
J Sched (2011) 14:541–555
545
Fig. 3 Structure of an optimal schedule
Lemma 2 T (n, r) is an increasing function of r. r r Proof If r+1 n = n , then T (n, r + 1) − T (n, r) = β( n r r r + r). Otherwise, r+1 n = n + 1, so we have n = n r and T (n, r + 1) − T (n, r) = β( n + r + 1). In both cases, T (n, r) < T (n, r + 1).
3.2 Constrained batch sizes In this section, we first give some feasibility properties, then we solve the special case when d = 0, and finally we provide a solution algorithm for 1-IBS. 3.2.1 Feasibility When batch size constraints (b, B) are imposed, we can easily observe that the minimum (resp. maximum) number of batches to process r units is nmin = Br (resp. nmax = br ). Let r, b and B be three integers such that 1 ≤ b ≤ B ≤ r. Integer r is said to be splittable into the integers of {b, . . . , B} q (in short r is (b, B)-splittable) if r = i=1 ni ki where for any i = 1, . . . , q, we have b ≤ ki ≤ B and where ni is a positive integer. The following property proved in Robert (2007) provides a necessary and sufficient condition for an integer r to be (b, B)-splittable. Property 5 (Splittability) A positive integer r is (b, B)splittable if and only if Br ≤ br . The following property defines a unique decomposition of a (b, B)-splittable integer r. Property 6 If r is (b, B)-splittable, there is a unique decomposition r = kn1 + (k + 1)n2 such that b ≤ k ≤ B and n1 + n2 = br . The decomposition of a (b, B)-splittable integer r corresponds to splitting r into a maximal number of batches. It is easy to see that the decomposition leads to n1 = (k + 1) br − r and n2 = r − k br . If all the br batches have size k, there will be n2 = r − k br units unscheduled. In addition, n1 = (k + 1) br − r more units are required to have all the batches of size k + 1. Therefore, the decomposition could be performed by generating br batches of size k = rr and evenly allocating the remaining n2 = r − k br b units to n2 batches. This decomposition is unique; we can easily show that any other decomposition will not satisfy n1 + n2 = br .
Example 3 We consider the following integers: r = 26, b = 7 and B = 10. Since Br ≤ br , r is (b, B)-splittable. The decomposition of r is given by n1 = 1, n2 = 2 and k = 8, which is obtained by the following procedure. We first split r into br = 3 batches of size rr = 8, then the b two remaining unscheduled units are evenly assigned to the batches. We thus have one batch of size 8 and two batches of size 9. Let us now provide additional technical properties concerning (b, B)-splittability. Lemma 3 If r is (b, B)-splittable and there exists a nonnegative integer k such that kb < r < (k + 1)b, then r − 1 is also (b, B)-splittable. Proof The splittability of r requires Br ≤ br . Moreover, as there exists a non-negative integer k such that kb < r < r r−1 r (k + 1)b, r−1 b = b = k. Since, B ≤ B , we have r−1 r−1 B ≤ b , r − 1 is then (b, B)-splittable. Using the same line of reasoning, we get the following lemma. Lemma 4 If r is (b, B)-splittable and there exists a nonnegative integer k such that kB < r < (k + 1)B, then r + 1 is also (b, B)-splittable. 3.2.2 Solving 1-IBS when d = 0 In this section, we show that, as long as r is (b, B)splittable, the dominance properties of 1-IBS(U, d = 0, n) easily extend to the special case of 1-IBS when d = 0 denoted by 1-IBS(d = 0), and that a simple variant of the binary search algorithm for 1-IBS(U, d = 0) polynomially solves 1-IBS(d = 0). In the sequel, we will call this variant BinS(I ) when it is applied to an instance I of the problem. Let (n, q, S) be an optimal schedule of instance (r, β, π) of 1-IBS(U, d = 0, n). Lemma 5 If Br ≤ n ≤ br , an optimal schedule of instance (r, β, π) of 1-IBS(U, d = 0, n) is an optimal schedule of instance (r, β, π, b, B) of 1-IBS(d = 0). Proof From Lemma 1, we know that the first nr n − r batches have size nr − 1 and that the remaining batches have size nr . We also have Br ≤ n ≤ br . If nr is not an
546
integer, then b ≤
J Sched (2011) 14:541–555 r br
≤
r n
< nr . Similarly, nr ≤ rr ≤
r = B. Therefore, b ≤ r
B
nr
B
− 1 < nr ≤ B. If nr is an have size nr . Using the same ar-
integer, then all the batches guments, we get b ≤ nr ≤ B.
• Σ2 , the subset of the schedules of I with a straddling batch Bi such that Si mod B = 0.
The following theorem restricts the set of the possible values of Si in an optimal schedule of I .
It comes from Lemma 5 that BinS polynomially solves 1-IBS(d = 0) by simply applying the binary search algorithm solving 1-IBS(U, d = 0) within the interval Br .. br .
Theorem 1 If d > 0 and b < d, then Σ0 ∪ Σ1 ∪ Σ2 is a dominant subset of the schedules of the instance I = (d, r, β, π, b, B) of 1-IBS.
3.2.3 Solving 1-IBS when d > 0 Let I = (d, r, β, π, b, B) be an instance of 1-IBS such that d > 0. If d ≤ b, then we easily see that I and the corresponding instance I = (r, β, π, b, B) of 1-IBS(d = 0) have the same set of feasible schedules. Moreover, given a schedule, since the tardiness of each unit is d time units greater in I than in I , the cost of that schedule is βrd larger for I than for I . So, if d ≤ b, an optimal schedule of I is also an optimal schedule of I . We now consider the case when b < d. If d ≥ r, the due date d is not restrictive. All the units will be early or on time, and an optimal schedule is simply obtained by minimizing the number of early or on-time batches. The following property is useful in this case. Property 7 If d ≥ r, then the optimal schedule of I is structured into Br batches of size at least b and at most B. The associated cost E(r) is equal to π Br . In the sequel, we denote by MinNB(r) the algorithm that splits r into Br batches of size at least b and at most B. Example 4 The optimal schedule of an instance I of 1-IBS such that d = 28, r = 25, b = 7, and B = 10 obtained using MinNB(r) is structured into three batches B1 and B2 of size 8 and B3 of size 9. If d < r, then the due date d is restrictive. The optimal schedule may contain a straddling batch, and, in this case, additional dominance properties are required to efficiently get the optimal schedule. We first separate the set of feasible schedules into a subset of schedules without a straddling batch and a subset of schedules with a straddling batch. Finding the best schedule of the former subset is easy. Concerning the latter subset, we show that only two starting times are to be considered for the straddling batch. Let I = (d, r, β, π, b, B) be an instance of 1-IBS such that d > 0 and b < d. We denote by: • Σ0 , the subset of the schedules of I with no straddling batch, • Σ1 , the subset of the schedules of I with a straddling batch Bi such that (r − Si ) mod b = 0,
Proof Let us denote by Ψ an optimal schedule of I , and let us assume that Ψ ∈ / Σ0 ∪ Σ1 ∪ Σ2 . Therefore, Ψ has a straddling batch Bi of length qi such that the starting time Si satisfies Si mod B = 0 and (r − Si ) mod b = 0. Since (r − Si ) mod b = 0, there is at least one tardy batch whose size is strictly greater than b. Let us first consider the case when d − Si ≤ b. The restriction Ψ of Ψ to its tardy batches is an optimal schedule of the instance I = (d, r − Si , β, π, b, B) of 1-IBS. From Property 1, we may assume that the longest batch of Ψ is scheduled first so that we have qi > b. Furthermore, since Ψ ∈ / Σ2 , Ψ has at least an early batch Bj whose size is strictly lower than B. By transferring the first unit of Bi to Bj , we get a feasible schedule of I whose cost is smaller than the cost of Ψ , since the two schedules have the same number of batches but the transferred unit is tardy in Ψ and early or on time in the new schedule. This makes a contradiction, since Ψ is an optimal schedule of I . If d − Si > b, we may again transfer the first unit of Bi to Bj and get a better schedule than Ψ , which makes a contradiction. The following property shows that in an optimal schedule of an instance I = (d, r, β, π, b, B) of 1-IBS only two dates must be considered for the starting time of the straddling batch.
Let Qb (I ) = max{0, r − r−d b b}, Qb (I ) = r − Qb (I ), QB (I ) = Bd B, and Q B (I ) = r − QB (I ). Figure 4 illustrates the definitions of Qb (I ), QB (I ), Ψ1 ∈ Σ1 , and Ψ2 ∈ Σ2 . Corollary 1 The straddling batch of an optimal schedule of an instance I of 1-IBS starts at time Qb (I ) or QB (I ). Proof Assume that an optimal schedule of an instance I of 1-IBS has a straddling batch Bi . From Theorem 1, we have Si mod B = 0 or (r − Si ) mod b = 0. If Si mod B = 0, then we necessarily have Si = QB (I ), otherwise the straddling batch would have a size larger than B. If Si mod B = 0, the first unit of the current straddling batch may be transferred to an early batch with size less than B until the straddling batch starts at Qb (I ) or all the early batches have size B.
J Sched (2011) 14:541–555
547
Fig. 4 Illustration of the starting time of the straddling batch
Fig. 5 Illustration of the algorithm
3.2.4 A solution algorithm for 1-IBS
Schedule Ψ2 Q (I ) Bb .
Let us now present the solution algorithm solving 1-IBS. Let I = (d, r, β, π, b, B) be an instance of 1-IBS. If r ≤ d, then the optimal schedule is obtained by using MinNB(r). If d < r, then schedules Ψ0 , Ψ1 and Ψ2 (if they exist) are computed, where Ψ0 is the best schedule of I with no straddling batch, Ψ1 is the best schedule of I with a straddling batch starting at Qb (I ), and Ψ2 is the best schedule of I with a straddling batch starting at QB (I ). Finally, the optimal schedule of I is the best schedule among the existing schedules Ψ0 , Ψ1 and Ψ2 . Let us now show how these three schedules are computed. Schedule Ψ0 Schedule Ψ0 exists if and only if Bd ≤ db r−d and r−d B ≤ b . Ψ0 is obtained as follows. The partial schedule of Ψ0 over [0, d] is derived from algorithm MinNB(d), while the partial schedule of Ψ0 over [d, r] is obtained by using algorithm BinS((d, r − d, β, π, b, B)). Schedule Ψ1 Schedule Ψ1 exists if and only if QbB(I ) ≤ Qbb(I ) . Ψ1 has the following structure: the partial schedule of Ψ1 over [0, Qb (I )] is obtained using algorithm MinNB(Qb (I )), while the partial schedule of Ψ1 over [Qb (I ), r] is derived by using algorithm BinS((d, r − Qb (I ), β, π, b, B)) where d − Qb (I ) < b.
Schedule Ψ2 exists if and only if
Q B (I ) B
≤
Clearly, the partial schedule of Ψ2 over [0, QB (I )] is obtained using MinNB(QB (I )). We also know that the partial schedule of Ψ2 over [QB (I ), r] is an optimal schedule of the instance J = (d, r − QB (I ), β, π, b, B). If d − b ≤ QB (I ), then the optimal schedule of J is derived from the optimal solution of instance (0, r − QB (I ), β, π, b, B) of 1-IBS(d = 0). If QB (I ) < d − b, we need to compare the instances I0 = (QB (I ), r − QB (I ), β, π, d − QB (I ) + 1, B) and I1 = (d, r − QB (I ), β, π, d − QB (I ) + 1, B). The following property is easily observed. Property 8 A schedule Ψ is feasible for instance I0 if and only if Ψ is feasible for instance I1 . Moreover, fI0 = fI1 + (r − QB (I ))(d − QB (I )). From Property 8, we can get the partial schedule of Ψ2 over [QB (I ), r] by solving the instance I0 using BinS(I0 ). We illustrate the solution algorithm with an example. Example 5 We consider the data given in Example 2, that is d = 12, r = 26, β = 1, π = 5, b = 3, B = 5 for an instance I of 1-IBS and find out the optimal schedule of I . Schedules Ψ0 , Ψ1 and Ψ2 are illustrated in Fig. 5; the starting time of the straddling batches and the total setup and tardiness costs of these schedules are given below. We have Qb (I ) = 11, QB (I ) = 10, fI (Ψ0 ) = 123 + 7 × 5 = 158, fI (Ψ1 ) = 120 + 8 × 5 = 160, and fI (Ψ2 ) = 122 + 7 × 5 = 157. Ψ2 is the optimal schedule.
548
4 Single-order batch sizing and scheduling without setup costs We address in this section the special case of 1-IBS where the creation of a batch is not penalized, i.e., π = 0, which we will define as 1-IBS(π = 0). An instance of this special case will be defined by (d, r, β, b, B). 4.1 Structural properties The following corollary is induced by Property 3 (Monotonicity) and Lemma 5. Let us consider a schedule Ψ of the instance I = (d, r, β, b, B) of 1-IBS(π = 0). Corollary 2 If Ψ has a straddling batch such that Si ≤ Qb (I ) (resp. Si > Qb (I )), then Ψ is optimal if and only if r−d it has r−d b (resp. b ) tardy batches. If Ψ has no straddling batch, Ψ is optimal if and only if it has r−d b tardy batches. Proof According to Theorem 1 and Corollary 1, there exists an optimal schedule of instance I for 1-IBS(π = 0) either with no straddling batch or with a straddling batch Bi satisfying either Si = Qb (I ), or Si = QB (I ). Using Property 3 (Monotonicity) and Lemma 5, we know that an optimal schedule contains a maximum number of tardy batches when the (b, B)-splittability is observed. If there exists an optimal schedule with no straddling batch, the maximum number of tardy batches is r−d b . If there exists an optimal schedule with a straddling batch such that Si = Qb (I ), there exist r−d b tardy batches of size b. Otherwise, if Si = QB (I ), we consider two cases: If Qb (I ) < QB (I ), the maximum number of tardy batches is r−d b . If QB (I ) < Qb (I ), the straddling batch completes before Qb (I ) + b, otherwise splitting the straddling batch such that Si = Qb (I ) leads to a better schedule, which is contradictory. Therefore, there exist r−d b tardy batches in the optimal schedule. We can also derive from Corollary 2 and the AEBS property, the following property. Let us consider a schedule Ψ of the instance I = (d, r, β, b, B) of 1-IBS(π = 0). Corollary 3 If Ψ has a straddling batch such that Si ≤ Qb (I ) (resp. Si > Qb (I )), then Ψ is optimal if and only if the restriction of Ψ to its tardy batches is an AEBS-schedule r−d with r−d b (resp. b ) tardy batches. If Qb (I ) is (b, B)-splittable, we can show that the starting time of a straddling batch in an optimal schedule of instance I is Qb (I ).
J Sched (2011) 14:541–555
Theorem 2 Σ1 (resp. Σ0 ∪ Σ2 ) is a dominant subset of the schedules of the instance I = (d, r, β, b, B) of 1-IBS(π = 0) if Qb is (resp. is not) (b, B)-splittable. The proof is given in Appendix. 4.2 A solution algorithm for 1-IBS(π = 0) We finally give the algorithm for solving the problem of an instance I = (d, r, β, b, B) of 1-IBS(π = 0). If r ≤ d, then any feasible schedule of I that starts at time 0 without idle time is optimal. Otherwise, we consider the following cases. If Qb (I ) is (b, B)-splittable, then the optimal schedule of I is obtained by splitting Qb (I ) units with any feasible number of batches and by splitting r − Qb (I ) units with batches of length b (schedule Ψ1 ). Otherwise, we consider the following two schedules, and the one with the minimum cost is the optimal schedule of I : 1. If d is (b, B)-splittable, we consider the schedule where d units are split with any feasible number of batches and such that the partial schedule in the time window [d, r] is an AEBS-schedule (schedule Ψ0 ). 2. If QB (I ) is (b, B)-splittable, we consider the schedule with a straddling batch that starts at Si = QB (I ) and such that the partial schedule in the time window [QB (I ), r] is an AEBS-schedule (schedule Ψ2 ). We illustrate the algorithm by the following example. Example 6 We consider the data given in Example 2 with π = 0 for the instance I = (d, r, β, b, B) of 1-IBS(π = 0). Schedules Ψ0 , Ψ1 and Ψ2 are illustrated in Fig. 5, and the starting times of the straddling batches are Qb (I ) = 11 and QB (I ) = 10. The tardiness costs are fI (Ψ0 ) = 123, fI (Ψ1 ) = 120, and fI (Ψ2 ) = 122. Ψ1 is the optimal schedule.
5 Multiple-order batch sizing and scheduling with common due date In this section, we study the special case of K-IBS when all customer orders have the same due date dk = d. This problem will be denoted by K-IBS(CDD) (for K-IBS with Common Due Date) and an instance of K-IBS(CDD) will be ˆ π, b, B). This problem is encountered defined by (d, rˆ , β, when several orders must be delivered to the customers at the same date. 5.1 Dominance properties We give in this section some dominance properties that will be fully exploited in the dynamic programming algorithm solving K-IBS(CDD).
J Sched (2011) 14:541–555
549
Ψ are ordered in non-increasing tardiness weights, we have fI (Ψ ) − fI (Ψ ) ≥ βl (qi − 1 − qi+1 ) ≥ 0. Such a transfer from Bi to Bi+1 can be repeated until the SPT order is ob served for the batch sizes or Bi becomes on time.
Fig. 6 Illustration of Theorem 4
ˆ π, b, B) be an instance of KTheorem 3 Let I = (d, rˆ , β, IBS(CDD). There exists an optimal schedule of I such that the customer orders are processed in non-increasing order of the βk values. Proof Let Ψ = (N, o, S) be an optimal schedule of I . Assume that two consecutive time units t and t + 1 are respectively assigned to orders k and l, i.e., o(t) = k and o(t + 1) = l and that βk < βl . If o(t) and o(t + 1) belong to the same batch, interchanging the assignment of t and t + 1 will not affect the objective function. Otherwise, o(t) belongs to batch Bi and o(t + 1) belongs to batch Bi+1 . Let Ψ be the schedule we get by interchanging the assignment of t and t + 1. The following cases must be considered: 1. If Ci < Ci+1 ≤ d, the units processed at time t and t + 1 are early or on time in Ψ and Ψ , hence fI (Ψ ) = fI (Ψ ). 2. If Ci ≤ d < Ci+1 , the unit processed at time t is on time or early while the unit processed at time t + 1 is tardy. Thus the net cost difference fI (Ψ )-fI (Ψ ) is (βl − βk )(Ci+1 − d) ≥ 0. 3. If d < Ci < Ci+1 , the units processed at time t and t + 1 are tardy in Ψ and in Ψ and the net cost difference fI (Ψ )-fI (Ψ ) is (βl − βk )(Ci+1 − Ci ) ≥ 0. The following theorems give some structural properties on the size of the tardy batches in an optimal schedule. ˆ π, b, B) be an instance Theorem 4 (SPT) Let I = (d, rˆ , β, of K-IBS(cdd). There exists an optimal schedule of I such that the tardy batches are processed in non-decreasing order of their batch sizes. Proof Let Ψ be an optimal schedule of instance I for KIBS(CDD) with two tardy batches Bi and Bi+1 such that qi > qi+1 . We may assume from Theorem 3 that the units of Ψ are processed in a non-increasing order of the βk value. A new schedule Ψ may be built by transferring the last unit of Bi to Bi+1 . The size of batch Bi (resp. Bi+1 ) in Ψ is qi − 1 (resp. qi+1 + 1). As b ≤ qi+1 < qi ≤ B in Ψ , feasibility is maintained in Ψ (see Fig. 6). As a result of this transfer, the tardiness of the transferred unit is qi+1 time units larger while the tardiness of each other unit of Bi is one time unit smaller. Since the units of
ˆ π, b, B) be an instance of KTheorem 5 Let I = (d, rˆ , β, IBS(cdd). If two consecutive linked batches Bi and Bi+1 of an optimal schedule of I are such that Bi is uniform and tardy, then we have qi+1 − qi ≤ 1. Proof Let Ψ be an optimal schedule of I such that Bi is tardy and uniform and processes order l. Bi and Bi+1 are linked and qi < qi+1 − 1. Let t be the first time unit of Bi+1 . A new schedule Ψ is obtained by setting t as the last time unit of Bi . Ψ is feasible since qi < qi+1 − 1 and, since Bi is uniform, we have fI (Ψ ) − fI (Ψ ) = βl (qi+1 − 1) − βl qi > 0, which is a contradiction. The following corollary is directly issued from Theorems 4 and 5. ˆ π, b, B) be an instance of Corollary 4 Let I = (d, rˆ , β, K-IBS(CDD). There exists an optimal schedule of I such that the AEBS property is observed for any sequence Bj , Bj +1 , . . . , Bk of batches such that Bj , Bj +1 , . . . , Bk−1 are tardy and uniform and (Bk−1 , Bk ) are linked mixed batches. 5.2 A dynamic programming solution algorithm We now propose a dynamic programming algorithm that solves K-IBS(CDD). We assume that the customer orders k = 1, . . . , K are sorted in non-increasing order of their tardiness weights. According to Theorem 3, they will be processed in this order. Assume that Ψ is an optimal schedule of an instance I of K-IBS(CDD). Let us denote by xk the number of units of order k in the first batch of Ψ containing units of order k. In the last batch of Ψ containing units of order k, we denote by yk (resp. x) the number of units of order k (resp. of orders k + 1, . . . , K). See Fig. 7 for these definitions. We now assume that the value of yk may be computed from the values of x and xk . Since Ψ is an optimal schedule, the restriction Ψ of Ψ to the units of the time window [Rk−1 + xk , Rk + x] is also optimal. So it comes from Corollary 4 that Ψ is an AEBS and SPT schedule. Now, given xk and x, we may seek the best AEBS and SPT schedule of units of the time window [Rk−1 + xk , Rk + x] such that the size of the longest batch is at least x. For each feasible value n of the number of batches, there is a unique AEBS and SPT schedule Ψ (n). The cost of Ψ (n) is the sum of the tardiness cost of the x units of the last batch (a constant with respect to n) and the setup and tardiness costs
550
J Sched (2011) 14:541–555
Fig. 7 The definition of xk and yk
induced by the units of order k. This latter cost is clearly equal to the optimal cost f (n, Rk + x − (Rk−1 + xk )) of scheduling Rk + x − (Rk−1 + xk ) units of order k in the time window [Rk−1 + xk , Rk + x] using n batches minus the tardiness cost of the last x units of order k (also a constant with respect to n). The value n∗ leading to the best schedule Ψ (n) is thus obtained using the binary search algorithm BinS as described in Sect. 3.2.2, since the convexity property of the cost function is not destroyed by adding a constant. So, if q ∗ is the size of the longest batch of Ψ (n∗ ), we have yk = q ∗ − x. Let Hk (x) denote the minimum (total) cost of processing the first k orders given that the last batch completes at time Rk + x. The cost of the optimal schedule thus corresponds to HK (0). It comes from the definitions of x and xk that Hk (x) satisfies the following recursive relation: ⎧ min xk ∈Dk (xk ) {Gk (xk , x) + Hk−1 (xk )} ⎪ ⎨ if b ≤ rk + x Hk (x) = + ⎪ ⎩ βrk (Rk + x − d) + Hk−1 (x + rk ) if rk + x < b where Dk (xk ) = {xk , 0 ≤ xk ≤ min{rk , B}}. In the recursive formula, Gk (xk , x) refers to the total cost of processing order k given the values of xk and x. We consider the following two cases to compute Gk (xk , x). Let Fk (t, t + r) denote the cost of the optimal solution of instance (d, r, π, βk , b, B) of 1-IBS over [t, t + r], and let us denote by I the particular instance where t = Rk−1 + xk and r = rk − (xk + yk ). If d < Rk−1 + xk , then all the units of order k are tardy (see Fig. 7). Since the partial schedule of the units of order k in the time window [Rk−1 + xk , Rk − yk ] is an optimal schedule of (Rk−1 + xk , d, Rk − yk − (Rk−1 + xk ), π, βk , b, B), we have Gk (xk , x) = π + βk xk (Rk−1 + xk − d) + Fk (Rk−1 + xk , Rk − yk ) + βk yk (Rk + x − d). Moreover, since we know that Fk (Rk−1 + xk , Rk − yk ) = βk (rk − xk − yk )(Rk−1 + xk − d) + Fk (d, d + rk − xk − yk ),
Gk (xk , x) is also equal to π + βk (Rk−1 + xk − d)(rk − yk ) + Fk (d, d + rk − xk − yk ) + βk yk (Rk + x − d). If Rk−1 + xk ≤ d, then some of the batches that complete in the time window [Rk−1 + xk , Rk − yk ] could be early or on time. In that case, Gk (xk , x) mainly depends on the value Qb (I ) or QB (I ) (as defined in Sect. 3.2.3) of the starting time Si of the straddling batch Bi . If Rk−1 + xk ≤ d ≤ Rk − yk , then we have (see Fig. 8) Gk (xk , x) = π + βk xk (Rk−1 + xk − d) + Fk (Rk−1 + xk , Rk − yk ) + βk yk (Rk + x − d), where Fk (Rk−1 + xk , Rk − yk ) is equal to the minimum of the values over Si of E(Si − Rk−1 − xk ) + Fk (dk , dk + Rk − yk − Si ) − βk (Rk − yk − Si )(d − Si ) for Si ∈ {Qb (I ), QB (I )}. If Rk − yk < d < Rk + x, then all the batches that complete in [Rk−1 + xk , Rk ] are early. This case is illustrated in Fig. 9. The associated value of Gk (xk , x) is equal to π + E(rk − xk − yk ) + βk yk (Rk + x − d). If Rk + x ≤ d, then all the units of order k are early (see Fig. 10), and we have Gk (xk , x) = π + E(rk − xk − yk ). Finally, the initial conditions of the recursive relation are x1 = xK+1 = 0 and H0 (.) = 0. The optimal cost will be given by HK (0). 5.3 Complexity of the algorithm The initial sorting phase of the tardiness weights is in O(K log K) time. A preprocessing phase will consist in computing E(r) and Fk (t, t + r) for the values of r and t used in the computation of Hk (x). These values are obtained by binary search due to the convexity property. The maximal quantity to be split in the binary search is rmax =
J Sched (2011) 14:541–555
551
Fig. 8 Early, on-time, and tardy batches
Fig. 9 Almost early batches
Fig. 10 Early batches
maxk∈K {rk }. For a given order k, the cost computation of E(.) and Fk (.) is O(log rmax b ). So, for the K orders, the cost ). There are K stages in the dynamic prois O(K log rmax b gramming algorithm. At each stage k, the maximal value of xk and x is B. The computation of Hk (.) requires O(B 2 ) steps of constant time. The complexity of the dynamic pro2 gramming algorithm is then O(K(log( rmax b ) + B + log K)). Note that, when π = 0, since the binary search is not required and the batch size is at most 2b, the complexity of the algorithm reduces to O(K(b2 + log K)).
ˆ rˆ , β, π, b, B). For this case, we recall the essential by (d, dominance property of Earliest Due Date schedules (EDDschedules), we provide two polynomially solvable special cases, and we finally show that K-IBS(CTP) is solved by a variant of the dynamic programming algorithm solving KIBS(CDD). The dominance of the EDD-schedules has been proved in Robert (2007) for β = 1 and can be easily extended to any common value β. Property 9 EDD-schedules are dominant for K-IBS(CTP).
6 Multiple-order batch sizing and scheduling with distinct due dates The distinct due dates case refers to the system where different due dates are assigned to different customers. Demanddependent tardiness penalties are observed when the demand of some customers has priority over the requirements of other customers. Loss of revenue, loss of goodwill, or penalty charges define the priorities and tardiness penalties, and hence the penalties are customer dependent. We consider the special case of K-IBS and distinguish two special cases: whether the tardiness penalties βk are customer demand independent or dependent. 6.1 Demand-independent tardiness weights Let us first consider the problem where the customer orders have a Common Tardiness Penalty β. This special case is denoted K-IBS(CTP), and an instance of K-IBS(CTP) is defined
We now provide two polynomially solvable special cases of K-IBS(CTP). Consider first the special case of K-IBS(CTP) with no setup cost and unconstrained batch sizes. In that case, unitary batches will clearly provide dominant schedules. So an optimal schedule will be obtained by processing (in EDD order) the customer orders in unitary batches. The complexity of the corresponding algorithm is thus O(K log K), which is the cost of sorting the due dates. Consider now the special case of K-IBS(CTP) with no setup cost and a fixed batch size equal to B. An instance of this problem reduces to a feasibility problem. If RK is (B, B)-splittable, an optimal schedule is obtained by processing (in EDD order) the customer orders in batches of size B, otherwise the instance has no solution. The complexity of the corresponding algorithm is again O(K log K). In order to solve K-IBS(CTP), we use a modified version of the dynamic programming algorithm described in Sect. 5.2 that solves K-IBS(CDD). First, the orders are
552
processed in EDD order. Then, the main difference is that, in the modified version, yk (the number of units of order k in the last batch that processes units of order k) is now a decision variable. Indeed, in this case, some units may be early or on time and some units may be tardy in one batch, a situation that could not occur in the common due date case. In order to ensure feasibility, we require b ≤ yk + x ≤ B for k = 1, . . . , K. We thus derive the following recursive relation: ⎧ Min xk ,yk {Gk (xk , yk , x) + Hk−1 (xk )} ⎪ ⎨ if b ≤ rk + x Hk (x) = + ⎪ ⎩ βrk (Rk + x − dk ) + Hk−1 (x + rk ) rk + x < b In the recursive formula, Gk (xk , yk , x) refers to the total cost of processing order k given the values of xk , yk and x. For each fixed value of yk = y in the interval {max{0, b − x}, . . . , max{0, B − x}}, we compute Gk (xk , y, x) using the algorithm described in Sect. 5.2 for the common due date case. As there are B possible values for yk , the complexity of the dynamic programming algorithm used to solve the instance (dk , rk , βk = β, π, b, B) will be O(K(log( rmax b )+ B 3 + log K)). 6.2 Demand-dependent tardiness penalties We address in this section the special case of K-IBS. We first note that if the processing order of the customer orders is fixed (for example, the EDD order), the dynamic programming algorithm presented in Sect. 6.1 also solves the problem. However, it is important to observe that, for the general case, it may happen that no schedule such that the units of any customer order are processed consecutively is optimal. Such a situation is illustrated by the following example. Example 7 Consider the instance of K-IBS defined by K = 2, b = 1, B = 5, dˆ = (1, 2), rˆ = (2, 1), βˆ = (1, 2), and π = 0. The optimal schedule is clearly defined by N = 3, q11 = 1, q22 = 1, and q31 = 1. This schedule has three unitary batches. In the first and third batches order 1 is processed, whereas in the second batch order 2 is processed. In the rest of this section, we present two polynomial special cases with dependent tardiness penalties. Consider first the special case with no setup cost and unconstrained batch sizes. In that case, there is an optimal schedule where all the batches are unitary. The time horizon is divided into RK unitary intervals. The RK batches, which are indexed by i = 1, . . . , RK , are assigned to the K customer orders (indexed by k = 1, . . . , K). The assignment of batch Bi to order k induces the cost cik = βk (i − dk )+ where i is the completion time of batch Bi . Consequently, the problem reduces to a minimum cost network flow problem, in which the time intervals are the supply nodes, each
J Sched (2011) 14:541–555
with a unitary capacity, and the orders are the demand nodes where the requirement of node k is rk (see Fig. 11). Consider now the special case with no setup cost and a fixed batch size B. Clearly, an instance of the problem is feasible if RK is a multiple of B. If RK = N × B, we define N batches Bi , i = 1, . . . , N and, as in the preceding case, a unit of order k assigned to batch Bi incurs the cost cik = βk (iB − dk )+ . Therefore, the problem is a transportation model in which the batches correspond to the supply nodes (each with capacity B), and the orders are the demand nodes where the demand of node k is rk .
7 Computational experiments In this section, we address K-IBS(CTP) with computational experiments using the dynamic programming algorithm described in Sect. 6.1. Before the computational analysis, we present a merging procedure that improves the computational results. 7.1 Merging customer orders We assume in what follows that the customer orders follow the EDD order, i.e., d1 ≤ d2 ≤ · · · ≤ dK . Let I be an instance of the K-IBS(CTP). For any two orders k and k + 1, a merging operation consists in constructing an instance I
with K − 1 orders by deleting order k + 1 and increasing the requirement of order k by the value rk+1 . Let us denote by ¯ the optimal schedule ¯ S)) ΨI = (N, o, S) (resp. ΨI = (N¯ , o, of I (resp. I ). Since the EDD and no idle time properties are observed, o and o¯ are implicitly defined. Theorem 6 If (Rk−1 ≥ dk and Rk ≥ dk+1 ) or (Rk + B − 1 ≤ dk and Rk+1 + B − 1 ≤ dk+1 ) for instance I , then (N, S) = ¯ (N¯ , S). The theorem is illustrated for the first case in Fig. 12, where the schedule before and after the merging operation is depicted. Proof If we have Rk−1 ≥ dk and Rk ≥ dk+1 , then all the units of orders k and k +1 are tardy, in any feasible schedule. Similarly, if Rk + B − 1 ≤ dk and Rk+1 + B − 1 ≤ dk+1 , then all the units of orders k and k + 1 are on time or early, in any feasible schedule. Since βk = β, we can easily prove that if ¯ then ΨI is not optimal by contradiction. (N, S) = (N¯ , S), 7.2 Experiments The experiments are performed to measure the efficiency of the algorithm, which is implemented in the C language on a 2.6 GHz PC with 3.6 GB memory.
J Sched (2011) 14:541–555
553
Fig. 11 Network representation
Fig. 12 The merging property
In order to derive instances, we use the generation scheme provided by Congram et al. (2002) for the weighted tardiness scheduling problem. However, we do not require the weights, as the problem involves demand-independent weights. For simplicity, we set βk = 1 in our experiments. The requirements rk are randomly generated from the uniform distribution {1, 100}. There are two parameters used to compute the due dates, namely, the tardiness factor τ and the range factor ρ. Given τ , ρ and rk for all k, the due date of each customer order k is generated from the uniform distribution {RK (1 − τ − ρ/2), . . . , RK (1 − τ + ρ/2)}. Three additional parameters are used in order to define b, B and π which are respectively μb , μB and ν. We set the lower and upper bounds on batch sizes as b = RK × μb and B = RK × μB . Parameters μb and μB , respectively, refer to the lower and upper bound batch size factors. These factors set the batch constraints as a ratio of the total requirement. Similarly, in order to generate the setup costs, we use the quadratic equation, π = βk × b2 × ν, where ν refers to the setup factor. We have tested a total of 6000 instances generated with the settings described in Table 1. We observe that on average an instance is solved to optimality in less than 1 second. The minimum, average, and
Table 1 Experimental settings Parameter
Level
K
40, 50, 100
ρ
0.2, 0.4, 0.6, 0.8, 1.0
τ
0.2, 0.4, 0.6, 0.8, 1.0
μb
0.01, 0.02, 0.03, 0.04
μB
0.06, 0.08, 0.10, 0.12
ν
0.25, 0.5, 0.75, 1, 1.25
Table 2 Experimental results for the CPU time (seconds) CPU time (s) Min
Average
Max
40
0.01
0.22
1.91
50
0.01
0.22
1.71
100
0.01
0.66
4.85
K
maximum CPU times to solve the instances with respect to the number of orders are reported in Table 2. The number of customer orders K and the bounds on batch sizes μb and
554
μB are highly influential on the computational effort. However, the CPU time is lower than 1 second to solve any of the instances of the test bed.
8 Conclusion In this paper, we have addressed an integrated batch sizing and scheduling problem for a single machine. The problem aims at clustering the customer orders into batches of limited sizes to minimize the sum of tardiness penalties and setup costs. Batch sizing and scheduling are combined. We have presented some theoretical results on the structural properties of the optimal solutions. Furthermore, using these results, we have developed an efficient dynamic programming algorithm. In order to measure the efficiency of the algorithm under various problem settings, computational experiments have been performed. One important question left open by this paper is whether K-IBS(CDD) is polynomial. If, on the contrary, K-IBS is weakly NP-hard, it should also be quite interesting to investigate whether the dynamic programming could lead to a fully polynomial time approximation scheme (FPTAS). As a future extension of this research, we will incorporate earliness penalties which are essential for just-in-time production systems. In this way, lead times and work in process could be reduced. Some properties might be derived for the multiple orders general case. Furthermore, extension of the research to multi-machine production systems is valuable. The theory developed and the results presented in this paper will serve as a basis to model these production systems. Acknowledgements The authors are grateful to the anonymous referees for their helpful comments and suggestions, which have improved the presentation of the paper.
Appendix: Proof of Theorem 2 According to Theorem 1 and Corollary 1, there exists an optimal schedule either with no straddling batch or with a straddling batch Bi satisfying either Si = Qb (I ) or Si = QB (I ). We assume that Qb (I ) is (b, B)-splittable and Q B (I ), which is r − QB (I ), is (b, B)-splittable. Ψ1 includes n1 = r−d b batches. The tardiness cost of the straddling batch is βb(Qb (I ) + b − d). The cost of processing r − Qb (I ) − b units in the time window [d, d + r − Qb (I ) − b] is T (n1 − 1, r − Qb (I ) − b), and the cost of shifting Q b (I ) − b units from d to Qb (I ) + b is β(Q b (I ) − b)(Qb (I ) + b − d). Therefore, fI (Ψ1 ) = T (n1 − 1, r − Qb (I ) − b) + β(r − Qb (I ))(Qb (I ) + b − d). Now, we construct a new schedule Ψ of I where the straddling batch starts at Si = QB (I ). In the sequel, we will compare the cost of Ψ with the costs of Ψ1 and Ψ2 . If
J Sched (2011) 14:541–555
Qb (I ) < QB (I ) ≤ d, then we assign r − Qb (I ) − b units in n1 − 1 tardy batches of size b in the time interval [Qb (I ) + b, r] at a tardiness cost of T (n1 − 1, r − Qb (I ) − b) + β(r − Qb (I ) − b)(Qb (I ) + b − d). The first QB (I ) units are assigned to batches of size B in the time interval [0, QB (I )]. The batch of size of Qb (I ) + b − QB (I ) is not feasible since it is smaller than b, therefore the Qb (I ) + b − QB (I ) units will be transferred to the n1 − 1 tardy batches as follows. 1. Reorder the tardy batches so that the first batch (denoted by Bıˆ ) contains the smallest number of units (all the tardy batches remain tardy and the order independence property holds). 2. Assign one unit to Bıˆ by setting Sıˆ one time unit earlier (AEBS property is observed). 3. Reiterate Steps 1 and 2 until all the units are assigned. We now show that the schedule obtained from the previous procedure is feasible since Q B (I ) is (b, B)-splittable. We know from Property 6 that the unique AEBSschedule of the units to be processed in the time window
[QB (I ), r] with r−d b batches is feasible since QB (I ) is (b, B)-splittable. So, the schedule obtained by the procedure, which is AEBS and has r−d b batches, is feasible. In addition to feasibility, due to Corollary 3, Ψ is optimal, hence Ψ = Ψ2 . In Step 2, each assignment will increment the tardiness cost as follows. The first Qb (I ) + b − d assignments will incur a tardiness penalty of at least βb for each unit, and the remaining d − QB (I ) assignments increase the cost at least by β for each unit. Considering the cost of the initial n1 − 1 tardy batches and the cost of the transfers, fI (Ψ ) will be at least T (n1 − 1, r − Qb (I ) − b) + β(r − Qb (I ) − b)(Qb (I ) + b − d) + βb(Qb (I ) + b − d) + β(d − QB (I )). Since we have shown that fI (Ψ1 ) = T (n1 − 1, r − Qb (I ) − b) + β(r − Qb (I ))(Qb (I ) + b − d) and fI (Ψ ) = fI (Ψ2 ), we get fI (Ψ1 ) < fI (Ψ2 ). If QB (I ) < Qb (I ) < d, then Ψ2 processes more tardy units than Ψ1 and from Corollary 2 it has the same number of batches. Therefore, using the arguments of the proof of Lemma 2, fI (Ψ1 ) < fI (Ψ2 ). Finally, let Ψ0 be the best schedule with no straddling batch. We may apply the same transferring policy as for the definition of Ψ , but restricted to the units of the time window [d, Qb + b] to get a schedule Ψ
, which is equal to Ψ0 and satisfies fI (Ψ
) > fI (Ψ1 ). If Qb (I ) is not (b, B)-splittable, the result follows from Theorem 1.
References Albers, S., & Brucker, P. (1993). The complexity of one-machine batching problems. Discrete Applied Mathematics, 47, 87–107.
J Sched (2011) 14:541–555 Allahverdi, A., Ng, C. T., Cheng, T. C. E., & Kovalyov, M. Y. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3), 985–1032. Azizoglu, M., & Webster, S. (1997). Scheduling job families about an unrestricted common due date on a single machine. International Journal of Production Research, 35(5), 1321–1330. Baptiste, P. (2000). Batching identical jobs. Mathematical Methods of Operations Research, 52, 355–367. Cheng, T. C. E., & Kovalyov, M. Y. (2001). Single machine batch scheduling with sequential processing. IIE Transactions, 33, 413– 420. Coffman, E. G., Yannakakis, M., Magazine, M. J., & Santos, C. A. (1990). Batch sizing and job sequencing on a single machine. Annals of Operation Research, 26, 135–147. Congram, R. K., Potts, C. N., & Van de Velde, S. L. (2002). An iterated dynasearch algorithm for the single-machine weighted tardiness problem. INFORMS Journal on Computing, 14, 52–67. Hall, N. G., & Potts, C. N. (2003). Supply chain scheduling: batching and delivery. Operations Research, 51(4), 566–584.
555 Hall, N. G., & Potts, C. N. (2005). The coordination of scheduling and batch deliveries. Annals of Operation Research, 135, 41–64. Potts, C. N., & Kovalyov, M. Y. (2000). Scheduling with batching: a review. European Journal of Operational Research, 120(2), 228– 249. Robert, A. (2007). Optimisation des batches de production. Ph.D. thesis, Université Pierre et Marie Curie, Paris 6. Santos, C. A., & Magazine, M. J. (1985). Batching in single operation manufacturing systems. Operations Research Letters, 4, 99–103. Selvarajah, E., & Steiner, G. (2006). Batch scheduling in a two-level supply chain: a focus on the supplier. European Journal of Operational Research, 173, 226–240. Sung, C. S., & Joo, U. G. (1997). Batching to minimize weighted mean flow time on a single machine with batch size restrictions. Computers and Industrial Engineering, 32(2), 333–340. Webster, S., & Baker, K. R. (1995). Scheduling groups of jobs on a single machine. Operations Research, 43, 692–703.