J Sched DOI 10.1007/s10951-015-0433-1

Approximation algorithms for inventory constrained scheduling on a single machine Ehab Morsy1,2 · Erwin Pesch3

© Springer Science+Business Media New York 2015

Abstract We consider the problem of scheduling a set of jobs on a single machine subject to inventory constraints, i.e., conditions that jobs add or remove items to or from a centralized inventory, respectively. Jobs that remove items cannot be processed if the required number of items is not available. We focus on scheduling problems on a single machine where the objective is to minimize the total weighted completion time. In this paper, we design 2-approximation algorithms for special cases of the problem that run in polynomial time. Keywords Approximation algorithms · Scheduling problem · Weighted completion time · Inventory constraints

1 Introduction We consider a scheduling problem which has originally been introduced by Briskorn et al. (2010) and which is to schedule jobs on a single machine subject to inventory constraints. Jobs insert to and remove items from a centralized inventory. Consequently, a job removing items can only be processed if the inventory provides enough items at its start time. The

B

Ehab Morsy [email protected] Erwin Pesch [email protected]

1

Department of Management Information Science, Siegen University, Holderlinstr. 3, 57068 Siegen, Germany

2

Department of Mathematics, Suez Canal University, Ismailia 22541, Egypt

3

Department of Management Information Science, Siegen University, Kohlbettstr. 15, 57068 Siegen, Germany

objective is to minimize the total weighted completion time. For possible applications of the problem, see Briskorn et al. (2010) and Briskorn et al. (2013) and the references therein. We assume that all jobs are available for processing at the beginning of the planning horizon. Furthermore the inventory’s capacity is unlimited and our model can initially be applied to those real-world settings where inventory capacity is not an issue. Inventory constraints have been considered in project scheduling; see, for example, Bartels and Zimmermann (2009), Neumann and Schwindt (2002), Neumann et al. (2005), and Schwindt and Trautmann (2000). In Neumann and Schwindt (2002) it has been shown that inventory constraints are a generalization of both renewable and nonrenewable resources. Thus, finding a minimum makespan project schedule considering (standard) precedence constraints as well as inventory constraints is a generalization of the well-known resource constrained project scheduling problem which is known to be strongly NP-hard. Scheduling of trucks at cross-dock terminals has been considered in Boysen et al. (2010). Trucks arrive to either drop off or pick up goods. The model assumes that the terminal has two gates. While trucks are unloaded at the first gate, they are loaded at the second one. Boysen et al. (2010) showed that minimizing makespan is strongly NP-hard even if all processing times are equal. Yu and Egbelu (2008) considered a similar model and developed a heuristic to solve the problem. McWilliams et al. (2005) proposed a genetic algorithm in order to solve a problem with more than two gates. Further truck scheduling procedures varying, e.g., with regard to the number of dock doors, the objective, whether or not transportation times inside the terminal are considered and whether or not commodities are interchangeable between outbound trucks, are presented by Boysen (2010), Boysen et al. (2010), Chen and Lee (2009), Chen and Song (2009), and Miao et al. (2009). A recent review article on

123

J Sched

truck scheduling at cross-docking terminals is provided by Boysen and Fliedner (2010). In maintenance scheduling, maintenance activities are usually limited to fixed time windows, see Lee (2004), or a lower and an upper bound for the time span between two maintenance activities has to be observed, see Chen (2008) and Sun and Li (2010). Usually, durations of maintenance activities are fixed in advance, whereas Mosheiov and Sarig (2009) restricted the number of maintenance activities. In a stream of papers on maintenance scheduling it is often assumed that processing times of jobs are affected by preceding maintenance activities, see Mosheiov and Sarig (2009) and Zhao and Tang (2010). Our model contributes to this area by allowing total flexibility for the scheduling of jobs as long as the maintenance state does not drop below zero. Note that jobs representing maintenance activities should not have a direct impact on the objective value. Briskorn et al. (2010) elaborated on the computational complexity and distinguish polynomially solvable special cases. The more general single machine cases with objective to minimize maximum lateness and total weighted completion time have been proven to be strongly NP-hard. Recently, Briskorn and Leung (2013) developed a branch and bound algorithm for the problem with the objective of minimizing the maximum lateness among all jobs. For the problem with objective to minimize the total weighted completion time, Briskorn et al. (2013) designed two exact algorithms: branch and bound and dynamic programming. In this paper we present constant factor approximation algorithms for some special cases of the problem. This paper is organized as follows. In the next section we formally specify the details of the problem. In Sect. 3, we develop constant factor approximation algorithms for some NP-hard special cases of the underlying problem. We conclude the paper in Sect. 4.

2 Problem description Consider a single machine and a set J of n jobs where each job j ∈ J is specified by its processing time p j , its weight w j , and its inventory modification δ j . The processing time p j of job j is the total time j uses the machine for being completed. A job’s weight describes its influence on the objective value of a schedule and thus intuitively its importance. The inventory modification parameter δ j of job j specifies the change of the inventory level when j is started being processed until its completion. Consequently, if δ j > 0 job j adds items to the inventory and j removes items from the inventory if δ j < 0. We may assume that inventory changes at the start of processing, at the completion of processing, or continuously during processing. However, as long as the inventory level changes during processing of a job on a sin-

