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     

Minimizing makespan on a single batch processing machine with nonidentical job sizes

We deal with the problem of minimizing makespan on a single batch processing machine. In this problem, each job has both processing time and size (capacity requirement). The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is just the processing time of the longest job in the batch. An approximation algorithm with worst‐case ratio 3/2 is given for the version where the processing times of large jobs (with sizes greater than 1/2) are not less than those of small jobs (with sizes not greater than 1/2). This result is the best possible unless P = NP. For the general case, we propose an approximation algorithm with worst‐case ratio 7/4. A number of heuristics by Uzosy are also analyzed and compared. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 226–240, 2001     

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.     

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     

链约束下加工时间恶化的Flow Shop排序问题

讨论作业具有线性加工时间,作业间具有链约束的两台处理机流水作业排序问题,目标函数为极小化完工时间。在作业加工时间简单线性恶化下,提出作业的非负开始和停止延迟恶化率,构造了满足约束条件的复合作业。在此基础上,给出作业间具有平行链约束的两台处理机流水作业排序问题的最优多项式算法。     

Makespan minimization in the two‐machine flowshop batch scheduling problem

In this paper we consider a practical scheduling problem commonly arising from batch production in a flexible manufacturing environment. Different part‐types are to be produced in a flexible manufacturing cell organized into a two‐stage production line. The jobs are processed in batches on the first machine, and the completion time of a job is defined as the completion time of the batch containing it. When processing of all jobs in a batch is completed on the first machine, the whole batch of jobs is transferred intact to the second machine. A constant setup time is incurred whenever a batch is formed on any machine. The tradeoff between the setup times and batch processing times gives rise to the batch composition decision. The problem is to find the optimal batch composition and the optimal schedule of the batches so that the makespan is minimized. The problem is shown to be strongly NP‐hard. We identify some special cases by introducing their corresponding solution methods. Heuristic algorithms are also proposed to derive approximate solutions. We conduct computational experiments to study the effectiveness of the proposed heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 128–144, 2000     

Flow‐shop batch scheduling with identical processing‐time jobs

In many practical situations of production scheduling, it is either necessary or recommended to group a large number of jobs into a relatively small number of batches. A decision needs to be made regarding both the batching (i.e., determining the number and the size of the batches) and the sequencing (of batches and of jobs within batches). A setup cost is incurred whenever a batch begins processing on a given machine. This paper focuses on batch scheduling of identical processing‐time jobs, and machine‐ and sequence‐independent setup times on an m‐machine flow‐shop. The objective is to find an allocation to batches and their schedule in order to minimize flow‐time. We introduce a surprising and nonintuitive solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost

In the last decade, there has been much progress in understanding scheduling problems in which selfish jobs aim to minimize their individual completion time. Most of this work has focused on makespan minimization as social objective. In contrast, we consider as social cost the total weighted completion time, that is, the sum of the agent costs, a standard definition of welfare in economics. In our setting, jobs are processed on restricted uniform parallel machines, where each machine has a speed and is only capable of processing a subset of jobs; a job's cost is its weighted completion time; and each machine sequences its jobs in weighted shortest processing time (WSPT) order. Whereas for the makespan social cost the price of anarchy is not bounded by a constant in most environments, we show that for our minsum social objective the price of anarchy is bounded above by a small constant, independent of the instance. Specifically, we show that the price of anarchy is exactly 2 for the class of unit jobs, unit speed instances where the finite processing time values define the edge set of a forest with the machines as nodes. For the general case of mixed job strategies and restricted uniform machines, we prove that the price of anarchy equals 4. From a classical machine scheduling perspective, our results establish the same constant performance guarantees for WSPT list scheduling. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

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     

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.     

Single machine sequencing with random processing times and random due-dates

A single machine scheduling problem in which both the processing times and due-dates of the jobs awaiting servicing are random variables is analyzed. It is proved that the properties of the shortest processing time rule and the due-date rule which are known for the deterministic situation also hold in the probabilistic environment when they are suitably, and reasonably, refined for this context.     

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.     

