Minimizing the number of late jobs in a stochastic setting using a chance constraint

We consider the single-machine scheduling problem of minimizing the number of late jobs. We omit here one of the standard assumptions in scheduling theory, which is that the processing times are deterministic. In this scheduling environment, the completion times will be stochastic variables as well. Instead of looking at the expected number of on time jobs, we present a new model to deal with the stochastic completion times, which is based on using a chance constraint to define whether a job is on time or late: a job is on time if the probability that it is completed by the deterministic due date is at least equal to a certain given minimum success probability. We have studied this problem for four classes of stochastic processing times. The jobs in the first three classes have processing times that follow: (i) A gamma distribution with shape parameter p _j and scale parameter β, where β is common to all jobs; (ii) A negative binomial distribution with parameters p _j and r, where r is the same for each job; (iii) A normal distribution with parameters p _j and σ _j ². The jobs in the fourth class have equally disturbed processing times, that is, the processing times consist of a deterministic part and a random component that is independently, identically distributed for each job. We show that the first two cases have a common characteristic that makes it possible to solve these problems in O(nlog n) time through the algorithm by Moore and Hodgson. To analyze the third and fourth problem we need the additional assumption that the due dates and the minimum success probabilities are agreeable. We show that under this assumption the third problem is -hard in the ordinary sense, whereas the fourth problem is solvable by Moore and Hodgson’s algorithm. We further indicate how the problem of maximizing the expected number of on time jobs (with respect to the standard definition) can be tackled if we add the constraint that the on time jobs are sequenced in a given order and when we require that the probability that a job is on time amounts to at least some given lower bound. Supported by EC Contract IST-1999-14186 (Project alcom-FT).     

Operator scheduling in data stream systems

In many applications involving continuous data streams, data arrival is bursty and data rate fluctuates over time. Systems that seek to give rapid or real-time query responses in such an environment must be prepared to deal gracefully with bursts in data arrival without compromising system performance. We discuss one strategy for processing bursty streams - adaptive, load-aware scheduling of query operators to minimize resource consumption during times of peak load. We show that the choice of an operator scheduling strategy can have significant impact on the runtime system memory usage as well as output latency. Our aim is to design a scheduling strategy that minimizes the maximum runtime system memory while maintaining the output latency within prespecified bounds. We first present Chain scheduling, an operator scheduling strategy for data stream systems that is near-optimal in minimizing runtime memory usage for any collection of single-stream queries involving selections, projections, and foreign-key joins with stored relations. Chain scheduling also performs well for queries with sliding-window joins over multiple streams and multiple queries of the above types. However, during bursts in input streams, when there is a buildup of unprocessed tuples, Chain scheduling may lead to high output latency. We study the online problem of minimizing maximum runtime memory, subject to a constraint on maximum latency. We present preliminary observations, negative results, and heuristics for this problem. A thorough experimental evaluation is provided where we demonstrate the potential benefits of Chain scheduling and its different variants, compare it with competing scheduling strategies, and validate our analytical conclusions.Received: 18 October 2003, Accepted: 16 April 2004, Published online: 14 September 2004Edited by: J. Gehrke and J. HellersteinBrian Babcock: Supported in part by a Rambus Corporation Stanford Graduate Fellowship and NSF Grant IIS-0118173.Shivnath Babu: Supported in part by NSF Grants IIS-0118173 and IIS-9817799.Mayur Datar: Supported in part by Siebel Scholarship and NSF Grant IIS-0118173.Rajeev Motwani: Supported in part by NSF Grant IIS-0118173, an Okawa Foundation Research Grant, an SNRC grant, and grants from Microsoft and Veritas.Dilys Thomas: Supported by NSF Grant EIA-0137761 and NSF ITR Award Number 0331640.     

Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains

We study a supply chain scheduling problem in which n jobs have to be scheduled on a single machine and delivered to m customers in batches. Each job has a due date, a processing time and a lateness penalty (weight). To save batch-delivery costs, several jobs for the same customer can be delivered together in a batch, including late jobs. The completion time of each job in the same batch coincides with the batch completion time. A batch setup time has to be added before processing the first job in each batch. The objective is to find a schedule which minimizes the sum of the weighted number of late jobs and the delivery costs. We present a pseudo-polynomial algorithm for a restricted case, where late jobs are delivered separately, and show that it becomes polynomial for the special cases when jobs have equal weights and equal delivery costs or equal processing times and equal setup times. We convert the algorithm into an FPTAS and prove that the solution produced by it is near-optimal for the original general problem by performing a parametric analysis of its performance ratio.     

Makespan minimization with OR-precedence constraints