123

gle machine, there is no relevant difference between these models. We refer to jobs having positive or negative inventory modifications as positive jobs or negative jobs and denote the corresponding subsets of jobs as J + with |J + | = n + and J − with |J − | = n − , respectively. Without loss of generality we may assume that processing times, weights, and inventory modifications are integers. Let an initial inventory I0 ≥ 0 specify the inventory level at time zero, before the first job starts being processed. Consequently, we refer to the inventory level after completing the kth job as Ik . Hence, for  a given sequence σ of jobs we have Ik = I0 + 1≤i≤k δσ (i) , where σ (i) is the ith job in σ . Let S ⊂ J × N be a set of tuples where the first entry specifies a job j and the second one defines the completion time C j of job j which is the end of the period in which job j is completed. All jobs have to be processed and the machine can only process one job at a time. We consider the non-preemptive case where a job’s processing cannot be interrupted. We say a sequence σ induces a schedule S if for any k, , 1 ≤ k <  ≤ n implies Cσ (k) + pσ () ≤ Cσ () . A schedule S is feasible if Ik ≥ 0, 1 ≤ k ≤ n, for the sequence inducing S. A sequence inducing a schedule is also said to be a schedule. We assume that a feasible schedule always exists, i.e. In ≥ 0. We consider a regular machine scheduling objective function,  namely we minimize total weighted completion time j∈J w j C j . As there are no release times an optimal schedule exists with no machine idle time. Such a schedule is fully specified by its inducing sequence. Extending the wellknown three field notation as proposed by Graham et al.  (1979), the problem may be specified as 1|inv| w j C j , see Briskorn et al. (2010). Briskorn et al. (2010) showed that  1|inv| w j C j is strongly NP-hard even if (i) all positive jobs have the same processing times, weights, and inventory modifications, and all negative jobs have either the same weights or the same processing times, or (ii) all negative jobs have the same processing times, weights, and inventory modifications, and all positive jobs have either the same weights or the same processing times. Independently, Kononov and Lin (2010) studied the computational complexity of a general version of 1|inv| w j C j in which each job j consumes an amount of α j items from the inventory at the beginning of its processing and adds an amount of β j items to the inventory after its completion. Namely Kononov and Lin (2010) proved that their problem is strongly NP-hard even if, for each job j ∈ J , either β j − α j ≥ 0 or β j − α j ≤ 0 and p j = 1. They also designed 2-approximation algorithms for these special cases. Note that, an instance of the problem introduced by Briskorn et al. (2010) can be reduced to an instance of that of Kononov and Lin (2010) by assuming that α j = 0 and β j = δ j for each positive job j and α j = |δ j | and β j = 0 for each negative job j. This implies that algorithms designed for the problem of Kononov and Lin (2010) guarantee the

J Sched

same performance for that of Briskorn et al. (2010). By the choice of the parameters α j and βi in Briskorn et al. (2010), an instance there satisfies β j − α j ≥ 0 (resp., β j − α j ≤ 0) if all jobs are positive (resp., negative), which is polynomially solvable (by applying WSPT rule).  Let V be an instance of 1|inv| w j C j with initial inventory I0 such that each job j has a processing time p j , a weight w j , and an inventory modification δ j . We construct ¯ another instance  V of the problem with initial inventory I¯0 = I0 + j∈J δ j such that job j has a processing time p¯ j = w j , a weight w¯ j = p j , and an inventory modification δ¯ j = −δ j . The proof of the following lemma is similar to that of Theorem 3 in Kononov and Lin (2010).

Problem A: All positive jobs have the same processing time p, weight w, and inventory modification δ; all negative jobs have either the same weight or the same processing time, I0 = 0, and, for any two negative jobs j and k with |δ j |, |δk | < δ, it holds δ j ≥ δk if and only if p j /w j ≤ pk /wk . Problem B: All negative jobs have the same processing time p, weight w, and inventory modification δ, all positive jobs have either the same weight or the same processing time, I0 = 0, and, for any two positive jobs j and k with δ j , δk < |δ|, it holds δ j ≥ δk if and only if p j /w j ≤ pk /wk .

Lemma 1 A schedule σ = σ (1), σ (2), . . . , σ (n) is optimal for V if and only if σ = σ (n), σ (n − 1), . . . , σ (1) is optimal ¯ for V.

It is not difficult to see from Briskorn et al. (2010) that problems A and B remain NP-hard, and hence we turn our attention to design efficient approximation algorithms for these problems. In this paper, we propose 2-approximation algorithms for problems A and B. By Lemma 1, it suffices to present algorithms for only one of problems A and B.

Proof Assume that σ = σ (1), σ (2), . . . , σ (n) is an optimal schedule for V. We show that σ = σ (n), σ (n − 1), . . . , σ (1) ¯ We first prove the feasibility of is an optimal schedule for V. σ¯ by showing that I¯σ¯ (k) ≥ 0 for each k = 1, 2, . . . , n. By the definition of I¯σ¯ (k) and I¯0 , we have I¯σ¯ (k) = I¯0 +

 1≤i≤k