Order-preserving allocation of jobs to two machines

In this paper, we consider the problem of minimizing the mean flow time of jobs to be processed on two machines. The jobs have a predetermined order, perhaps reflecting the order of arrival, and each job has a known processing time. We wish to assign the jobs to machines so as to minimize the mean flow time, with the constraint that the original order must be preserved within the subset of jobs assigned to each machine. An efficient algorithm based on dynamic programming is developed.     

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.     

Optimal timing schedules in earliness-tardiness single machine sequencing

The article deals with a single machine earliness-tardiness scheduling model where idle times are permitted in job processing. Based on a cluster concept we develop properties of the model that lead to a very fast algorithm to find an optimal timing schedule for a given sequence of jobs. The performance of this algorithm is tested on 480 randomly generated problems involving 100, 200, 400 and 500 jobs. It takes less than two seconds to solve a 500 job problem on a PC. © 1995 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.     

On n/1/F̄ dynamic deterministic problems

We consider sequencing of n jobs which will arrive intermittently and are to be processed on a single machine; the arrival and the processing times of each jobs are assumed known. A schedule is to be developed that minimizes the mean flow time. Two models are considered: (i) when no pre-emption or inserted idle time is allowed in the schedule, and (ii) when pre-emption is allowed but the jobs follow a pre-empt-repeat discipline We illustrate that Cobham's and Phipp's SPT dispatching rule does not guarantee the optimum F? even for the non-preemptive model We propose a branch and bound algorithm for both models and discuss our computational experience We also examine the relative performances of the optimum nonpre-emptive sequence, and the optimum pre-empt-repeat sequence over that resulting from SPT dispatching rule on a large number of sets of jobs of varying sizes and tightness.     

Scheduling jobs and maintenance activities on parallel machines

Most machine scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines need to be maintained and hence may become unavailable during certain periods. In this paper, we study the problem of processing a set of n jobs on m parallel machines where each machine must be maintained once during the planning horizon. Our objective is to schedule jobs and maintenance activities so that the total weighted completion time of jobs is minimized. Two cases are studied in this paper. In the first case, there are sufficient resources so that different machines can be maintained simultaneously if necessary. In the second case, only one machine can be maintained at any given time. In this paper, we first show that, even when all jobs have the same weight, both cases of the problem are NP-hard. We then propose branch and bound algorithms based on the column generation approach for solving both cases of the problem. Our algorithms are capable of optimally solving medium sized problems within a reasonable computational time. We note that the general problem where at most j machines, 1 ≤ j ≤ m, can be maintained simultaneously, can be solved similarly by the column generation approach proposed in this paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 145–165, 2000     

Machine scheduling with an availability constraint and job delivery coordination

In this paper we study the scheduling problem that considers both production and job delivery at the same time with machine availability considerations. Only one vehicle is available to deliver jobs in a fixed transportation time to a distribution center. The vehicle can load at most K jobs as a delivery batch in one shipment due to the vehicle capacity constraint. The objective is to minimize the arrival time of the last delivery batch to the distribution center. Since machines may not always be available over the production period in real life due to preventive maintenance, we incorporate machine availability into the models. Three scenarios of the problem are studied. For the problem in which the jobs are processed on a single machine and the jobs interrupted by the unavailable machine interval are resumable, we provide a polynomial algorithm to solve the problem optimally. For the problem in which the jobs are processed on a single machine and the interrupted jobs are nonresumable, we first show that the problem is NP‐hard. We then propose a heuristic with a worst‐case error bound of 1/2 and show that the bound is tight. For the problem in which the jobs are processed on either one of two parallel machines, where only one machine has an unavailable interval and the interrupted jobs are resumable, we propose a heuristic with a worst‐case error bound of 2/3. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

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.