Single machine earliness and tardiness scheduling

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs without considering machine idle time. We decompose the problem into two subproblems with a simpler structure. Then the lower bound of the problem is the sum of the lower bounds of two subproblems. A lower bound of each subproblem is obtained by Lagrangian relaxation. Rather than using the well-known subgradient optimization approach, we develop two efficient multiplier adjustment procedures with complexity O(nlog n) to solve two Lagrangian dual subproblems. A branch-and-bound algorithm based on the two efficient procedures is presented, and is used to solve problems with up to 50 jobs, hence doubling the size of problems that can be solved by existing branch-and-bound algorithms. We also propose a heuristic procedure based on the neighborhood search approach. The computational results for problems with up to 3 000 jobs show that the heuristic procedure performs much better than known heuristics for this problem in terms of both solution efficiency and quality. In addition, the results establish the effectiveness of the heuristic procedure in solving realistic problems to optimality or near optimality.     

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.     

Single machine scheduling with flow time and earliness penalties

This paper considers the problem of schedulingn jobs on a single machine to minimize the total cost incurred by their respective flow time and earliness penalties. It is assumed that each job has a due date that must be met, and that preemptions are not allowed. The problem is formulated as a dynamic program (DP) and solved with a reaching algorithm that exploits a series of dominance properties and efficiently generated bounds. A major factor underlying the effectiveness of the approach is the use of a greedy randomized adaptive search procedure (GRASP) to construct high quality feasible solutions. These solutions serve as upper bounds on the optimum, and permit a predominant portion of the state space to be fathomed during the DP recursion.To evaluate the performance of the algorithm, an experimental design involving over 240 randomly generated problems was followed. The test results indicate that problems with up to 30 jobs can be readily solved on a microcomputer in less than 12 minutes. This represents a significant improvement over previously reported results for both dynamic programming and mixed integer linear programming approaches.     

Order acceptance and scheduling with earliness and tardiness penalties

This paper addresses a production scheduling problem in a single-machine environment, where a job can be either early, on time, late, or rejected. In order acceptance and scheduling contexts, it is assumed that the production capacity of a company is overloaded. The problem is therefore to decide which orders to accept and how to sequence their production. In contrast with the existing literature, the considered problem jointly takes into account the following features: earliness and tardiness penalties (which can be linear or quadratic), sequence-dependent setup times and costs, rejection penalties, and the possibility of having idle times. The practical relevance of this new NP-hard problem is discussed and various solution methods are proposed, ranging from a basic greedy algorithm to refined metaheuristics (e.g., tabu search, the adaptive memory algorithm, population-based approaches loosely inspired on ant algorithms). The methods are compared for instances with various structures containing up to 200 jobs. For small linear instances, the metaheuristics are favorably compared with an exact formulation using CPLEX 12.2. Managerial insights and recommendations are finally given.     

Single-machine scheduling with time windows and earliness/tardiness penalties

We study the single machine earliness/tardiness problem with arbitrary time windows (STW). We show that STW is NP-hard and then decompose it into the subproblems of finding a good job sequence and optimally inserting idle time into a given sequence. We propose heuristics for the sequencing subproblem by appropriately modifying heuristics originally developed for other single machine scheduling problems. Experimentation with randomly generated problems shows that one of the proposed heuristics is computationally efficient and capable of finding good solutions to problems of arbitrary size. We also propose an algorithm to optimally insert idle time into a given job sequence.     

Single machine scheduling with family setups to minimize total earliness and tardiness

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize total earliness and tardiness when family setup times exist. The paper proposes optimal branch-and-bound algorithms for both the group technology assumption and if the group technology assumption is removed. A heuristic algorithm is proposed to solve larger problems with the group technology assumption removed. The proposed algorithms were empirically evaluated on problems of various sizes and parameters. The paper also explores how the choice of procedure affects total earliness and tardiness if an implementation of lean production methods has resulted in a reduction in setup times. An important finding of these empirical investigations is that scheduling jobs by removing the group technology assumption can significantly reduce total earliness and tardiness.     

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).     

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.     

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.     

Effects of change of scale on optimality in a scheduling model with priorities and earliness/tardiness penalties

