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.     

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     

Scheduling stochastic jobs with asymmetric earliness and tardiness penalties

We consider a stochastic counterpart of the well-known earliness-tardiness scheduling problem with a common due date, in which n stochastic jobs are to be processed on a single machine. The processing times of the jobs are independent and normally distributed random variables with known means and known variances that are proportional to the means. The due dates of the jobs are random variables following a common probability distribution. The objective is to minimize the expectation of a weighted combination of the earliness penalty, the tardiness penalty, and the flow-time penalty. One of our main results is that an optimal sequence for the problem must be V-shaped with respect to the mean processing times. Other characterizations of the optimal solution are also established. Two algorithms are proposed, which can generate optimal or near-optimal solutions in pseudopolynomial time. The proposed algorithms are also extended to problems where processing times do not satisfy the assumption in the model above, and are evaluated when processing times follow different probability distributions, including general normal (without the proportional relation between variances and means), uniform, Laplace, and exponential. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44, 531–557, 1997.     

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     

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     

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.     

Simultaneous optimization of efficiency and performance balance measures in single-machine scheduling problems

Manufacturing and service organizations routinely face the challenge of scheduling jobs, orders, or individual customers in a schedule that optimizes either (i) an aggregate efficiency measure, (ii) a measure of performance balance, or (iii) some combination of these two objectives. We address these questions for single-machine job scheduling systems with fixed or controllable due dates. We show that a large class of such problems can be optimized by solving either a single instance or a finite sequence of instances of the so-called (SQC) problem, in which the sum of general quasiconvex functions of the jobs' completion times is to be minimized. To solve a single instance of (SQC), we develop an efficient, though pseudopolynomial algorithm, based on dynamic programming. The algorithm generates a solution that is optimal among all schedules whose starting time is restricted to the points of a prespecified (arbitrary) grid. The algorithm is embedded in an iterative procedure, where in each iteration a specific instance of (SQC) is solved. Special attention is given to the simultaneous minimization of the mean and variance of completion times. © 1993 John Wiley & Sons, Inc.     

Note: “Simultaneous optimization of efficiency and performance balance measures in single-machine scheduling problems”

n independent jobs are to be scheduled nonpreemptively on a single machine so as to minimize some performance measure. Federgruen and Mosheiov [2] show that a large class of such scheduling problems can be optimized by solving either a single instance or a finite sequence of instances of the so-called SQC problem, in which all the jobs have a fixed or controllable common due date and the sum of general quasiconvex functions of the job completion times is to be minimized. In this note we point out that this is not always true. In particular, we show that the algorithm proposed in [2] does not always find a global optimal schedule to the problem of minimizing the weighted sum of the mean and variance of job completion times. © 1996 John Wiley & Sons, Inc.     

Integrated production scheduling and preventive maintenance planning for a single machine under a cumulative damage failure process

This paper finds the optimal integrated production schedule and preventive maintenance plan for a single machine exposed under a cumulative damage process, and investigates how the optimal preventive maintenance plan interacts with the optimal production schedule. The goal is to minimize the total tardiness. The optimal policy possesses the following properties: Under arbitrary maintenance plan when jobs have common processing time, and different due dates, the optimal production schedule is to order the jobs by earliest due date first rule; and when jobs have common due date and different processing times, the optimal production schedule is shortest processing time first. The optimal maintenance plan is of control limit type under any arbitrary production schedule when machine is exposed under a cumulative damage failure process. Numerical studies on the optimal maintenance control limit of the maintenance plan indicate that as the number of jobs to be scheduled increases, the effect of jobs due dates on the optimal maintenance control limit diminishes. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Evaluating the effects of machine breakdowns in stochastic scheduling problems

In most of the stochastic resource-allocation problems discussed in the literature it is supposed that the key resource, herein called the machine, is continuously available until all tasks are completed. Plainly, this will often be an unrealistic assumption. This paper supposes that intermittent availability of the machine is due to a breakdown proces, and describes various approaches to the evaluation of the effect of breakdowns. Firstly, for the case of geometric up times, conditions are given under which breakdowns have no effect on optimal allocation strategies. Secondly, two different procedures are given which yield an upper bound on the loss incurred when a processing strategy is adopted under the assumption of no breakdowns, when in fact breakdowns do occur. The first of these is based on Gittins's indices and is described for the case of geometric up times, and the second uses a bounding argument on the breakdown process.     

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.     

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     

