Optimal due-date determination and sequencing with random processing times

This paper considers the problem of due-date determination and sequencing of n stochastically independent jobs on a single machine with random processing times. The objective is to find the optimal due-date values for the constant due-date assignment method and the optimal job sequence that minimize the expected value of a total cost function. It is shown that under suitable assumptions the optimal due-date values can be analytically determined and the jobs should be arranged in the SEPT sequence to minimize the cost.     

Learning effect and deteriorating jobs in the single machine scheduling problems

This paper studies the single machine scheduling problems with learning effect and deteriorating jobs simultaneously. In this model, the processing times of jobs are defined as functions of their starting times and positions in a sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, the makespan, the total completion time and the sum of the k$k$th power of completion times minimization problems remain polynomially solvable, respectively. But for the following objective functions: the total weighted completion time and the maximum lateness, this paper proves that the shortest weighted processing time first (WSPT) rule and the earliest due-date first (EDD) rule can construct the optimal sequence under some special cases, respectively.     

Single Machine Batch Scheduling Problem with Resource Dependent Setup and Processing Time in the Presence of Fuzzy Due Date

We consider a batch scheduling problem on a single machine which processes jobs with resource dependent setup and processing time in the presence of fuzzy due-dates given as follows:1. There are n independent non-preemptive and simultaneously available jobs processed on a single machine in batches. Each job j has a processing time and a due-date.2. All jobs in a batch are completed together upon the completion of the last job in the batch. The batch processing time is equal to the sum of the processing times of its jobs. A common machine setup time is required before the processing of each batch.3. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource.4. The due-date of each job is flexible. That is, a membership function describing non-decreasing satisfaction degree about completion time of each job is defined.5. Under above setting, we find an optimal batch sequence and resource values such that the total weighted resource consumption is minimized subject to meeting the job due-dates, and minimal satisfaction degree about each due-date of each job is maximized. But usually we cannot optimize two objectives at a time. So we seek non-dominated pairs i.e. the batch sequence and resource value, after defining dominance between solutions.A polynomial algorithm is constructed based on linear programming formulations of the corresponding problems.     

Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs

This paper studies the problem of simultaneous due-date determination and sequencing of a set of n jobs on a single machine where processing times are random variables and job earliness and tardiness costs are distinct. The objective is to determine the optimal sequence and the optimal due-dates which jointly minimize the expected total earliness and tardiness cost. We present an analytical approach to determine optimal due-dates, and propose two efficient heuristics of order O(n log n) to find candidates for the optimal sequence. It is demonstrated that variations in processing times increase cost and affect sequencing and due-date determination decisions. Our illustrative examples as well as computational results show that the proposed model produces optimal sequences and optimal due-dates that are significantly different from those provided by the classical deterministic single machine models. Furthermore, our computational experiments reveal that the proposed heuristics perform well in providing either optimal sequences or good candidates with low overcosts.     

Minmax earliness–tardiness costs with unit processing time jobs

The problem addressed in this paper is defined by M parallel identical machines, N jobs with identical (unit) processing time, job-dependent weights, and a common due-date for all jobs. The objective is of a minmax type, i.e. we are interested in minimizing the cost of the worst scheduled job. In the case of a non-restrictive (i.e., sufficiently large) common due-date, the problem is shown to have a solution that is polynomial in the number of jobs. The solution in the case of a restrictive due-date remains polynomial in the number of jobs, but is exponential in the number of machines. We introduce a lower bound on the optimal cost and an efficient heuristic. We show that the worst case relative error of the heuristic is bounded by 2 and that this bound is tight. We also prove that the heuristic is asymptotically optimal under very general assumptions. Finally, we provide an extensive numerical study demonstrating that in most cases the heuristic performs extremely well.     

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.     

Optimal Due-Date Determination and Sequencing of <Emphasis Type="Italic">n</Emphasis> Jobs on a Single Machine

Given a set of n jobs with deterministic processing times and the same ready times, the problem is to find the optimal processing-time multiple k* for the T.W.K. due-date assignment method, and the optimal sequence σ* to minimize the total amount of missed due-dates. It is found that k* is a constant for a given job set and σ* should be in S.P.T. sequence. After the theoretical treatment, a numerical example is given for discussion. The optimal results can readily be extended to situations in which the processing times are random variables with known means and having the same coefficient of variation. From a practical point of view, the main merit of this paper is that it demonstrates how, under certain production environments in which completion times of the jobs can be anticipated, to determine the optimal due-dates and obtain the optimal sequence.     

A due-date assignment problem with learning effect and deteriorating jobs

In this paper we consider a single-machine scheduling problem with the effects of learning and deterioration. In this model, job processing times are defined by functions of their starting times and positions in the sequence. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of earliness, tardiness and due-date. We show that the problem remains polynomially solvable under the proposed model.     

Minimizing the average deviation of job completion times about a common due-date: An extension

This paper treats the same problem as considered by Kanet [Nav. Res. Logist. Q. 28, 643–651 (1981)] about sequencing n jobs on a single machine with penalties occuring when a job is completed early or late. The objective is to minimize the total penalty. The penalty function has the same form as assumed by Kanet, but the restrictive assumption on the due-dates is relaxed. The result is that the quoted common due-date is reduced, while the efficient algorithm proposed by Kanet can still be used to help determine the optimal job sequence.     

On Optimal Common Due-Date Determination

