Single-machine scheduling with waiting-time-dependent due dates

We consider a single-machine scheduling problem in which due dates are linear functions of the job waiting-times and the objective is to minimize the maximum lateness. An optimal sequence is constructed by implementing an index-based priority rule for a fixed value of the due date normalizing constant k. We determine in polynomial time all the k value ranges so that the optimal sequence remains the same within each range. The optimal due dates are computed as linear functions of the global optimal value of k. The overall procedure is illustrated in a numerical example.     

Solution strategies for multi-stage wafer probing scheduling problem with reentry

The multi-stage wafer probing scheduling problem (M-WPSP) with reentry is a practical variation of the parallel-machine scheduling problem. Since the M-WPSP involves multiple product families, to be processed on multiple stages, with various job due dates, ready times, reentry, serial and batch operations, sequential-dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problems. In this paper, we consider two strategies to solve the M-WPSP with reentry, where the total machine workload must be minimized. These two strategies incorporate a global planning mechanism, in advance, to determine the required stage due date of job at each process stage to prevent the due date problems occurring at the final stage. The sequential strategy schedules the jobs at the required stages according to the sequence of manufacturing process. The parallel strategy is designed specifically for the reentrant characteristic. To evaluate the efficiency of the proposed strategies, a set of test problems involving four critical factors, the product family ratio, the temperature-change consideration, the tightness of due dates, and the ready time, are designed to test the quality of solutions under two levels of workload.     

Single machine common flow allowance scheduling with controllable processing times

In this paper, we consider single machine SLK due date assignment scheduling problem in which job processing times are controllable variables with linear costs. The objective is to determine the optimal sequence, the optimal common flow allowance and the optimal processing time compressions to minimize a total penalty function based on earliness, tardiness, common flow allowance and compressions. We solve the problem by formulating it as an assignment problem which is polynomially solvable. For some special cases, we present an O(n logn) algorithm to obtain the optimal solution respectively.     

Flow shop scheduling algorithms for minimizing the completion time variance and the sum of squares of completion time deviations from a common due date

We consider two problems of m-machine flow shop scheduling in this paper: one, with the objective of minimizing the variance of completion times of jobs, and the other with the objective of minimizing the sum of squares of deviations of job completion times from a common due date. Lower bounds on the sum of squares of deviations of job completion times from the mean completion time of jobs for a given partial sequence are first presented. Using these lower bounds, a branch and bound algorithm based on breadth-first search procedure for scheduling n jobs on m-machines with the objective of minimizing completion time variance (CTV) is developed to obtain the best permutation sequence. We also present two lower bounds and thereafter, a branch and bound algorithm with the objective of minimizing the sum of squares of deviations of job completion times from a given common due date (called the MSD problem). The computational experience with the working of the two proposed branch and bound algorithms is also reported. Two heuristics, one for each of the two problems, are developed. The computational experience on the evaluation of the heuristics is discussed.     

Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences

In the paper a single machine time-dependent scheduling problem is considered. The processing time p_j of each job is described by a function of the starting time t of the job, p_j=1+α_jt, where the job deterioration rate α_j?0 for j=0,1,…,n and t?0. Jobs are nonpreemptable and independent, there are no ready times and no deadlines. The criterion of optimality of a schedule is the total completion time.First, the notion of a signature for a given sequence of job deterioration rates is introduced, two types of the signature are defined and their properties are shown. Next, on the basis of these properties a greedy polynomial-time approximation algorithm for the problem is formulated. This algorithm, starting from an initial sequence, iteratively constructs a new sequence concatenating the previous sequence with new elements, according to the sign of one of the signatures of this sequence.Finally, these results are applied to the problem with job deterioration rates which are consecutive natural numbers, α_j=j for j=0,1,…,n. Arguments supporting the conjecture that in this case the greedy algorithm is optimal are presented.     

Single machine scheduling problems with general position-dependent processing times and past-sequence-dependent delivery times

This paper considers single machine scheduling with past-sequence-dependent (psd) delivery times, in which the processing time of a job depends on its position in a sequence. We provide a unified model for solving single machine scheduling problems with psd delivery times. We first show how this unified model can be useful in solving scheduling problems with due date assignment considerations. We analyze the problem with four different due date assignment methods, the objective function includes costs for earliness, tardiness and due date assignment. We then consider scheduling problems which do not involve due date assignment decisions. The objective function is to minimize makespan, total completion time and total absolute variation in completion times. We show that each of the problems can be reduced to a special case of our unified model and solved in O(n ³) time. In addition, we also show that each of the problems can be solved in O(nlogn) time for the spacial case with job-independent positional function.     

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 branch and bound algorithm for scheduling jobs with controllable processing times on a single machine to meet due dates

