A single-machine scheduling problem with random processing times

We consider the problem of scheduling n jobs with random processing times on a single machine in order to minimize the expected variance of the completion times. We prove a number of results, including one to the effect that the optimal schedule must be V shaped when the jobs have identical means or variances or have exponential processing times.     

Stochastic scheduling subject to machine breakdowns: The preemptive‐repeat model with discounted reward and other criteria

We consider the problem of scheduling a set of jobs on a single machine subject to random breakdowns. We focus on the preemptive‐repeat model, which addresses the situation where, if a machine breaks down during the processing of a job, the work done on the job prior to the breakdown is lost and the job will have to be started from the beginning again when the machine resumes its work. We allow that (i) the uptimes and downtimes of the machine follow general probability distributions, (ii) the breakdown process of the machine depends upon the job being processed, (iii) the processing times of the jobs are random variables following arbitrary distributions, and (iv) after a breakdown, the processing time of a job may either remain a same but unknown amount, or be resampled according to its probability distribution. We first derive the optimal policy for a class of problems under the criterion to maximize the expected discounted reward earned from completing all jobs. The result is then applied to further obtain the optimal policies for other due date‐related criteria. We also discuss a method to compute the moments and probability distributions of job completion times by using their Laplace transforms, which can convert a general stochastic scheduling problem to its deterministic equivalent. The weighted squared flowtime problem and the maintenance checkup and repair problem are analyzed as applications. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

A generalized Johnson's rule for stochastic assembly systems

Johnson's rule gives the optimal order to schedule a set of jobs through a two-machine flow shop with deterministic processing times. We extend Johnson's rule to fork-join systems with random processing times. Most of the system may be an arbitrary network. We give conditions under which Johnson's rule is optimal in the stochastic sense, in the increasing convex sense, and in expected value. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 211–220, 1997     

Scheduling jobs with random processing times on a single machine subject to stochastic breakdowns to minimize early-tardy penalties

We examine the problem of scheduling n jobs with a common due date on a single machine. The processing time of each job is a random variable, which follows an arbitrary distribution with a known mean and a known variance. The machine is not reliable; it is subject to stochastic breakdowns. The objective is to minimize the expected sum of squared deviations of job completion times from the due date. Two versions of the problem are addressed. In the first one the due date is a given constant, whereas in the second one the due date is a decision variable. In each case, a general form of the deterministic equivalent of the stochastic scheduling problem is obtained when the counting process related to the machine uptime distribution is a generalized Poisson process. A sufficient condition is derived under which optimal sequences are V-shaped with respect to mean processing times. Other characterizations of optimal solutions are also established. Based on the optimality properties, algorithms with pseudopolynomial time complexity are proposed to solve both versions of the problem. © 1996 John Wiley & Sons, Inc.     

Minimization of expected variance of completion times on single machine for stochastic jobs

This article deals with the problem of scheduling jobs with random processing times on single machine in order to minimize the expected variance of job completion times. Sufficient conditions for the existence of V-shaped optimal sequences are derived separately for general and ordered job processing times. It is shown that when coefficient of variation of random processing times are bounded by a certain value, an optimal sequence is V-shaped. © 1997 John Wiley & Sons, Inc.     

Single-machine scheduling of stochastic jobs subject to deterioration or delay

N jobs are available for processing by a single machine. Jobs make (stochastic) progress while being processed but deteriorate while awaiting processing. The pioneering work of Browne and Yechiali, who developed scheduling policies for such models, is extended (i) to incorporate a precedence relation on the job set, delimiting the class of admissible policies, and (ii) to preemptive scheduling models. For the latter, we demonstrate that under appropriate conditions there is an optimal policy which is nonpreemptive. This is also achieved for a class of preemptive models in which processing generates delays for waiting jobs. A single class of algorithms is shown to generate optimal policies for many of the problems considered. © 1992 John Wiley & Sons, Inc.     

