Approximation algorithms for inventory constrained scheduling on a single machineby Ehab Morsy, Erwin Pesch

Journal of Scheduling



A 1.47-approximation algorithm for a preemptive single-machine scheduling problem

Michel X. Goemans, Joel M. Wein, David P. Williamson

A Genetic Algorithm with Dominance Properties for Single Machine Scheduling Problems

Shih-Shin Chen, Pei-Chann Chang, Shih-Min Hsiung, Chin-Yuan Fan

Approximation Algorithms for Average Stretch Scheduling

Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman


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 singlemachine 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 problemwhich 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

Erwin Pesch 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 paperwe 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 , itsweightw j , and its inventorymodification δ j . The processing time p j of job j is the total time j uses themachine 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 single machine, there is no relevant difference between these models.