+





δ¯σ¯ (i) = I0 +

δσ¯ (i)

1≤i≤n

δ¯σ¯ (i) = I0 +

1≤i≤k



δσ¯ (i) .

(1)

k+1≤i≤n

Note that σ¯ (i) = σ (n − i + 1) for all i = 1, 2, . . . , n, and hence equation (1) implies that I¯σ¯ (k) = I0 +



δσ (i) = Iσ (n−k) ≥ 0,

1≤i≤n−k

where the last inequality follows from the feasibility of σ . Now, we show that the total weighted completion times of the schedules σ and σ¯ are equal. Let Cσ ( j) and Cσ¯ ( j) denote the completion time of jobs σ ( j) and σ¯ ( j), respectively. We have 

wσ ( j) Cσ ( j) =

1≤ j≤n



wσ ( j)

1≤ j≤n

=



=

pσ ( j)

=



w¯ σ¯ ( j)

3.1 Preliminaries Let S be a schedule on n jobs induced by sequence σ . A schedule F is said to be a partial schedule of S if it is induced by the sequence σ (i), σ (i + 1), . . . , σ (k) for some 1 ≤ i ≤ k ≤ n. followed by G, of a given schedule S, if

wσ (i)



In this section we present a 2-approximation algorithm for problem A. We first present some basic results that will be used frequently throughout the rest of the paper. For the sake of simple explanation, we propose a 2-approximation algorithm for a special case of problem A in which the absolute value of the inventory modification of each negative job is at least δ (the inventory modification of every positive job). Finally, we extend our algorithm to give the same performance factor for the general formulation of problem A.

Lemma 2 For any two adjacent partial  schedules,  say F S

 j∈G j∈G

pj wj

<

 j∈F j∈F

pj wj

,

obtained by interchanging F and G, then the schedule preserving all the other positions, has a total weighted completion time less than that of S.

j≤i≤n

1≤ j≤n



pσ (i)

1≤i≤ j

1≤ j≤n





3 Approximation algorithm to problem A

p¯ σ¯ (i)

1≤i≤ j

w¯ σ¯ ( j) Cσ¯ ( j) .

1≤ j≤n

 

This completes the proof. Consider the following special cases of 1|inv|



wjCj.

Proof Assume that the first job in F starts its processing at time t. We observe that S  differs from S only in the |F| + |G| positions reserved for jobs in F and G, in which the schedule S  first processes jobs in G followed by jobs in F (in each of the partial schedules F and G, jobs have the same order as in S). Note that the total weighted com-

123

J Sched

pletion time of all jobs processed before (respectively, after) F and G remains unchanged. Hence, the difference of the total weighted completion times of the two schedules S and S  is due to only the jobs of the two partial schedules F and G. On the other hand, the total weighted completion time of F and G equals the total weighted completion time of F and the completion time of G plus the quan  total weighted tity ( j∈F p j )( j∈G w j ) if F is processed before G in the   whole schedule and ( j∈G p j )( j∈F w j ) otherwise. This implies that the total weighted completion time of S  is less than that of S, which completes the proof.   Now, consider an instance of problem A. p Note that, if wp ≤ w jj holds for all jobs j ∈ J − , then the problem is polynomially solvable. Namely the schedule S obtained by arranging all positive jobs in an arbitrary order in the first n + positions of S followed by all negative jobs arranged in the next n − positions due to the WSPT rule is an optimal schedule to problem A in this case. Thus, throughout p this section we focus on the case where wp > w jj holds for

some j ∈ J − . In particular, we can assume, without loss of p generality, that wp > w jj holds for all j ∈ J − . J −,

We start by showing that if, for each job j ∈ it holds |δ j | = m j δ for some positive integer m j , then the following simple procedure outputs an optimal schedule for the problem in this case. For each job j ∈ J − , we first assign a set M j of arbitrary m j distinct positive jobs to j, and then we form a partial schedule  S j by arranging jobs in M j in an S j followed by job arbitrary order in the first m j positions of  j. Next, we construct a schedule  S over all jobs by arranging all these partial schedules  S j , j ∈ J − , in non-decreasing order of the ratio of the total processing times of all jobs m p+ p in each partial schedule to their weights (i.e., m jjw+wjj ), and then attaching the remaining positive jobs (if any) to the end of the schedule. Clearly, by the construction, the resulting schedule  S is feasible. It remains to show that  S is optimal. Lemma 3 The schedule  S is an optimal schedule for problem A with |δ j | = m j δ for all jobs j ∈ J − , where m j is a positive integer. Proof Assume for the contrary that there is an optimal schedule S that has less total weighted completion time than that of  S. By the feasibility of the schedule S, we conclude that, for every job j ∈ J − , the number of positive jobs processed  before j in S is at least x∈J − m x , where J j− denotes the set j

of all jobs from J − processed before j in S, including j itself. We first show that, for each j ∈ J − , the number of positive  jobs processed before j in S is exactly x∈J − m x . Assume j