In most deterministic scheduling problems, job-processing times are regarded as constant and known in advance. However, in many realistic environments, job-processing times can be controlled by the allocation of a common resource to jobs. In this paper, we consider the problem of scheduling jobs with arbitrary release dates and due dates on a single machine, where job-processing times are controllable and are modeled by a non-linear convex resource consumption function. The objective is to determine simultaneously an optimal processing permutation as well as an optimal resource allocation, such that no job is completed later than its due date, and the total resource consumption is minimized. The problem is strongly NP\mathcal{NP}-hard. A branch and bound algorithm is presented to solve the problem. The computational experiments show that the algorithm can provide optimal solution for small-sized problems, and near-optimal solution for medium-sized problems in acceptable computing time.     

Scheduling jobs with position-dependent processing times

The paper is devoted to some single machine scheduling problems, where job processing times are defined by functions dependent on their positions in the sequence. It is assumed that each job is available for processing at its ready time. We prove some properties of the special cases of the problems for the following optimization criteria: makespan, total completion time and total weighted completion time. We prove strong NP-hardness of the makespan minimization problem for two different models of job processing time. The reductions are done from the well-known 3-Partition Problem. In order to solve the makespan minimization problems, we suggest the Earliest Ready Date algorithms, for which the worst-case ratios are calculated. We also prove that the makespan minimization problem with job ready times is equivalent to the maximum lateness minimization problem.     

Scheduling with controllable release dates and processing times: Makespan minimization

The paper deals with the single-machine scheduling problem in which job processing times as well as release dates are controllable parameters and they may vary within given intervals. While all release dates have the same boundary values, the processing time intervals are arbitrary. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amount. The objective is to minimize the makespan together with the total compression cost. We construct a reduction to the assignment problem for the case of equal release date compression costs and develop an O(n²) algorithm for the case of equal release date compression costs and equal processing time compression costs. For the bicriteria version of the latter problem with agreeable processing times, we suggest an O(n²) algorithm that constructs the breakpoints of the efficient frontier.     

Batch scheduling with controllable setup and processing times to minimize total completion time

We study a problem of scheduling n jobs on a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time dependent on the position of this batch in the batch sequence. Setup times and job processing times are continuously controllable, that is, they are real-valued variables within their lower and upper bounds. A deviation of a setup time or job processing time from its upper bound is called a compression. The problem is to find a job sequence, its partition into batches, and the values for setup times and job processing times such that (a) total job completion time is minimized, subject to an upper bound on total weighted setup time and job processing time compression, or (b) a linear combination of total job completion time, total setup time compression, and total job processing time compression is minimized. Properties of optimal solutions are established. If the lower and upper bounds on job processing times can be similarly ordered or the job sequence is fixed, then O(n³ log n) and O(n⁵) time algorithms are developed to solve cases (a) and (b), respectively. If all job processing times are fixed or all setup times are fixed, then more efficient algorithms can be devised to solve the problems.     

Scheduling with controllable release dates and processing times: Total completion time minimization

The single machine scheduling problem with two types of controllable parameters, job processing times and release dates, is studied. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amounts. The objective is to minimize the sum of the total completion time of the jobs and the total compression cost. For the problem with equal release date compression costs we construct a reduction to the assignment problem. We demonstrate that if in addition the jobs have equal processing time compression costs, then it can be solved in O(n²) time. The solution algorithm can be considered as a generalization of the algorithm that minimizes the makespan and total compression cost. The generalized version of the algorithm is also applicable to the problem with parallel machines and to a range of due-date scheduling problems with controllable processing times.     

Scheduling with release dates and preemption to minimize multiple max-form objective functions

In this paper, we study multi-agent scheduling with release dates and preemption on a single machine, where the scheduling objective function of each agent to be minimized is regular and of the maximum form (max-form). The multi-agent aspect has three versions, namely ND-agent (multiple agents with non-disjoint job sets), ID-agent (multiple agents with an identical job set), and CO-agent (multiple competing agents with mutually disjoint job sets). We consider three types of problems: The first type (type-1) is the constrained scheduling problem, in which one objective function is to be minimized, subject to the restriction that the values of the other objective functions are upper bounded. The second type (type-2) is the weighted-sum scheduling problem, in which a positive combination of the objective functions is to be minimized. The third type (type-3) is the Pareto scheduling problem, for which we aim to find all the Pareto-optimal points and their corresponding Pareto-optimal schedules. We show that the type-1 problems are polynomially solvable, and the type-2 and type-3 problems are strongly NP-hard even when all jobs’ release dates are zero and processing times are one. When the number of the scheduling criteria is fixed and they are all lateness-like, such as minimizing C_max, F_max, L_max, T_max, and WC_max, where WC_max is the maximum weighted completion time of the jobs, the type-2 and type-3 problems are polynomially solvable. To address the type-3 problems, we develop a new solution technique that guesses the Pareto-optimal points through some elaborately constructed schedule-configurations.     