We consider a variant of the NP-hard problem of assigning jobs to machines to minimize the completion time of the last job. Usually, precedence constraints are given by a partial order on the set of jobs, and each job requires all its predecessors to be completed before it can start. In this paper, we consider a different type of precedence relation that has not been discussed as extensively and is called OR-precedence. In order for a job to start, we require that at least one of its predecessors is completed—in contrast to all its predecessors. Additionally, we assume that each job has a release date before which it must not start. We prove that a simple List Scheduling algorithm due to Graham (Bell Syst Tech J 45(9):1563–1581, 1966) has an approximation guarantee of 2 and show that obtaining an approximation factor of \(4/3 - \varepsilon \) is NP-hard. Further, we present a polynomial-time algorithm that solves the problem to optimality if preemptions are allowed. The latter result is in contrast to classical precedence constraints where the preemptive variant is already NP-hard. Our algorithm generalizes previous results for unit processing time jobs subject to OR-precedence constraints, but without release dates. The running time of our algorithm is \(O(n^2)\) for arbitrary processing times and it can be reduced to O(n) for unit processing times, where n is the number of jobs. The performance guarantees presented here match the best-known ones for special cases where classical precedence constraints and OR-precedence constraints coincide.

     

Ideal preemptive schedules on two processors

An ideal schedule minimizes both makespan and total flow time. It is known that the Coffman-Graham algorithm [Acta Informatica 1, 200-213, 1972] solves in polynomial time the problem of finding an ideal nonpreemptive schedule of unit-execution-time jobs with equal release dates and arbitrary precedence constraints on two identical parallel processors. This paper presents an extension of the algorithm that solves in polynomial time the preemptive counterpart of this problem. The complexity status of the preemptive problem of minimizing just the total flow time has been open.Received: 2 May 2003, J. Sethuraman: Research supported by an NSF CAREER Award DMI-0093981 and an IBM Faculty Partnership Award.     

Competitive Analysis of Scheduling Algorithms for Aggregated Links

We study an online job scheduling problem arising in networks with aggregated links. The goal is to schedule n jobs, divided into k disjoint chains, on m identical machines, without preemption, so that the jobs within each chain complete in the order of release times and the maximum flow time is minimized. We present a deterministic online algorithm with competitive ratio , and show a matching lower bound, even for randomized algorithms. The performance bound for we derive in the paper is, in fact, more subtle than a standard competitive ratio bound, and it shows that in overload conditions (when many jobs are released in a short amount of time), ’s performance is close to the optimum. We also show how to compute an offline solution efficiently for k=1, and that minimizing the maximum flow time for k,m≥2 is -hard. As by-products of our method, we obtain two offline polynomial-time algorithms for minimizing makespan: an optimal algorithm for k=1, and a 2-approximation algorithm for any k. W. Jawor and M. Chrobak supported by NSF grants OISE-0340752 and CCR-0208856. Work of C. Dürr conducted while being affiliated with the Laboratoire de Recherche en Informatique, Université Paris-Sud, 91405 Orsay. Supported by the CNRS/NSF grant 17171 and ANR Alpage.     

Scheduling a Single Server in a Two-machine Flow Shop