for the contrary that there is a non-empty set of jobs in J − such that the number of positive jobs processed before each

123

job j of this set in S is more than



x∈J j− m x . Let k denote and k  denote the positive

the first processed job of this set, job processed directly before k in S. Then the schedule S  obtained by interchanging k and k  , preserving all the other jobs as in S, is feasible and attains a total weighted completion p time less than that of S since wk  = wp > wpkk holds. This k contradicts the optimality of S. For each j ∈ J − , let M j denote the set of positive jobs processed between j and the last job in J − processed before j in S. This implies that S is formed from a set of partial schedules S j , j ∈ J − , such that S j is formed from all jobs in M j ∪ { j}, in addition to the partial schedule containing all positive jobs processed after the last job of J − in S. Note that, for each j ∈ J − , the cardinality of the two sets M j and S j and S j are M j and the cardinality of the partial schedules  identical. Moreover, for each j ∈ J − , the ratio of the total processing times to the total weights of all jobs in  S j and S j are identical. Now, assume that there exist two adjacent partial schedules, say S j followed by Sk , in S such that  

j∈Sk j∈Sk

 m j p + pj m k p + pk j∈S j p j = < = . wj m k w + wk w m j jw + wj j∈S j pj

Let S  denote the schedule obtained by interchanging the positions of the two partial schedules S j and Sk , preserving the positions of all the remaining jobs as in S. Note that, by the construction, the schedule S  is feasible. On the other hand, by Lemma 2, the total weighted completion time of S  is less than that of S. This contradicts the optimality of S.   The rest of this section is devoted to designing approximation algorithms for problem A. A schedule L (which is not necessarily feasible) is said to be a lower bound schedule of problem A if the total weighted completion time of L is at most that of the optimal weighted completion time of the problem. Intuitively, the proposed algorithm constructs a lower bound schedule over all jobs of the problem, and then transforms this schedule to a feasible schedule by applying necessary job interchanges. Clearly, the schedule obtained by ordering all jobs due to the weighted shortest processing time (WSPT) rule (see Blazewicz et al. 2007 or Pinedo 2008) is a lower bound to the underlying problem, however, in general, the ratio of the optimal weighted completion time to the total weighted completion time of this schedule might be unbounded. Therefore, we turn our attention to define a “good” lower bound schedule L to the problem in the sense that (i) the total weighted completion time of L is close to the optimal weighted completion time, and (ii) based on L, we can obtain a feasible schedule to the original problem with total weighted completion time at most a constant factor of that of L.

J Sched

Algorithm 1 Approximation Algorithm for problem A with |δ j | ≥ δ for all j ∈ J − . Input: An instance of problem A with |δ j | ≥ δ for all j ∈ J − . Output: A feasible schedule S to this instance. 1. For each j ∈ J − , do |δ | 2. Assign a set M j of arbitrary m j = δj  distinct positive jobs to j. 3. Construct a schedule L j that consists of jobs in M j followed by j. 4. EndFor m p+ p 5. Arrange all L j , j ∈ J − , in non-decreasing order of m jjw+wjj to get a schedule L. 6. Attach unassigned positive jobs (if any) to the end of L, and let S := L. 7. While there exists a job j ∈ J − with I j < 0 in S do 8. Find the first job k ∈ J − in S such that Ik < 0. 9. Move the last positive job in S directly before k. 10. EndWhile 11. Output the resulting schedule S.

3.2 The 2-approximation for inventory-heavy jobs For simplicity, we start by constructing an approximate schedule to problem A in the case where |δ j | ≥ δ for all |δ | j ∈ J − . Define m j = δj  for all jobs j ∈ J − . Note that, by the assumptions, m j ≥ 1 holds for all jobs j ∈ J − . For each job j ∈ J − , we first assign a set M j of arbitrary m j distinct positive jobs to j, and then we form a partial schedule L j by arranging jobs in M j in an arbitrary order in the first m j positions of L j followed by job j. Next, we construct a schedule L by arranging all these partial schedules m p+ p L j , j ∈ J − , in non-decreasing order of m jjw+wjj , and then attaching the remaining positive jobs (if any) to the end of the schedule. Finally, we transform the obtained schedule L to a feasible schedule S by repeating the following procedure as long as there is a job j ∈ J − in the current schedule (initially, the current schedule is L) with inventory balance I j < 0. We first find the first job k ∈ J − in the current schedule such that Ik < 0, and then we move the last positive job in the current schedule to be processed directly before job k. Note that, for each j ∈ J − , at most one new positive job is moved to be processed directly before j. Clearly, at the end of this procedure, a nonnegative inventory is preserved all over the schedule, and hence the resulting schedule S is feasible. A formal description of the above algorithm is given in Algorithm 1. First, we show that the schedule L computed in Algorithm 1 is a lower bound schedule of problem A with |δ j | ≥ δ for all jobs j ∈ J − . Lemma 4 The schedule L computed in Algorithm 1 is a lower bound of problem A with |δ j | ≥ δ for all jobs j ∈ J − . Proof Define problem A that preserves all parameters of problem A, except that, for each j ∈ J − , the inventory

