Scheduling with earliness–tardiness penalties and parallel machines

This is a summary of the author’s PhD thesis supervised by Francis Sourd and Philippe Chrétienne and defended on 30 January 2007 at the Université Pierre et Marie Curie, Paris. The thesis is written in French and is available from the author upon request. This work is about scheduling on parallel machines in order to minimize the total sum of earliness and tardiness costs. To solve some variants of this problem we propose: an exact method based on continuous relaxations of convex reformulations derived from a 0–1 quadratic program; a heuristic algorithm that relies on a new exponential size neighborhood search; finally, a lower bound method based on a polynomial time solution of a preemptive scheduling problem for which the cost functions of the jobs have been changed into so called position costs functions. Partial funding provided by CONACyT (Mexican Council for Science&Technology).     

Scheduling problems with random processing times under expected earliness/tardiness costs

This work is concerned with scheduling problems for a single machine. Taking earliness and tardiness of completion time and due–date value into consideration, the objective function with a common due date is considered. The processing time of each job is random. Sufficient conditions guaranteeing an optimal SEPT sequence are derived. Under exponential and normal processing times, further results are obtained     

Efficient algorithms for machine scheduling problems with earliness and tardiness penalties

In this paper, we study the multi-machine scheduling problem with earliness and tardiness penalties and sequence dependent setup times. This problem can be decomposed into two subproblems—sequencing and timetabling. Sequencing focuses on assigning each job to a fixed machine and determine the job sequence on each machine. We call such assignment a semi-schedule. Timetabling focuses on finding an executable schedule from the semi-schedule via idle-time insertion. Sequencing is strongly NP-hard in general. Although timetabling is polynomial-time solvable, it can become a computational bottleneck if the procedure is executed many times within a larger framework. This paper makes two contributions. We first propose a quantum improvement to the computational efficiency of the timetabling algorithm. We then apply it within a squeaky wheel optimization framework to solve the sequencing and overall problem. Finally, we demonstrate the strength of our proposed algorithms by experiments.     

Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date

This study addresses a class of single-machine scheduling problems involving a common due date where the objective is to minimize the total job earliness and tardiness penalties. A genetic algorithm (GA) approach and a simulated annealing (SA) approach utilizing a greedy local search and three well-known properties in the area of common due date scheduling are developed. The developed algorithms enable the starting time of the first job not at zero and were tested using a set of benchmark problems. From the viewpoints of solution quality and computational expenses, the proposed approaches are efficient and effective for problems involving different numbers of jobs, as well as different processing time, and earliness and tardiness penalties.     

A sequential exchange approach for minimizing earliness–tardiness penalties of single-machine scheduling with a common due date

This study focuses on a class of single-machine scheduling problems with a common due date where the objective is to minimize the total earliness–tardiness penalty for the jobs. A sequential exchange approach utilizing a job exchange procedure and three previously established properties in common due date scheduling was developed and tested with a set of benchmark problems. The developed approach generates results better than not only those of the existing dedicated heuristics but also in many cases those of meta-heuristic approaches. And the developed approach performs consistently well in various job settings with respect to the number of jobs, processing time and earliness–tardiness penalties for the jobs.     

Single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs

We study a single-machine scheduling and due window assignment problem, in which job processing times are defined by functions of their starting times (deteriorating effect) and positions in the sequence (learning effect). The problem is to determine the optimal due windows and the processing sequence simultaneously to minimize costs for earliness, tardiness, the window location, window size and makespan. We show that the problem remains polynomially solvable under the proposed model for two popular due window assignment methods: The slack due date assignment method (usually referred to as SLK) and the unrestricted due date assignment method (usually referred to as DIF).     

Single-machine scheduling with linear decreasing deterioration to minimize earliness penalties

We consider a single-machine scheduling problem with linear decreasing deterioration in which the due dates are determined by the equal slack (SLK) method. By the linear decreasing deterioration, we mean that the job’s processing time is a decreasing function of its starting time. The objective is to minimize the total weighted earliness penalty subject to no tardy jobs. We prove that two special cases of the problem remain polynomially solvable. The first case is the problem with equally weighted monotonous penalty objective function and the other case is the problem with weighted linear penalty objective function.     

Scheduling a single machine to minimize earliness penalties subject to the SLK due-date determination method

This paper considers a single machine scheduling problem. There are n jobs to be processed on a single machine. The problem is to minimize total earliness penalties subject to no tardy jobs. The problem is NP-complete if the due-dates are arbitrary. We study the problem when the due-dates are determined by the equal slack (SLK) method. Two special cases of the problem are solved in polynomial time. The first one is the problem with equally weighted monotonous penalty objective function. The second one is the problem with weighted linear penalty objective function.     

Scheduling about a common due date with kob-dependent asymmetric earliness and tardiness penalties

This paper is concerned with the problem of scheduling n jobs with a common due date on a single machine so as to minimize the total cost arising from earliness and tardiness. A general model is examined, in which earliness penalty and tardiness penalty are, respectively, arbitrary non-decreasing functions. Moreover, the model includes two important features that commonly appear in practical problems, namely, 1) earliness and tardiness are penalized with different weights which are job-dependent, and 2) the earliness (or tardiness) penalty consists of two parts, one is a variable cost dependent on the length of earliness (or tardiness), while the other is a fixed cost incurred when a job is early (or tardy). This model provides a general and flexible performance measure for earliness/tardiness scheduling, which has not been addressed before. We establish a number of results on the characterizations of optimal and sub-optimal solutions, and propose two algorithms based on these results. The first algorithm can find, under an agreeable weight condition, an optimum in time O(n² P_n), and the second algorithm can generate a sub-optimum in time O(nP_n), where P_n is the sum of the processing times. Further, we derive an upper bound on the relative error of the sub-optimal solution and show that, under certain conditions, the error tends to zero as n increases. Computational results are also reported to demonstrate the effectiveness of the algorithms proposed.     

