Safe scheduling: Setting due dates in single-machine problems

Abstract

We consider single-machine stochastic scheduling models with due dates as decisions. In addition to showing how to satisfy given service-level requirements, we examine variations of a model in which the tightness of due-dates conflicts with the desire to minimize tardiness. We show that a general form of the trade-off includes the stochastic E/T model and gives rise to a challenging scheduling problem. We present heuristic solution methods based on static and dynamic sorting procedures. Our computational evidence identifies a static heuristic that routinely produces good solutions and a dynamic rule that is nearly always optimal. The dynamic sorting procedure is also asymptotically optimal, meaning that it can be recommended for problems of any size.

Introduction

Safe scheduling is a relatively new approach to stochastic scheduling problems which explicitly acknowledges the role of optimal safety time via the need to meet specified service levels. In this paper, we introduce several new and related problems in safe scheduling, and we provide full or partial solutions. These problems extend and generalize some of the familiar models of scheduling theory and thereby extend our knowledge about scheduling methods and solutions.

We build on the standard single-machine sequencing model containing n jobs (Baker, 2005, Pinedo, 2002). The key parameters in the model include the processing time for job j (p_j) and the due date (d_j). In the actual schedule, job j completes at time C_j, and the set of completion times is summarized in a measure of scheduling performance M that serves as the model’s objective function.

There are broadly two types of models that involve performance measures related to due dates. In one scenario, due dates are given, and a performance measure, such as total tardiness, captures the effectiveness of the schedule at meeting the given due dates. In such a scenario, we may consider rejecting some jobs to enhance performance (Akker and Hoogeveen, 2008, Trietsch and Baker, 2008). In the other scenario, due dates are internal decisions (Soroush, 1999, Portougal and Trietsch, 2006). Such due dates are often negotiated with customers or chosen by production control (ERP) systems to guide or pace the progress of work, and the performance measure may include earliness costs and tardiness costs as well as measures of due-date tightness. In this paper, we describe several related scheduling problems that involve setting due dates; thus, we treat the d_j-values as decision variables.

Our models are also stochastic: the p_j-values are random variables, and we assume that their probability distributions are given. We also assume, unless we state otherwise, that these distributions are independent. As a consequence, job completion times are random variables. In traditional models of stochastic scheduling, the objective function is usually the expected value of the measure M. For example, whereas a deterministic model calls for the minimization of total tardiness, T, the traditional stochastic model would call for the minimization of E[T]. This value is the simplest stochastic analog of the deterministic measure, and the model is referred to as the stochastic counterpart of the original deterministic model.

Safe scheduling models are not necessarily direct stochastic counterparts of deterministic models. A key element of safe scheduling models is the service level, defined for job j as SL_j = Pr{C_j ⩽ d_j}, the probability that job j completes by its due date. Let b_j denote a given target probability, 0 ⩽ b_j ⩽ 1. Then the form of a service-level constraint for job j is Pr{C_j ⩽ d_j} ⩾ b_j. We say that job j is stochastically on time if its service-level constraint is satisfied; otherwise, the job is stochastically tardy. One approach, then, is to optimize some measure of the stochastic tardiness in a schedule. Another approach is to minimize the expected costs associated with missing the due date, which leads to optimal service levels. Both approaches involve safety time, which is defined as the difference between the expected completion time and the due date that achieves the service level.

Our paper discusses a collection of due date setting problems in safe scheduling with one machine. In Section 2, we illustrate safe scheduling concepts by selecting due dates as tightly as possible, subject to service-level constraints. Next, we broaden this model to encompass a trade off between tight due dates and job tardiness. In Section 3, we analyze this trade off for a case in which tardiness depends on the makespan for a batch of jobs and sequencing is not at issue. In Section 4, we generalize to the case in which each job may contribute to tardiness, giving rise to a challenging sequencing problem. In Section 5, we summarize computational experiments that compare heuristic solutions to this problem. In Section 6, we generalize the model further and consider a weighted case. We show that this weighted case is also a generalization of the stochastic earliness–tardiness (E/T) problem analyzed by Soroush and Fredendall, 1994, Soroush, 1999, Portougal and Trietsch, 2006. Finally, in Section 7, we prove asymptotic optimality for two of the heuristics introduced in Sections 5 Computational results, 6 The weighted problem. Rather than begin with a literature review, we provide the main antecedents of our work as we proceed.