modification δ j of j in problem A satisfies |δ j | = m j δ, |δ |

where m j = δj . It is easy to observe that the optimal total weighted completion time of problem A is at most that p of problem A since wp > w jj for all j ∈ J − . On the other hand, Lemma 3 implies that the schedule L is an optimal schedule of problem A . Hence, the total weighted completion time of L is at most the optimal weighted completion time of problem A, which completes the proof.   Next, we prove the approximation factor of the schedule S output from Algorithm 1. Theorem 1 The schedule S output from Algorithm 1 is a 2approximate schedule to problem A in the case where |δ j | ≥ δ for all jobs j ∈ J − . Proof We prove the theorem by bounding the total weighted completion time of S in term of that of the lower bound schedule L. First, we consider the total weighted completion time of L. Let J − = {1, 2, . . . , n − } such that for all j, k ∈ J − with j < k, the job j is processed before k in L. Thus, the total weighted completion time of L is given by   pwn + (n + + 1) + (m i p + pi ) wk 2 1≤i≤n − i≤k≤n − ⎛ ⎞   +w pi ⎝n + − mk ⎠ . 1≤i≤n −

(2)

1≤k≤i

Note that, for each job j ∈ J − , at least one positive job is processed directly before j in L since δ j ≥ δ for all j ∈ J − , and hence m j ≥ 1 for all j ∈ J − . Now, we consider the total weighted completion time of S. Note that, during the construction of S from L, we observe that, for each j ∈ J − , at most one new positive job is moved to be processed directly before j. Therefore, the total weighted completion time of the schedule S is at most   pwn + (n + + 1) ((m i + 1) p + pi ) wk + 2 1≤i≤n − i≤k≤n − ⎞ ⎛   +w pi ⎝n + − (m k + 1)⎠ . (3) 1≤i≤n −

1≤k≤i

From (2) and (3), we see that the total weighted completion S minus that of L is bounded from above by  time of p 1≤i≤n − i≤k≤n − wk , which is at most the total weighted completion time of L since m i ≥ 1 for all i ∈ J − . That is, the total weighted completion time of S is at most twice that of L, which completes the proof of the theorem.  

123

J Sched

3.3 The 2-approximation

Algorithm 2 Approximation Algorithm for General Instances of Problem A.

Now, we propose an approximation algorithm for the general formulation of problem A. Let J− and Jh− denote the sets of all light and heavy jobs in J − to the condition that a job j ∈ J − is said to be light (resp., heavy) if |δ j | < δ (resp., |δ j | ≥ δ). We first construct a lower bound schedule L to the problem as follows. Consider the set Jh− . For each job j ∈ Jh− , we construct a partial schedule L j by assigning a set M j of arbitrary m j = |δ |

δj  distinct positive jobs to j, and then ordering jobs in M j in an arbitrary order in the first m j positions of L j followed by job j. Next, consider the set J− . A set {Z 1 , Z 2 , . . . , Z q } of pairwise-disjoint non-empty subsets of J− is said to be a q partition of J− if ∪i=1 Z i = J− holds. We first show the following partition of jobs in J− .

Input: An instance of problem A. Output: A feasible schedule S to this instance. 1. Define Jh− = { j ∈ J − | |δ j | ≥ δ} and J− = { j ∈ J − | |δ j | < δ}. 2. For each j ∈ Jh− , do 3. Assign a set M j of m j = |δ j |/δ distinct positive jobs to j. 4. Construct a schedule L j that consists of jobs in M j followed by j. 5. EndFor 6. Apply Lemma 5 to J− to get a partition {Z 1 , Z 2 , . . . , Z q } of J− . 7. For each i = 1, 2, . . . , q, do 8. Assign one of the remaining positive jobs, say j, to Z i . 9. Construct a schedule L j that consists of j followed by jobs in Z i arranged due to WSPT rule. 10. EndFor 11. Arrange all L j , j ∈ Jh− , and L i , i = 1, 2, . . . , q, in non-decreasing order of the ratio of total processing times of jobs in the partial schedule to their total weights to get a schedule L. 12. Attach the remaining positive jobs to the end of L, and let S := L. 13. While there exists a job j ∈ J − with I j < 0 in S do 14. Find the first job k ∈ J − in S such that Ik < 0. 15. Move the last positive job in S directly before k. 16. EndWhile 17. Output the resulting schedule S.

Lemma 5 There exists a partition {Z 1 , Z 2 , . . . , Z q } of J− such that