A faster algorithm for a due date assignment problem with tardy jobs

The single-machine due date assignment problem with the weighted number of tardy jobs objective, (the TWNTD problem), and its generalization with resource allocation decisions and controllable job processing times have been solved in O(n⁴) time by formulating and solving a series of assignment problems. In this note, a faster O(n²) dynamic programming algorithm is proposed for the TWNTD problem and for its controllable processing times generalization in the case of a convex resource consumption function.     

Minmax scheduling with job-classes and earliness–tardiness costs

We address scheduling problems with job-dependent due-dates and general (possibly nonlinear and asymmetric) earliness and tardiness costs. The number of distinct due-dates is substantially smaller than the number of jobs, thus jobs are partitioned to classes, where all jobs of a given class share a common due-date. We consider the settings of a single machine and parallel identical machines. Our objective is of a minmax type, i.e., we seek a schedule that minimizes the maximum earliness/tardiness cost among all jobs.     

Scheduling jobs on parallel machines with sequence-dependent setup times

Consider a number of jobs to be processed on a number of identical machines in parallel. A job has a processing time, a weight and a due date. If a job is followed by another job, a setup time independent of the machine is incurred. A three phase heuristic is presented for minimizing the sum of the weighted tardinesses. In the first phase, as a pre-processing procedure, factors or statistics which characterize an instance are computed. The second phase consists of constructing a sequence by a dispatching rule which is controlled through parameters determined by the factors. In the third phase, as a post-processing procedure, a simulated annealing method is applied starting from a seed solution which is the result of the second phase. In the dispatching rule of the second phase there are two parameters of which the values are dependent on the particular problem instance at hand. Through extensive experiments rules are developed for determining the values of the two parameters which make the priority rule work effectively. The performance of the simulated annealing procedure in the third phase is evaluated for various values of the factors.     

Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs

We give a direct combinatorial O(n³logn) algorithm for minimizing the number of late jobs on a single machine when jobs have release times and preemptions are allowed. Our algorithm improves the earlier O(n⁵) and O(n⁴) dynamic programming algorithms for this problem.     

Scheduling with deteriorating jobs and learning effects

This paper studies a single machine scheduling problem simultaneously with deteriorating jobs and learning effects. The objectives are to minimize the makespan and the number of tardy jobs, respectively. Two polynomial time algorithms are proposed to solve these problems optimally.     

准时生产和宽容交货中的排序问题

本文综述了近年来国内外对宽容交货中排序问题的研究．     

A unified approach for scheduling with convex resource consumption functions using positional penalties

We provide a unified model for solving single machine scheduling problems with controllable processing times in polynomial time using positional penalties. We show how this unified model can be useful in solving three different groups of scheduling problems. The first group includes four different due date assignment problems to minimize an objective function which includes costs for earliness, tardiness, due date assignment, makespan and total resource consumption. The second group includes three different due date assignment problems to minimize an objective function which includes the weighted number of tardy jobs, due date assignment costs, makespan and total resource consumption costs. The third group includes various scheduling problems which do not involve due date assignment decisions. We show that each of the problems from the first and the third groups can be reduced to a special case of our unified model and thus can be solved in O(n³)$O(n^3)$ time. Furthermore, we show how the unified model can be used repeatedly as a subroutine to solve all problems from the second group in O(n⁴)$O(n^4)$ time. In addition, we also show that faster algorithms exist for several special cases.     

Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine

We consider scheduling problems with learning/deterioration effects and time-dependent processing times on a single machine, with or without due date assignment considerations. By reducing them to a special assignment problem on product matrices, we solve all these problems in near-linear time. This improves the time complexity of previous algorithms for some scheduling problems and establishes the fast polynomial solvability for several other problems.     

Job sequencing and due date assignment in a single machine shop with uncertain processing times

This paper considers due date assignment and sequencing for multiple jobs in a single machine shop. The processing time of each job is assumed to be uncertain and is characterized by a mean and a variance with no knowledge of the entire distribution. A heuristic procedure is developed to find job sequence and due date assignment to minimize a linear combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. Numerical experiments indicate that the performance of the procedure is stable and robust to job processing time distributions. In addition, the performance improves when the means and variances of job processing times are uncorrelated or negatively correlated or when the penalty of a long due date assignment is significant.     

Scheduling chains with identical jobs and constant delays on a single machine

In this paper we study the single-machine problem 1|chains(l), p _j = p|∑ C _j in which jobs with constant processing times and generalized precedence constraints in form of chains with constant delays are given. One has to schedule the jobs on a single machine such that all delays between consecutive jobs in a chain are satisfied and the sum of all completion times of the jobs is minimized. We show that this problem is polynomially solvable. AMS Classification 90B35 Scheduling     

Precedence theorems and dynamic programming for the single-machine weighted tardiness problem

We tackle precedence-constrained sequencing on a single machine in order to minimize total weighted tardiness. Classic dynamic programming (DP) methods for this problem are limited in performance due to excessive memory requirements, particularly when the precedence network is not sufficiently dense. Over the last decades, a number of precedence theorems have been proposed, which distinguish dominant precedence constraints for a job pool that is initially without precedence relation. In this paper, we connect and extend the findings of the foregoing two strands of literature. We develop a framework for applying the precedence theorems to the precedence-constrained problem to tighten the search space, and we propose an exact DP algorithm that utilizes a new efficient memory management technique. Our procedure outperforms the state-of-the-art algorithm for instances with medium to high network density. We also empirically verify the computational gain of using different sets of precedence theorems.