Minimizing mean absolute deviation of completion times about a common due date

We consider a single machine scheduling problem in which the objective is to minimize the mean absolute deviation of job completion times about a common due date. We present an algorithm for determining multiple optimal schedules under restrictive assumptions about the due date, and an implicit enumeration procedure when the assumptions do not hold. We also establish the similarity of this problem to the two parallel machines mean flow time problem.     

Scheduling about a large common due date with tolerance to minimize mean absolute deviation of completion times

In this article the problem of minimizing the mean absolute deviation (MAD) of job completion times about an unrestricted given common due date with tolerance in the n-job, single-machine scheduling environment is considered. We describe some optimality conditions and show that the unrestricted version of the MAD problem with an arbitrary due date tolerance is polynomial by proposing a polynomial-time algorithm for identifying an optimal schedule. © 1994 John Wiley & Sons, Inc.     

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.     

Dynamic lot‐sizing model with production time windows

We consider a dynamic lot‐sizing model with production time windows where each of n demands has earliest and latest production due dates and it must be satisfied during the given time window. For the case of nonspeculative cost structure, an O(nlogn) time procedure is developed and it is shown to run in O(n) when demands come in the order of latest production due dates. When the cost structure is somewhat general fixed plus linear that allows speculative motive, an optimal procedure with O(T⁴) is proposed where T is the length of a planning horizon. Finally, for the most general concave production cost structure, an optimal procedure with O(T⁵) is designed. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Lower bounds for single-machine scheduling problems

This article addresses deterministic, nonpreemptive scheduling of n jobs with unequal release times on a single machine to minimize the sum of job completion times. This problem is known to be NP-hard. The article compares six available lower bounds in the literature and shows that the lower bound based on the optimal solution to the preemptive version of the problem is the dominant lower bound.     

Optimization of schedule stability and efficiency under processing time variability and random machine breakdowns in a job shop environment

The ability to cope with uncertainty in dynamic scheduling environments is becoming an increasingly important issue. In such environments, any disruption in the production schedule will translate into a disturbance of the plans for several external activities as well. Hence, from a practical point of view, deviations between the planned and realized schedules are to be avoided as much as possible. The term stability refers to this concern. We propose a proactive approach to generate efficient and stable schedules for a job shop subject to processing time variability and random machine breakdowns. In our approach, efficiency is measured by the makespan, and the stability measure is the sum of the variances of the realized completion times. Because the calculation of the original measure is mathematically intractable, we develop a surrogate stability measure. The version of the problem with the surrogate stability measure is proven to be NP‐hard, even without machine breakdowns; a branch‐and‐bound algorithm is developed for this problem variant. A tabu search algorithm is proposed to handle larger instances of the problem with machine breakdowns. The results of extensive computational experiments indicate that the proposed algorithms are quite promising in performance. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Proactive release procedures for just‐in‐time job shop environments,subject to machine failures

In this paper, we consider just‐in‐time job shop environments (job shop problems with an objective of minimizing the sum of tardiness and inventory costs), subject to uncertainty due to machine failures. We present techniques for proactive uncertainty management that exploit prior knowledge of uncertainty to build competitive release dates, whose execution improves performance. These techniques determine the release dates of different jobs based on measures of shop load, statistical data of machine failures, and repairs with a tradeoff between inventory and tardiness costs. Empirical results show that our methodology is very promising in comparison with simulated annealing and the best of 39 combinations of dispatch rules & release policies, under different frequencies of breakdowns. We observe that the performance of the proactive technique compared to the other two approaches improves in schedule quality (maximizing delivery performance while minimizing costs) with increase in frequency of breakdowns. The proactive technique presented here is also computationally less expensive than the other two approaches. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times

This paper deals with flowshop/sum of completion times scheduling problems, working under a “no-idle” or a “no-wait” constraint, the former prescribes for the machines to work continuously without idle intervals and the latter for the jobs to be processed continuously without waiting times between consecutive machines. Under either of the constraints the problem is unary NP-Complete for two machines. We prove some properties of the optimal schedule for n/2/F, no-idle/σC_i. For n/m/P, no-idle/σC_i, and n/m/P, no-wait/σC_i, with an increasing or decreasing series of dominating machines, we prove theorems that are the basis for polynomial bounded algorithms. All theorems are demonstrated numerically.