(i) For any two sets Z i and Z i  with i  > i, it holds p j /w j ≤ p j  /w j  for all j ∈ Z i and j  ∈ Z i  .  (ii) For each i = 1, 2, . . . , q − 1, it holds δ ≤ j∈Z i |δ j | <  2δ, and j∈Z q |δ j | < 2δ. Proof We compute a desired partition by applying the following simple iterative algorithm as long as there exists a job in J− that is not assigned yet to a set in the partition. In particular, in the ith iteration, the algorithm constructs a set Z i as follows. Initialize Z i = ∅. While the total absolute inventory of all jobs in Z i is less than δ and the set J− − ∪x≤i Z x is not empty, we repeatedly add a job j of the least δ j (or the least p j /w j ) from the set of all unassigned jobs in J− (i.e., from J− − ∪x≤i Z x ) to Z i . Note that, conditions (i) and (ii) follow immediately by the choice of jobs in the algorithm.   Consider the partition {Z 1 , Z 2 , . . . , Z q } of J− computed in Lemma 5. For each i = 1, 2, . . . , q, we construct a corresponding partial schedule L i formed from one of the unassigned yet positive jobs followed by all jobs in Z i arranged due to the WSPT rule. Now, we construct a schedule L overall jobs by arranging all the resulting partial schedules L j , j ∈ Jh− , and L i , i = 1, 2, . . . , q, in non-decreasing order of the ratio of total processing times of all jobs in the partial schedule to their total weights, and then attaching all the unassigned positive jobs (if any) to the end of the schedule. Finally, we transform L to a feasible schedule S by repeating the following procedure as long as there is a job j ∈ J − in the current schedule (initially, the current schedule is L) with inventory balance I j < 0. We first find the first job k ∈ J − in the current schedule such that Ik < 0, and then we move

123

the last positive job in the current schedule to be processed directly before job k. Note that, for each j ∈ Jh− , at most one new positive job is moved to be processed directly before j, and for each i = 1, 2, . . . , q −1, at most one new positive job is moved to be processed before a job in Z i . Clearly, at the end of this procedure, a nonnegative inventory is preserved all over the schedule, and hence the resulting schedule S is feasible. A formal description of the above algorithm is given in Algorithm 2. We first show that the schedule L computed in Algorithm 2 is a lower bound to problem A. Lemma 6 The schedule L computed in Algorithm 2 is a lower bound of problem A. Proof Define problem A that preserves all parameters of problem A, except that inventory modifications δ j of the negative jobs in problem A satisfy, (i) for each i = 1, 2, . . . , q,  it holds j∈Z i |δ j | = δ, (ii) for each job j ∈ Jh− , it holds |δ |

|δ j | = δj δ, and (iii) for any two jobs j, k ∈ J− , it holds δ j ≥ δk if and only if p j /w j ≤ pk /wk . It is easy to see that the optimal total weighted completion time of problem A is p at most that of problem A since wp > w jj for all jobs j ∈ J − , and hence it suffices to show that the schedule L is an optimal schedule of problem A . Clearly, by the construction, L is a feasible schedule to problem A . Assume for the contrary that there is an optimal schedule S of problem A that has less total weighted completion time than that of L. First we focus on the properties of all jobs of Jh− in S. For each j ∈ Jh− , let M j denote the set of positive jobs processed between j and the last negative job j  processed

J Sched

before j in S. We show that, for each j ∈ Jh− , the cardinality of M j equals m j , i.e, M j has the same cardinality as the set M j of all positive jobs processed between j and the last negative job processed before j in L. Consider the following two cases. In the first case, the cardinality of M j is less than m j . Let k denote the last positive job processed before j  in S. By the choice of k, we see that the job k  processed directly after k is a negative job. Now, let S  denote the schedule obtained by interchanging k and k  , preserving all the other positions as in S. By the feasibility of S, we conclude that S  is feasible since |δ j | = m j δ. Moreover, S  attains a total weighted completion p time less than that of S since wpkk = wp > wk  holds. This k contradicts the optimality of S in this case. In the second case, the cardinality of M j is more than m j . Then the schedule S  obtained by interchanging j and the positive job processed directly before j in S is feasible and attains a total weighted completion time less than that of S p since wp > w jj holds. This contradicts the optimality of S in this case. Hence, for each j ∈ Jh− , the cardinality of M j in S equals m j . Define, for each j ∈ Jh− , the partial schedule S j of S formed from all jobs in M j ∪ { j}. We observe that, for each j ∈ Jh− , the total weighted completion times (resp., the ratios of the total processing times to the total weights of all jobs) of L j and S j are identical since all the positive jobs have the same processing times, weights, and inventory modifications. Next we focus on the properties of all jobs of J− in S. First, we show that, for any two jobs j, k ∈ J− , the job j is processed before k in S if and only if p j /w j < pk /wk holds. Assume for the contrary that there exists a pair of jobs in S that does not obey this rule. Let k ∈ J− denote the first job in S such that there exists a job j processed after k with p j /w j < pk /wk . Let S  denote the schedule obtained by interchanging j and k. Note that the total weighted completion time of S  is less than that of S since p j /w j < pk /wk and all negative jobs have either the same weight or the same processing time. On the other hand, by the feasibility of S, the schedule S  is feasible since |δ j | < |δk | holds. This contradicts the optimality of S. Consider the partition {Z 1 , Z 2 , . . . , Z q } of J− defined in Lemma 5. By the construction of L, we see that all jobs in each set of this partition are adjacent in L. Let {Z 1 , Z 2 , . . . , Z q  } be the partition of the least cardinality of J− such that, for each i = 1, 2, . . . , q  , all jobs in Z i are adjacent in S. We show that, for each i = 1, 2, . . . , q  , exactly one positive job is processed directly before the first job from Z i in S. Consider the following two cases. In the first case, there exists a set Z i such that more than one positive job is processed directly before the first job j from Z i in S. Let k denote the positive job processed directly

