A Heuristic for Common Due-date Assignment and Job Scheduling on Parallel Machines

In this paper we consider the problem of scheduling a set of simultaneously available jobs on several parallel and identical machines. The problem is to find the optimal due-date, assuming this to be the same for all jobs. We also seek to sequence the jobs such that some are early and some are late so as to minimize a penalty function. For the single-machine problem, we present a simple proof of the well-known optimality result that the optimal due-date coincides with one of the job completion times. We show that the optimal job sequence for the single-machine problem can be easily determined. We prove that the same optimal due-date result can be generalized to the parallel-machine problem. However, determination of the optimal job sequence for such a problem is much more complex, and we present a simple heuristic to find an approximate solution. On the basis of a limited experiment, we observe that the heuristic is very effective in obtaining near-optimal solutions.     

Minimizing total completion time and total deviation of job completion times from a restrictive due-date

We study a single-machine scheduling problem with the objective of minimizing a linear combination of total job completion times and total deviation of job completion times from a common due-date. The due-date is assumed to be restrictive, i.e., it may be sufficiently small to have an impact on the optimal sequence. When more weight is allocated to total job completion times, the problem is shown to have a polynomial time solution. When more weight is allocated to total completion time deviations from the due-date, the problem is NP-hard in the ordinary sense. For the latter case, we introduce an efficient dynamic programming algorithm, which is shown numerically to perform well in all our tests.     

Due-date assignment and single machine scheduling with deteriorating jobs

We study a scheduling problem with deteriorating jobs, that is, jobs whose processing times are an increasing function of their start times. We consider the case of a single machine and linear job-independent deterioration. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of due-date, earliness and tardiness penalties. We give an O(n log n) time algorithm to solve this problem.     

Single-machine scheduling to minimize earliness and number of tardy jobs

This paper considers the problem of assigning a common due-date to a set of simultaneously available jobs and sequencing them on a single machine. The objective is to determine the optimal combination of the common due-date and job sequence that minimizes a cost function based on the assigned due-date, job earliness values, and number of tardy jobs. It is shown that the optimal due-date coincides with one of the job completion times. Conditions are derived to determine the optimal number of nontardy jobs. It is also shown that the optimal job sequence is one in which the nontardy jobs are arranged in nonincreasing order of processing times. An efficient algorithm of O(n logn) time complexity to find the optimal solution is presented and an illustrative example is provided. Finally, several extensions of the model are discussed.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant OPG0036424. The authors are thankful to two anonymous referees for their constructive comments.     

Order acceptance and due-date quotation in low machine rates

In real manufacturing environments, some customer orders include multiple jobs. However, a single due-date should be assigned to each order. Further, machine processing rate is not constant at all times. In effect, in many manufacturing operations, the machine processing rate decreases to a subnormal level during time and needs a special type of maintenance to bring the normal state back. Due to this reduction in capacity, production schedulers may decide to reject some orders. In this paper, the novel extensive problem of selecting a subset of orders, assigning due-dates to selected orders, scheduling the selected orders and jobs within each one, and scheduling the rate-modifying maintenance is studied. The objective function is minimizing total cost of lost-sales of rejected orders together with due-date length and maximum of earliness and tardiness of selected orders. The problem is proved polynomial and an optimal approach is developed.     

On the Multiple-machine Extension to a Common Due-date Assignment and Scheduling Problem

In a recent paper, Cheng considers the multiple-machine extension to a due-date assignment and scheduling problem. He implicitly assumes zero start times for all schedules (which does not ensure optimality), and overlooks the critical V-shape property for an optimal schedule (which leads him to over-estimate the effort needed to solve the problem). In this note, we correct these flaws, and also discuss the complexity of the problem and its special cases.     

Due-date assignment and parallel-machine scheduling with deteriorating jobs

In this paper we study the problem of scheduling n deteriorating jobs on m identical parallel machines. Each job's processing time is a nondecreasing function of its start time. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of the due-date, earliness and tardiness penalties. We show that this problem is NP-hard, and we present a heuristic algorithm to find near-optimal solutions for the problem. When the due-date penalty is 0, we present a polynomial time algorithm to solve it.     

A Note on the Common Due-Date Assignment Problem

This note considers the n-job, one-machine scheduling problem with common due-dates. Previous research has shown that the optimal value of the common due-date coincides with one of the job completion times for a given job sequence. In this note, we propose a linear programming (L.P.) formulation of the problem and obtain the same optimal result via considering the L.P. dual problem.     

Algorithms for common due-date assignment and sequencing on a single machine with sequence-dependent setup times

This paper focuses on the single machine sequencing and common due-date assignment problem for the objective of minimizing the sum of the penalties associated with earliness, tardiness and due-date assignment. Unlike the previous research articles on this class of scheduling problem, we consider sequence-dependent setup times that make the problem much more difficult. To solve the problem, a branch and bound algorithm, which incorporates the method to obtain lower and upper bounds as well as a dominance property to reduce the search space, is suggested that gives the optimal solutions for small-sized instances. Heuristic algorithms are suggested to obtain solutions for large-sized problems within a reasonable computation time. The performances of both the optimal and heuristic algorithms, in computational experiments on randomly generated test instances, are reported.     

Improving delivery reliability by a new due-date setting rule

We study the dynamic due-date setting problem where the objective is to improve delivery performance. Since the problem is NP-hard, we propose a simple, new, general, heuristic due-date setting procedure called the SL rule. For the classical M/M/1 queuing model, we analytically determine the optimum parameter for the proposed rule to achieve best due-date performance. We then show that the optimized SL rule outperforms the work-content-based TWK rule in terms of fraction tardy, mean tardiness, and mean earliness. Additional numerical and simulation analysis for a range of conditions, covering different shop workload levels and priority regimes, confirms that the proposed rule produces best due-date performance, compared to the work-content-based rule, under most of the conditions studied.