A technical note: fully polynomial time approximation schemes for minimizing the makespan of deteriorating jobs with non
- PDF / 294,115 Bytes
- 6 Pages / 595.276 x 790.866 pts Page_size
- 97 Downloads / 199 Views
A technical note: fully polynomial time approximation schemes for minimizing the makespan of deteriorating jobs with nonlinear processing times Nir Halman1
© Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract Fully polynomial time approximation schemes for scheduling deteriorating jobs with nonlinear processing times on a single machine are given via an application of the K -approximation sets and functions technique. Keywords Dynamic scheduling · FPTAS · K -approximation sets and functions
1 Introduction Time-dependent scheduling relates to machine scheduling problems wherein jobs can deteriorate (or shorten) as they await service, causing their processing times to grow (or shrink) while they wait (Gawiejnowicz 2008). In such a model, the actual processing times are functions of the scheduling policy. This model is applicable in real-world situations, such as firefighting, food processing, crop harvest, snow removal, chemical and metallurgical processes, and hospital emergency ward scheduling. More recent applications of this model reported in the literature include computer-assisted production planning of continuously moving assembly lines (Sedding 2018) and scheduling of telescope observations, see Fontan et al. (2018) and the references therein. Formally, there are n independent jobs that need to be processed by a single machine without preemption. Each job J j has basic processing time p j , j = 1, . . . , n. The jobs have a given common critical date d after which they start to deteriorate and a common maximum deterioration date D (D > d) after which they deteriorate no further. The actual processing time a j (t) of J j depends on its start time t in the following way: a j (t) =
B 1
pj, p j + w j (min{t, D} − d),
if t ≤ d, otherwise,
Nir Halman [email protected] Hebrew University of Jerusalem, Jerusalem, Israel
where w j ≥ 0 is the deterioration rate of J j . If D < ∞, the deterioration is called bounded, which is the case handled by Kovalyov and Kubiak (2012). If D = ∞, as the case studied by Cai et al. (1998) and Kovalyov and Kubiak (1998), the deterioration is called unbounded. We assume that d, D, and all p j and w j are integral for j = 1, . . . , n. Let pmax = max j { p j } and wmax = max j {w j }. If we set L = max{ pmax , wmax , D} (or L = max{ pmax , wmax , d} in the unbounded case) to be the largest numerical parameter in the input, then the problem (binary) size is O(n log L). The problem is to schedule the jobs to minimize the makespan, i.e., the completion time of the last job in the schedule. Following the notation in Kovalyov and Kubiak (1998, 2012), we shall denote this problem by Det. We shall assume that n j=1 p j > d (and therefore d < npmax ). Otherwise all jobs can start by d, and the problem becomes trivial. Furthermore, it is easy to realize that there is no machine idle time in any optimal schedule. Kubiak and van de Velde (1998, Theorem 1) show that the unbounded case is NP-hard in the ordinary sense by a reduction from PARTITION. Since in the unbou
Data Loading...