before j in S. Now, let S  denote the schedule obtained by interchanging j and k, preserving all the other positions as in S. By the feasibility of S, we conclude that the schedule S  is feasible since the absolute inventory |δ j | of j is less than δ. Moreover, S  attains a total weighted completion time less p than that of S since wpkk = wp > w jj holds. This contradicts the optimality of S in this case. In the second case, there exists a set Z i such that the job processed directly before the first job from Z i in S is a negative job. Let j denote the negative job processed before the first job from Z i in S. By the definition of Z i , we conclude that j belongs to Jh− . Let k denote the positive job processed before j. Now, let S  denote the schedule obtained by interchanging j and k, preserving all the other positions as in S. By the feasibility of S, we conclude that the schedule S  is feasible. Moreover, S  attains a total weighted completion p time less than that of S since wpkk = wp > w jj holds. This contradicts the optimality of S in this case. Hence, for each i = 1, 2, . . . , q  , the partial schedule Si of S is formed from one positive job followed by all jobs in Z i arranged due to the WSPT rule. Now, we show that q = q  and Z i = Z i for all i = 1, 2, . . . , q. Assume for the contrary that there exist two sets Z x and Z x such that Z x = Z x holds for some index 1 ≤ x ≤ min{q, q  }. Let i denote the smallest index such that Z i = Z i . Recall that, for any two jobs j, k ∈ J− , job j is processed before k in S if and only if p j /w j < pk /wk holds. This implies that the cardinality of Z i is at most that of Z i since the total absolute inventory of all jobs in Z i (resp., Z i ) equals (resp., is at most) δ. Moreover, all jobs in Z i are identical with the corresponding jobs in Z i . Now, assume the cardinality of Z i is strictly less than that of Z i and let j denote a job in Z i that does not belong to Z i . Assume that p j /w j is smallest among all those jobs. Thus, p j /w j ≤ pk /wk for all jobs in J− that do not belong to Z i . Hence, job j is the  in S. Let S  denote the schedule obtained first job of Z i+1 by interchanging j and the positive job k processed directly before j in S. Note that the total weighted completion time p of S  is less than that of S since the ratio wpkk = kp > w jj . On the other hand, by the feasibility of S, the schedule S  is feasible since the total absolute inventory of all jobs in Z i equals δ. This contradicts the optimality of S. Hence, for each i = 1, 2, . . . , q, the total weighted completion times (resp., the ratios of the total processing times to the total weights of all jobs) of L i and Si are identical. Finally, we discuss the order of the partial schedules S j , j ∈ Jh− , and Si , i = 1, 2, . . . , q, in S. Consider the set {S j | j ∈ Jh− } ∪ {Si | i = 1, 2, . . . , q} of partial schedules in S. Assume that there exist two adjacent partial schedules in this set, say F followed by G, in S such that

123

J Sched

 

j∈G

pj

j∈G w j

 <

j∈F

pj

j∈F w j

.

Let S  denote the schedule obtained by interchanging the partial schedules F and G, preserving the positions of all the remaining jobs as in S. Note that, by the construction of the partial schedules F and G, we conclude that S  is feasible. On the other hand, by Lemma 2, the total weighted completion time of S  is less than that of S. This contradicts the optimality of S.   Next, we prove the approximation factor of the schedule S output from Algorithm 2. The proof is similar to that of Theorem 1. Theorem 2 Algorithm 2 outputs a 2-approximate schedule S of problem A in O(n log n) time. Proof Consider the lower bound schedule L constructed in the algorithm. For each heavy negative job j ∈ Jh− , at least one positive job is processed directly before j in L. Also, for each i = 1, 2, . . . , q, exactly one positive job is processed directly before the first job of Z i in L. On the other hand, during the construction of S from L, at most one positive job is moved to be processed before each heavy negative job j ∈ Jh− , and at most one positive job is moved to be processed before a job of each set Z i , i = 1, 2, . . . , q. Therefore, the total weighted completion time of S is at most twice that of L. This proves the first part of the theorem. The time complexity of Lemma 5 in line 6 of the algorithm is bounded from above by the time complexity of the algorithm used to arrange all jobs in J− due to their inventory modifications. On the other hand, the time complexity of line 11 is bounded by the time complexity of the algorithm used to arrange all the constructed partial schedules L j , j ∈ Jh− , and L i , i = 1, 2, . . . , q in the lower bound schedule L. Thus, the time complexity of Algorithm 2 is bounded from above by O(n log n), the complexity of the best known sorting algorithm. This completes the proof of the theorem.   The approximation bound proved in Theorem 2 is tight for the algorithm. Consider an instance of problem A in which, (i) all negative jobs have the same weight w  , (ii) |δ j | = 2δ−ε for all negative jobs j, where ε is a small enough nonnegative number, and (iii) the values of the two parameters w and p are large enough comparing to w and all p j , j ∈ J − . By applying the proposed algorithm to this instance of problem A, we get a lower bound schedule L and an approximate schedule S of total weighted completion times described in equations (2) and (3), respectively (since |δ j | ≥ δ for all negative jobs j). Note that, condition (ii) implies that m j =