We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem. This result enables several cases of the server scheduling problem to be solved in O(n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup times are equal and there are two distinct due dates. This problem is solved in O(n ³) time when all job processing times on the first machine are equal, and it is solved in O(n ⁴) time when all processing times on the second machine are equal. Received November 20, 2001; revised October 18, 2002 Published online: January 16, 2003     

Optimal control of a class of DEDS: Flow-shops with state-dependent processing times

We consider a permutation flow-shop withn jobs andm machines, where the job processing times are given by a monotone nondecreasing function of the time elapsed since the release of the jobs. In this class of discrete event dynamic systems (DEDS), the dynamics is bothevent dependent, andtime dependent. Unless processing times are constant, it cannot be linearized using the (max, +) algebra. In order to schedule the jobs, we first need to know how to compute the (optimal) value of each schedule, i.e., when the jobs should be released. This optimal control problem is solved here by proving apredictive feedback control law, which holds for any regular performance criterion. Then we derive aBellman principle for this type of DEDS, and prove closed form control formulas for the minimum of: the makespan (C _max), the maximum lateness (L _max), and the maximum tardiness (T _max). We also prove some minimax theorems for a class of nonconvex maps derived from the dynamics of the system. The optimal control problem is solved in polynomial time, provided the inverse of the processing time functions can be computed in polynomial time.Research supported by the M.E.S.S. Québec Actions Structurantes, F.C.A.R. 86CE-130, 89EQ3528, NRC grants OGP38915, OGP37148, the Belgian Program on Interuniversity Poles of Attraction, and the CNRS, France.     

Notes on Max Flow Time Minimization with Controllable Processing Times

In a scheduling problem with controllable processing times the job processing time can be compressed through incurring an additional cost. We consider the identical parallel machines max flow time minimization problem with controllable processing times. We address the preemptive and non-preemptive version of the problem. For the preemptive case, a linear programming formulation is presented which solves the problem optimally in polynomial time. For the non-preemptive problem it is shown that the First In First Out (FIFO) heuristic has a tight worst-case performance of 3–2/m, when jobs processing times and costs are set as in some optimal preemptive schedule. Supported by Swiss National Science Foundation project 20-63733.00/1, Resource Allocation and Scheduling in Flexible Manufacturing Systems, and by the Metaheuristics Network, grant HPRN-CT-1999-00106.     

Single machine batch scheduling problem with family setup times and release dates to minimize makespan

In this paper we consider the single machine batch scheduling problem with family setup times and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an time dynamic programming algorithm and an time dynamic programming algorithm for the problem, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the setup times of all the families and the processing times of all the jobs. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme (PTAS) for the problem.     

Scheduling jobs with equal processing times and time windows on identical parallel machines

We present a linear programming approach to the problem of scheduling equal processing time jobs with release dates and deadlines on identical parallel machines. The known algorithm with complexity O(n ³log log n) of B. Simons schedules all the jobs while minimizing both the maximum completion time and the mean flow time. Our approach permits also to minimize the weighted sum of completion times and total tardiness in polynomial time for the problems without deadlines. The complexity status of these problems was open. Contract/grant sponsor: Alexander von Humboldt Foundation.     

On scheduling a single machine with resource dependent release times

We consider a single machine scheduling problem with resource dependent release times that can be controlled by a non-increasing convex resource consumption function. The objective is to minimize the weighted total resource consumption and sum of job completion times with an initial release time greater than the total processing times. It is known that the problem is polynomially solvable in O(n⁴) with n the number of jobs.     

Online scheduling of bounded length jobs to maximize throughput

We consider an online scheduling problem, motivated by the issues present at the joints of networks using ATM and TCP/IP. Namely, IP packets have to be broken down into small ATM cells and sent out before their deadlines, but cells corresponding to different packets can be interwoven. More formally, we consider the online scheduling problem with preemptions, where each job j is revealed at release time r _j , and has processing time p _j , deadline?d _j , and weight w _j . A?preempted job can be resumed at any time. The goal is to maximize the total weight of all jobs completed on time. Our main results are as follows. Firstly, we prove that when the processing times of all jobs are at most k, the optimum deterministic competitive ratio is ??(k/log?k). Secondly, we give a deterministic algorithm with competitive ratio depending on the ratio between the smallest and the largest processing time of all jobs. In particular, it attains competitive ratio 5 in the case when all jobs have identical processing times, for which we give a lower bound of 2.598. The latter upper bound also yields an O(log?k)-competitive randomized algorithm for the variant with processing times bounded by k.     

Approximation schemes for the Min-Max Starting Time Problem

We consider the off-line scheduling problem of minimizing the maximal starting time. The input to this problem is a sequence of n jobs and m identical machines. The goal is to assign the jobs to the machines so that the first time at which all jobs have already started running is minimized, under the restriction that the processing of the jobs on any given machine must respect their original order. Our main result is a polynomial time approximation scheme (PTAS) for this problem in the case where m is considered as part of the input. As the input to this problem is a sequence of jobs, rather than a set of jobs where the order is insignificant, we present techniques that are designed to handle order constraints imposed by the sequence. Those techniques are combined with common techniques of assignment problems in order to yield a PTAS for this problem. We also show that when m is a constant, the problem admits a fully polynomial time approximation scheme. Finally, we show that the makespan problem in the linear hierarchical model may be reduced to the min-max starting time problem, thus concluding that the former problem also admits a PTAS.Received: 26 May 2003, Published online: 5 August 2004A preliminary version of this paper appeared in Proc. of 28th Mathematical Foundations of Computer Science (2003)...... Research supported in part by the Israel Science Foundation, (grant no. 250/01)     

Minimizing Makespan in Batch Machine Scheduling

We study the scheduling of a set of n jobs, each characterized by a release (arrival) time and a processing time, for a batch processing machine capable of running at most B jobs at a time. We obtain an O(n log n)-time algorithm when B is unbounded. When there are only m distinct release times and the inputs are integers, we obtain an O(n(BR_max)^m-1(2/m)^m-3)-time algorithm where R_max is the difference between the maximum and minimum release times. When there are k distinct processing times and m release times, we obtain an O(n log m + k^k+2 B^k+1 m² log m)-time algorithm. We obtain even better algorithms for m=2 and for k=1. These algorithms improve most of the corresponding previous algorithms for the respective special cases and lead to improved approximation schemes for the general problem.     

Efficient Approximation Schemes for Scheduling Problems with Release Dates and Delivery Times

We consider the problem of scheduling n independent jobs on m identical machines that operate in parallel. Each job must be processed without interruption for a given amount of time on any one of the m machines. In addition, each job has a release date, when it becomes available for processing, and, after completing its processing, requires an additional delivery time. The objective is to minimize the time by which all jobs are delivered. In the notation of Graham et al. (1979), this problem is noted P|r _j|L_max. We develop a polynomial time approximation scheme whose running time depends only linearly on n. This linear complexity bound gives a substantial improvement of the best previously known polynomial bound (Hall and Shmoys, 1989). Finally, we discuss the special case of this problem in which there is a single machine and present an improved approximation scheme.     

Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs

In this paper we study the problem of scheduling n jobs with release dates, due dates, weights, and equal processing times on a single machine. The objective is to minimize total weighted tardiness. We formulate the problem as a time-indexed ILP after which we solve the LP-relaxation. We show that for certain special cases (namely when either all due dates, all weights, or all release dates are equal, or when all due dates and release dates are equally ordered), the solution for the LP-relaxation is either integral or can be adjusted in polynomial time into an integral one. For the general case we present a branching rule that performs well. Furthermore we show that the same approach holds for the m identical, parallel machines variant of the problem. Finally we show that with a minor modification the same approach also holds for the single-machine problems of minimizing the sum of weighted late jobs (1|r _j ,p _j =p|∑w _j U _j ) and the sum of weighted late work (1|r _j ,p _j =p|∑w _j V _j ) as well as their respective variants with m identical, parallel machines. We further show how we can solve these problems by applying column generation when there is not sufficient memory available to apply the direct ILP-approach.     

Calibrations scheduling with arbitrary lengths and activation length

Bender et al. (SPAA 2013) proposed a theoretical framework for testing in contexts where safety mistakes must be avoided. Testing in such a context is made by machines that need to be calibrated on a regular basis. Since calibrations have a non-negligible cost, it is important to study policies minimizing the total calibration cost while performing all the necessary tests. We focus on the single-machine setting, and we study the complexity status of different variants of the problem. First, we extend the model by considering that the jobs have arbitrary processing times, and we propose an optimal polynomial-time algorithm when the preemption of jobs is allowed. Then, we study the case where there are many types of calibrations with their corresponding lengths and costs. We prove that the problem becomes NP-hard for arbitrary processing times even when the preemption of the jobs is allowed. Finally, we focus on the case of unit processing time jobs, and we show that a more general problem, where the recalibration of the machine is not instantaneous, can be solved in polynomial time via dynamic programming.

     

Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs

In this article, we consider a single machine scheduling problem with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the job processing time is defined by a function of its starting time and total normal processing time of jobs in front of it in the sequence. The objective is to determine an optimal schedule so as to minimize the total completion time. This problem remains open for the case of ?1?a?a denotes the learning index; we show that an optimal schedule of the problem is V-shaped with respect to job normal processing times. Three heuristic algorithms utilising the V-shaped property are proposed, and computational experiments show that the last heuristic algorithm performs effectively and efficiently in obtaining near-optimal solutions.     

Throughput maximization for speed scaling with agreeable deadlines

We study the following energy-efficient scheduling problem. We are given a set of n jobs which have to be scheduled by a single processor whose speed can be varied dynamically. Each job \(J_j\) is characterized by a processing requirement (work) \(p_j\), a release date \(r_j\), and a deadline \(d_j\). We are also given a budget of energy E which must not be exceeded and our objective is to maximize the throughput (i.e., the number of jobs which are completed on time). We show that the problem can be solved optimally via dynamic programming in \(O(n^4 \log n \log P)\) time when all jobs have the same release date, where P is the sum of the processing requirements of the jobs. For the more general case with agreeable deadlines where the jobs can be ordered so that, for every \(i < j\), it holds that \(r_i \le r_j\) and \(d_i \le d_j\), we propose an optimal dynamic programming algorithm which runs in \(O(n^6 \log n \log P)\) time. In addition, we consider the weighted case where every job \(J_j\) is also associated with a weight \(w_j\) and we are interested in maximizing the weighted throughput (i.e., the total weight of the jobs which are completed on time). For this case, we show that the problem becomes \(\mathcal{NP}\)-hard in the ordinary sense even when all jobs have the same release date and we propose a pseudo-polynomial time algorithm for agreeable instances.