We consider the effect of changes of scale of measurement on the conclusion that a particular solution to a scheduling problem is optimal. The analysis in this paper was motivated by the problem of finding the optimal transportation schedule when there are penalties for both late and early arrivals, and when different items that need to be transported receive different priorities. We note that in this problem, if attention is paid to how certain parameters are measured, then a change of scale of measurement might lead to the anomalous situation where a schedule is optimal if the parameter is measured in one way, but not if the parameter is measured in a different way that seems equally acceptable. This conclusion about the sensitivity of the conclusion that a given solution to a combinatorial optimization problem is optimal is different from the usual type of conclusion in sensitivity analysis, since it holds even though there is no change in the objective function, the constraints, or other input parameters, but only in scales of measurement. We emphasize the need to consider such changes of scale in analysis of scheduling and other combinatorial optimization problems. We also discuss the mathematical problems that arise in two special cases, where all desired arrival times are the same and the simplest case where they are not, namely the case where there are two distinct arrival times but one of them occurs exactly once. While specialized, these two examples illustrate the types of mathematical problems that arise from considerations of the interplay between scale-types and optimization.     

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 scheduling with release times,deadlines and tardiness objectives

A polynomial time algorithm is developed to minimize maximum tardiness on a single machine in the presence of deadlines. The possibility of extending the total tardiness pseudopolynomial algorithm to the cases where release times or deadlines are in place is also investigated. It is concluded that the aforementioned pseudopolynomial algorithm can be extended only when deadlines and due dates are compatible and all job release times are equal.     

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.     

Minimizing earliness and tardiness costs in stochastic scheduling

We address the single-machine stochastic scheduling problem with an objective of minimizing total expected earliness and tardiness costs, assuming that processing times follow normal distributions and due dates are decisions. We develop a branch and bound algorithm to find optimal solutions to this problem and report the results of computational experiments. We also test some heuristic procedures and find that surprisingly good performance can be achieved by a list schedule followed by an adjacent pairwise interchange procedure.     

Single machine scheduling with total tardiness criterion and convex controllable processing times

We consider a single machine scheduling problem with total tardiness criteria and controllable job-processing times specified by a convex resource consumption function. The objective is to have the total tardiness limited into a given range, and minimize the total resource consumption. A polynomial time algorithm of O(n ²) is presented for the special case where jobs have a common due date.     

Scheduling jobs with different,job-dependent earliness and tardiness penalties using the SLK method

The single machine job scheduling problem, where due dates are assigned using the SLK due date determination method, is examined assuming different penalties for the early and tardy jobs. These penalties are assumed to be job-dependent, proportional to the processing times of jobs raised to an integer, non-negative power. The objective function is the total weighted lateness. Several cases are examined and four algorithms providing the optimal sequences for these cases are presented. Examples are given and conclusions are drawn.     

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.     

Minimizing earliness and tardiness penalties in a single-machine problem with a common due date

Scheduling problems involving both earliness and tardiness costs have received significant attention in recent years. This type of problem became important with the advent of the just-in-time (JIT) concept, where early or tardy deliveries are highly discouraged. In this paper we examine the single-machine scheduling problem with a common due date. Performance is measured by the minimization of the sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, we propose a tabu search-based heuristic and a genetic algorithm which exploit specific properties of the optimal solution. Hybrid strategies are also analyzed to improve the performance of these methods. The proposed approaches are examined through a computational comparative study with 280 benchmark problems with up to 1000 jobs.     

Beam search heuristics for quadratic earliness and tardiness scheduling

In this paper, we present beam search heuristics for the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. These heuristics include classic beam search procedures, as well as filtered and recovering algorithms. We consider three dispatching heuristics as evaluation functions, in order to analyse the effect of different rules on the performance of the beam search procedures. The computational results show that using better dispatching heuristics improves the effectiveness of the beam search algorithms. The performance of the several heuristics is similar for instances with low variability. For high variability instances, however, the detailed, filtered and recovering beam search (RBS) procedures clearly outperform the best existing heuristic. The detailed beam search algorithm performs quite well, and is recommended for small- to medium-sized instances. For larger instances, however, this procedure requires excessive computation times, and the RBS algorithm then becomes the heuristic of choice.     

Single machine scheduling problems with controllable processing times and total absolute differences penalties

In this paper, we consider single machine scheduling problem in which job processing times are controllable variables with linear costs. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time, total absolute differences in completion times and total compression cost; minimizing a cost function containing total waiting time, total absolute differences in waiting times and total compression cost. The problem is modelled as an assignment problem, and thus can be solved with the well-known algorithms. For the case where all the jobs have a common difference between normal and crash processing time and an equal unit compression penalty, we present an O(n log n) algorithm to obtain the optimal solution.