|δ j |/δ = 1 for all negative jobs j. We observe that the total weighted completion time (3) of S is nearly twice that in (2), the total weighted completion time of L.

123

The following result on problem B follows directly from Lemma 1 and Theorem 2. Theorem 3 Algorithm 2 can be applied to get a 2-approximate schedule of problem B.

4 Conclusion In this paper, we have studied the problem of scheduling a set of jobs in a single machine under inventory constraints. It is well known that this problem in strongly NP-hard even if all jobs have unit weights and either positive or negative jobs are identical. We have designed 2-approximation algorithms for some NP-hard special cases of the original problem. Constructing a constant factor approximation algorithm for the general formulation of the problem is still an interesting open question. Acknowledgments E. Morsy has been supported by the Alexander von Humboldt Stiftung, E. Pesch has been supported by the German Science Foundation (DFG) through the grant ”Optimierung der Containerabfertigung in Umschlagbahnhöfen” (PE 514/16-1,2), as well as the Grant ”Scheduling mechanisms for rail mounted gantries with regard to crane interdependencies” (PE 514/22-1).

References Bartels, J.-H., & Zimmermann, J. (2009). Scheduling tests in automotive R&D projects. European Journal of Operational Research, 193(3), 805–819. Blazewicz, J., Ecker, K., Pesch, E., Schmidt, G., & Weglarz, J. (2007). Handbook on scheduling. Berlin: Springer. Boysen, N. (2010). Truck scheduling at zero-inventory crossdocking terminals. Computers and Operations Research, 37, 32–41. Boysen, N., & Fliedner, M. (2010). Cross dock scheduling: Classification, literature review and research agenda. Omega, 38, 413–422. Boysen, N., Fliedner, M., & Scholl, A. (2010). Scheduling inbound and outbound trucks at cross docking terminals. OR Spectrum, 32, 135–161. Briskorn, D., Jaehn, F., & Pesch, E. (2013). Exact algorithms for inventory constrained scheduling on a single machine. Journal of Scheduling, 16, 105–115. Briskorn, D., & Leung, J. (2013). Minimizing maximum lateness of jobs in inventory constrained scheduling. Journal of the Operational Research Society, 64, 1851–1864. Briskorn, D., Choi, B.-C., Lee, K., Leung, J., & Pinedo, M. (2010). Complexity of single machine scheduling subject to nonnegative inventory constraints. European Journal of Operational Research, 207(2), 605–619. Chen, F., & Lee, C.-Y. (2009). Minimizing the makespan in a twomachine cross-docking flow shop problem. European Journal of Operational Research, 193, 5972. Chen, F., & Song, K. (2009). Minimizing makespan in two-stage hybrid cross docking scheduling problem. Computers and Operations Research, 36, 2066–2073. Chen, J.-S. (2008). Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan. European Journal of Operational Research, 190, 90–102.

J Sched Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimisation and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326. Kononov, A., & Lin, B. M.-T. (2010). Minimizing the total weighted completion time in the relocation problem. Journal of Scheduling, 13, 123–129. Lee, C.-Y. (2004). Machine scheduling with availability constraints. In J. Y.-T. Leung (Ed.), Handbook of scheduling: Algorithms, models and performance analysis (pp. 22.1–22.13). Boca Raton, FL: CRC Press. McWilliams, D. L., Stanfield, P. M., & Geiger, C. D. (2005). The parcel hub scheduling problem: A simulation-based solution approach. Computers and Industrial Engineering, 49, 393–412. Miao, Z., Lim, A., & Ma, H. (2009). Truck dock assignment with operational time constraint within crossdocks. European Journal of Operational Research, 192(1), 105–115. Mosheiov, G., & Sarig, A. (2009). Scheduling a maintenance activity and due-window assignment on a single machine. Computers and Operations Research, 36, 2541–2545. Neumann, K., & Schwindt, C. (2002). Project scheduling with inventory constraints. Mathematical Methods of Operations Research, 56, 513–533.

Neumann, K., Schwindt, C., & Trautmann, N. (2005). Scheduling of continuous and discontinuous material flows with intermediate storage restrictions. European Journal of Operational Research, 165, 495–509. Pinedo, M. (2008). Scheduling: Theory, algorithms, and systems. Berlin: Springer. Schwindt, C., & Trautmann, N. (2000). Batch scheduling in process industries: An application of resource-constrained project scheduling. OR-Spektrum, 22(4), 501–524. Sun, K., & Li, H. (2010). Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines. International Journal of Production Economics, 124, 151–158. Yu, W., & Egbelu, P. J. (2008). Scheduling of inbound and outbound trucks in cross docking systems with temporary storage. European Journal of Operational Research, 184, 377–396. Zhao, C.-L., & Tang, H.-Y. (2010). Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan. Applied Mathematical Modelling, 34, 837– 841.

123