Given a set of n independent jobs to be processed on a singlemachine, the problem is to determine the optimal constant flowallowance for the CON due-date assignment method and the optimaljob sequence to minimize an average missed due-date cost. Alinear programming formulation of the problem is proposed andthe optimal due-date is obtained by solving the LP dual problem.It is shown that the optimal job sequence can be determinedanalytically only under a special circumstance. Finally, a numericalexample is given to demonstrate how the results can be appliedto find the optimal solutions.     

A Generalized Model of Optimal Due-Date Assignment by Linear Programming

A linear-programming model to find the optimal ‘CON due-date’ is considered for n independent jobs to be processed on a single machine. The term ‘CON due-date’ stands for constant-allowance due-date, where each job receives exactly the same due-date. The measure of performance considered is a more generalized version of similar problems studied earlier. Duality theory is used to obtain an optimal solution. Some earlier studies are shown to be special cases of the model studied in this paper. Numerical examples are presented for better understanding.     

Single machine batch scheduling to minimize the weighted number of late jobs

The single machine batch scheduling problem to minimize the weighted number of late jobs is studied. In this problem,n jobs have to be processed on a single machine. Each job has a processing time, a due date and a weight. Jobs may be combined to form batches containing contiguously scheduled jobs. For each batch, a constant set-up time is needed before the first job of this batch is processed. The completion time of each job in the batch coincides with the completion time of the last job in this batch. A job is late if it is completed after its due date. A schedule specifies the sequence of jobs and the size of each batch, i.e. the number of jobs it contains. The objective is to find a schedule which minimizes the weighted number of late jobs. This problem isNP-hard even if all due dates are equal. For the general case, we present a dynamic programming algorithm which solves the problem with equal weights inO(n ³) time. We formulate a certain scaled problem and show that our dynamic programming algorithm applied to this scaled problem provides a fully polynomial approximation scheme for the original problem. Each algorithm of this scheme has a time requirement ofO(n ³/ +n ³ logn). A side result is anO(n logn) algorithm for the problem of minimizing the maximum weight of late jobs.Supported by INTAS Project 93-257.     

Group Scheduling with Controllable Setup and Processing Times: Minimizing Total Weighted Completion Time

The following single machine scheduling problem is studied. A partition of a set of n jobs into g groups on the basis of group technology is given. The machine processes jobs of the same group contiguously, with a sequence independent setup time preceding the processing of each group. The setup times and the job processing times are controllable through the allocation of a continuously divisible or discrete resource to them. Each job uses the same amount of the resource. Each setup also uses the same amount of resource, which may be different from that for the jobs. Polynomial-time algorithms are constructed for variants of the problem of finding an optimal job sequence and resource values so as to minimize the total weighted job completion time, subject to given restrictions on resource consumption. The algorithms are based on a polynomial enumeration of the candidates for an optimal job sequence and solving the problem with a fixed job sequence by linear programming. This research was supported in part by The Hong Kong Polytechnic University under grant number G-T246 and the Research Grants Council of Hong Kong under grant number PolyU 5191/01E. In addition, the research of M.Y. Kovalyov was supported by INTAS under grant number 00-217.     

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.     

Optimal Assignment of Total-work-content Due-dates and Sequencing in a Single-machine Shop

This paper considers the problem of optimal assignment of total-work-content due-dates to n jobs and of sequencing them on a single machine to minimize an objective function depending on the assigned due-date multiple value and maximum tardiness penalty. It is shown that both the earliest due-date and shortest processing time orders yield an optimal sequence. A simple analytical solution method is presented to find the optimal due-dates. After the theoretical treatment an illustrative example is presented for discussion.     

Due-date assignment and maintenance activity scheduling problem

In the scheduling problem addressed in this note we have to determine: (i) the job sequence, (ii) the (common) due-date, and (iii) the location of a rate modifying (maintenance) activity. Jobs scheduled before (after) the due-date are penalized according to their earliness (tardiness) value. The processing time of a job scheduled after the maintenance activity decreases by a job-dependent factor. The objective is minimum total earliness, tardiness and due-date cost. We introduce a polynomial (O(n⁴)) solution for the problem.     

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.     

Minimizing weighted earliness–tardiness and due-date cost with unit processing-time jobs

The classical single-machine scheduling and due-date assignment problem of Panwalker et al. [Panwalker, S.S., Smith, M.L., Seidmann, A., 1982. Common due date assignment to minimize total penalty for the one machine scheduling problem. Operations Research 30(2) (1982) 391–399] is the following: All n jobs share a common due-date, which is to be determined. Jobs completed prior to or after the due-date are penalized according to a cost function which is linear and job-independent. The objective is to minimize the total earliness–tardiness and due-date cost. We study a generalized version of this problem in which: (i) the earliness and tardiness costs are allowed to be job dependent and asymmetric and (ii) jobs are processed on parallel identical machines. We focus on the case of unit processing-time jobs. The problem is shown to be solved in polynomial (O(n⁴)) time. Then we study the special case with no due-date cost (a classical problem known in the literature as TWET). We introduce an O(n³) solution for this case. Finally, we study the minmax version of the problem, (i.e., the objective is to minimize the largest cost incurred by any of the jobs), which is shown to be solved in polynomial time as well.     

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.     

On a single-machine optimal constant due-date assignment and sequencing problem

This paper considers the problem of optimal constant due-date assignment and sequencing of jobs in a single-machine shop. We formulate the problem as a general constrained optimization problem and apply the Kuhn-Tucker conditions to find the optimal solution which is shown to be independent of the job sequence.