A bicriterion approach to common flow allowances due window assignment and scheduling with controllable processing times

We investigate a single‐machine scheduling problem for which both the job processing times and due windows are decision variables to be determined by the decision maker. The job processing times are controllable as a linear or convex function of the amount of a common continuously divisible resource allocated to the jobs, where the resource allocated to the jobs can be used in discrete or continuous quantities. We use the common flow allowances due window assignment method to assign due windows to the jobs. We consider two performance criteria: (i) the total weighted number of early and tardy jobs plus the weighted due window assignment cost, and (ii) the resource consumption cost. For each resource consumption function, the objective is to minimize the first criterion, while keeping the value of the second criterion no greater than a given limit. We analyze the computational complexity, devise pseudo‐polynomial dynamic programming solution algorithms, and provide fully polynomial‐time approximation schemes and an enhanced volume algorithm to find high‐quality solutions quickly for the considered problems. We conduct extensive numerical studies to assess the performance of the algorithms. The computational results show that the proposed algorithms are very efficient in finding optimal or near‐optimal solutions. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 41–63, 2017     

CON/SLK due date assignment and scheduling on a single machine with two agents

We consider scheduling problems involving two agents (agents A and B), each having a set of jobs that compete for the use of a common machine to process their respective jobs. The due dates of the A‐jobs are decision variables, which are determined by using the common (CON) or slack (SLK) due date assignment methods. Each agent wants to minimize a certain performance criterion depending on the completion times of its jobs only. Under each due date assignment method, the criterion of agent A is always the same, namely an integrated criterion consisting of the due date assignment cost and the weighted number of tardy jobs. Several different criteria are considered for agent B, including the maxima of regular functions (associated with each job), the total (weighted) completion time, and the weighted number of tardy jobs. The overall objective is to minimize the performance criterion of agent A, while keeping the objective value of agent B no greater than a given limit. We analyze the computational complexity, and devise polynomial or pseudo‐polynomial dynamic programming algorithms for the considered problems. We also convert, if viable, any of the devised pseudopolynomial dynamic programming algorithms into a fully polynomial‐time approximation scheme. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 416–429, 2016     

On‐line algorithms for minimizing makespan on batch processing machines

We consider problem of scheduling jobs on‐line on batch processing machines with dynamic job arrivals to minimize makespan. A batch machine can handle up to B jobs simultaneously. The jobs that are processed together from a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time becomes known upon its arrival. In the first part of this paper, we address the single batch processing machine scheduling problem. First we deal with two variants: the unbounded model where B is sufficiently large and the bounded model where jobs have two distinct arrival times. For both variants, we provide on‐line algorithms with worst‐case ratio (the inverse of the Golden ratio) and prove that these results are the best possible. Furthermore, we generalize our algorithms to the general case and show a worst‐case ratio of 2. We then consider the unbounded case for parallel batch processing machine scheduling. Lower bound are given, and two on‐line algorithms are presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 241–258, 2001     

Probabilistic analysis of an asymptotically optimal solution for the completion time variance problem

Scheduling a set of n jobs on a single machine so as to minimize the completion time variance is a well‐known NP‐hard problem. In this paper, we propose a sequence, which can be constructed in O(n log n) time, as a solution for the problem. Our primary concern is to establish the asymptotical optimality of the sequence within the framework of probabilistic analysis. Our main result is that, when the processing times are randomly and independently drawn from the same uniform distribution, the sequence is asymptotically optimal in the sense that its relative error converges to zero in probability as n increases. Other theoretical results are also derived, including: (i) When the processing times follow a symmetric structure, the problem has 2^{⌊(n−1)/2⌋} optimal sequences, which include our proposed sequence and other heuristic sequences suggested in the literature; and (ii) when these 2^{⌊(n−1)/2⌋} sequences are used as approximate solutions for a general problem, our proposed sequence yields the best approximation (in an average sense) while another sequence, which is commonly believed to be a good approximation in the literature, is interestingly the worst. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 373–398, 1999     