Two machine preemptive scheduling problem with release dates,equal processing times and precedence constraints

We consider a scheduling problem with two identical parallel machines and n jobs. For each job we are given its release date when job becomes available for processing. All jobs have equal processing times. Preemptions are allowed. There are precedence constraints between jobs which are given by a (di)graph consisting of a set of outtrees and a number of isolated vertices. The objective is to find a schedule minimizing mean flow time. We suggest an O(n²) algorithm to solve this problem.The suggested algorithm also can be used to solve the related two-machine open shop problem with integer release dates, unit processing times and analogous precedence constraints.     

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.     

一个非常规目标函数的单机随机调度的最优策略

本文考虑了n个工件在同一台机器上加工的调度问题 ,其中工件的加工时间和交货期都是具有任意分布的随机变量 .我们考虑了一个非常规目标函数 ,其中工件的权数与平均加工时间成比例 .在工件的交货期与加工时间满足相容条件下 ,得到了个简单的最优排序策略 .     

Soft due window assignment and scheduling of unit-time jobs on parallel machines

We study problems of scheduling n unit-time jobs on m identical parallel machines, in which a common due window has to be assigned to all jobs. If a job is completed within the due window, then no scheduling cost incurs. Otherwise, a job-dependent earliness or tardiness cost incurs. The job completion times, the due window location and the size are integer valued decision variables. The objective is to find a job schedule as well as the location and the size of the due window such that a weighted sum or maximum of costs associated with job earliness, job tardiness and due window location and size is minimized. We establish properties of optimal solutions of these min-sum and min-max problems and reduce them to min-sum (traditional) or min-max (bottleneck) assignment problems solvable in O(n ⁵/m ²) and O(n ^4.5log^0.5 n/m ²) time, respectively. More efficient solution procedures are given for the case in which the due window size cost does not exceed the due window start time cost, the single machine case, the case of proportional earliness and tardiness costs and the case of equal earliness and tardiness costs.     

Single-Machine Scheduling with Exponential Processing Times and General Stochastic Cost Functions

We study a single-machine stochastic scheduling problem with n jobs, in which each job has a random processing time and a general stochastic cost function which may include a random due date and weight. The processing times are exponentially distributed, whereas the stochastic cost functions and the due dates may follow any distributions. The objective is to minimize the expected sum of the cost functions. We prove that a sequence in an order based on the product of the rate of processing time with the expected cost function is optimal, and under certain conditions, a sequence with the weighted shortest expected processing time first (WSEPT) structure is optimal. We show that this generalizes previous known results to more general situations. Examples of applications to practical problems are also discussed.This work was partially supported by the Research Grants Council of Hong Kong under Earmarked Grants No. CUHK4418/99E and No. PolyU 5081/00E.     

Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time

In this paper, we consider single-machine due window assignment and scheduling with a common flow allowance and controllable job processing times, subject to unlimited or limited resource availability. Due window assignment with a common flow allowance means that each job has a job-dependent due window, the starting time and completion time of which are equal to its actual processing time plus the job-independent parameters q₁ and q₂, respectively, which are common to all the jobs. The processing time of each job is either a linear or a convex function of the amount of a common continuously divisible resource allocated to the job. We study five versions of the problem that differ in terms of the objective function and processing time function being used. We provide structural properties of the optimal schedules and polynomial-time solution algorithms for the considered problems.     

Single machine group scheduling with resource dependent setup and processing times

A single machine scheduling problem is studied. There is a partition of the set of n jobs into g groups on the basis of group technology. Jobs of the same group are processed contiguously. A sequence independent setup time precedes the processing of each group. Two external renewable resources can be used to linearly compress setup and job processing times. The setup times are jointly compressible by one resource, the job processing times are jointly compressible by another resource and the level of the resource is the same for all setups and all jobs. Polynomial time algorithms are presented to find an optimal job sequence and resource values such that the total weighted resource consumption is minimum, subject to meeting job deadlines. The algorithms are based on solving linear programming problems with two variables by geometric techniques.