Server scheduling on parallel dedicated machines with fixed job sequences

We consider server scheduling on parallel dedicated machines to minimize the makespan. Each job has a loading operation and a processing operation. The loading operation requires a server that serves all the jobs. Each machine has a given set of jobs to process, and the processing sequence is known and fixed. We design a polynomial‐time algorithm to solve the two‐machine case of the problem. When the number of machines is arbitrary, the problem becomes strongly NP‐hard even if all the jobs have the same processing length or all the loading operations require a unit time. We design two heuristic algorithms to treat the case where all the loading times are unit and analyze their performance.     

Optimal scheduling of reader—systems

We consider a reader—writer system consisting of a single server and a fixed number of jobs (or customers) belonging to two classes. Class one jobs are called readers and any number of them can be processed simultaneously. Class two jobs are called writers and they have to be processed one at a time. When a writer is being processed no other writer or readers can be processed. A fixed number of readers and writers are ready for processing at time 0. Their processing times are independent random variables. Each reader and writer has a fixed waiting cost rate. We find optimal scheduling rules that minimize the expected total waiting cost (expected total weighted flowtime). We consider both nonpreemptive and preemptive scheduling. The optimal nonpreemptive schedule is derived by a variation of the usual interchange argument, while the optimal schedule in the preemptive case is given by a Gittins index policy. These index policies continue to be optimal for systems in which new writers enter the system in a Poisson fashion. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 483–495, 1998     

Single batch machine scheduling with deliveries

We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time p_j and a size s_j. All jobs are available for processing at time 0. The batch machine has a capacity D. Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D. The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K. We assume that K = rD, where and r is an integer. The travel time of the vehicle is T; that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst‐case ratios in both cases. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 470–482, 2015     

Parallel machine scheduling: A probabilistic analysis

The minimum makespan of the general parallel machine scheduling problem with m machines and n jobs is studied. As for a number of other important combinatorial problems, the theory of empirical processes proves to be a very elegant and powerful tool for the probabilistic analysis of the solution value. It is used in this paper to derive a scheduling constant θ such that, for random processing times, the minimum makespan almost surely grows as θn when n goes to infinity. Moreover, a thorough probabilistic analysis is performed on the difference between the minimum makespan and θn. Explicit expressions for the scheduling constant are given for an arbitrary number of unrelated machines with identically distributed processing times (with an increasing failure rate), and for an arbitrary number of uniform machines and generally distributed processing times. © 1996 John Wiley & Sons, Inc.     

Batch scheduling with step‐deteriorating processing times to minimize flowtime

Both topics of batch scheduling and of scheduling deteriorating jobs have been very popular among researchers in the last two decades. In this article, we study a model combining these two topics. We consider a classical batch scheduling model with unit‐jobs and batch‐independent setup times, and a model of step‐deterioration of processing times. The objective function is minimum flowtime. The optimal solution of the relaxed version (allowing non‐integer batch sizes) is shown to have a unique structure consisting of two consecutive decreasing arithmetic sequences of batch sizes. We also introduce a simple and efficient rounding procedure that guarantees integer batch sizes. The entire solution procedure requires an effort of O(n) (where nis the number of jobs.) © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time

The problem of scheduling n jobs on m parallel machines is considered when the machines are subject to random breakdowns and job processing times are random variables. An objective function of mean flow time is developed for a general parallel machine system, and an expression of its expected value is derived. The problem is transformed into a deterministic unrelated parallel machine scheduling model with modified processing times when the number of breakdowns is modeled as a generalized Poisson process. © 1994 John Wiley & Sons, Inc.     

Scheduling jobs that are subject to failure propagation

A single machine is available to process a collection of stochastic tasks. Processing is interrupted when the machine breaks down. We introduce a new model of breakdowns that more realistically incorporates the effects that job processing may have on the machine. This failure propagation model is equivalent to a Bayesian formulation in which learning about breakdown rates occurs as jobs evolve. Optimal scheduling policies are described in terms of Gittins indices and these indices are characterised in two special cases. For example, we obtain conditions which ensure that an optimal policy will only preempt a job's processing either at its completion or at a machine breakdown. We also bound the value lost by simplistic modelling which ignores the learning phenomenon. © 1996 John Wiley & Sons, Inc.     

A dynamic,nonstationary inventory problem for a price/quantity setting firm

A dynamic and nonstationary model is formulated for a firm which attempts to minimize total expected costs over a finite planning horizon. The control variables are price and production. The price p and the demand ζ are linked through the relationship ζ = g(p) + η, where g(p) is the riskless demand curve and η is a random variable. The general model allows for proportional ordering costs, convex holding and stockout costs, downward sloping riskless demand curve, backlogging, partial backlogging, lost sales, partial spoilage of inventory, and two modes of collecting revenue. Sufficient conditions are developed for this problem to have an optimal policy which resembles the single critical number policy known from stochastic inventory theory. It is also shown what set of parameters will satisfy these sufficiency conditions.     

Scheduling maintenance and semiresumable jobs on a single machine

The majority of scheduling literature assumes that the machines are available at all times. In this paper, we study single machine scheduling problems where the machine maintenance must be performed within certain intervals and hence the machine is not available during the maintenance periods. We also assume that if a job is not processed to completion before the machine is stopped for maintenance, an additional setup is necessary when the processing is resumed. Our purpose is to schedule the maintenance and jobs to minimize some performance measures. The objective functions that we consider are minimizing the total weighted job completion times and minimizing the maximum lateness. In both cases, maintenance must be performed within a fixed period T, and the time for the maintenance is a decision variable. In this paper, we study two scenarios concerning the planning horizon. First, we show that, when the planning horizon is long in relation to T, the problem with either objective function is NP-complete, and we present pseudopolynomial time dynamic programming algorithms for both objective functions. In the second scenario, the planning horizon is short in relation to T. However, part of the period T may have elapsed before we schedule any jobs in this planning horizon, and the remaining time before the maintenance is shorter than the current planning horizon. Hence we must schedule one maintenance in this planning horizon. We show that the problem of minimizing the total weighted completion times in this scenario is NP-complete, while the shortest processing time (SPT) rule and the earliest due date (EDD) rule are optimal for the total completion time problem and the maximum lateness problem respectively. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 845–863, 1999     

Using stochastic programming to solve an outpatient appointment scheduling problem with random service and arrival times

We study a stochastic outpatient appointment scheduling problem (SOASP) in which we need to design a schedule and an adaptive rescheduling (i.e., resequencing or declining) policy for a set of patients. Each patient has a known type and associated probability distributions of random service duration and random arrival time. Finding a provably optimal solution to this problem requires solving a multistage stochastic mixed‐integer program (MSMIP) with a schedule optimization problem solved at each stage, determining the optimal rescheduling policy over the various random service durations and arrival times. In recognition that this MSMIP is intractable, we first consider a two‐stage model (TSM) that relaxes the nonanticipativity constraints of MSMIP and so yields a lower bound. Second, we derive a set of valid inequalities to strengthen and improve the solvability of the TSM formulation. Third, we obtain an upper bound for the MSMIP by solving the TSM under the feasible (and easily implementable) appointment order (AO) policy, which requires that patients are served in the order of their scheduled appointments, independent of their actual arrival times. Fourth, we propose a Monte Carlo approach to evaluate the relative gap between the MSMIP upper and lower bounds. Finally, in a series of numerical experiments, we show that these two bounds are very close in a wide range of SOASP instances, demonstrating the near‐optimality of the AO policy. We also identify parameter settings that result in a large gap in between these two bounds. Accordingly, we propose an alternative policy based on neighbor‐swapping. We demonstrate that this alternative policy leads to a much tighter upper bound and significantly shrinks the gap.