A tabu search algorithm for the single machine total weighted tardiness problem

In this study, a tabu search (TS) approach to the single machine total weighted tardiness problem (SMTWT) is presented. The problem consists of a set of independent jobs with distinct processing times, weights and due dates to be scheduled on a single machine to minimize total weighted tardiness. The theoretical foundation of single machine scheduling with due date related objectives reveal that the problem is NP-hard, rendering it a challenging area for meta-heuristic approaches. This paper presents a totally deterministic TS algorithm with a hybrid neighborhood and dynamic tenure structure, and investigates the strength of several candidate list strategies based on problem specific characteristics in increasing the efficiency of the search. The proposed TS approach yields very high quality results for a set of benchmark problems obtained from the literature.     

A decomposition algorithm for the single machine total tardiness problem

The problem of sequencing jobs on a single machine to minimize total tardiness is considered. An algorithm, which decomposes the problem into subproblems which are then solved by dynamic programming when they are sufficiently small, is presented and is tested on problems with up to 100 jobs.     

带有固定区间的单机双代理可中断总误工问题

研究带有固定区间的两个代理单机排序问题.第一个代理工件可中断,且工件到达时间与工期满足一致关系,目标函数为最小化总误工.第二个代理工件被安排在固定时间窗口.目标是寻找一个排序,使得满足第二个代理目标可行情况下,第一个代理目标函数值最小.在固定区间等于加工时间的情况下,利用分块原则,提出了一个伪多项式时间动态规划算法,并给出了固定区间大于加工时间情况下的时间复杂度分析.     

Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness

We consider the problem of scheduling n preemptive jobs on a single machine to minimize total tardiness, subject to agreeable due dates, i.e., a later release date corresponds to a later due date. We prove that the problem is -hard in the ordinary sense by showing that it is -hard, and deriving a pseudo-polynomial algorithm for it.     

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.     

单机排序中带可分配工期的总误工问题的应急管理

对于机器排序的应急管理问题,Qi Xiang-tong等人进行了系统分析,得出了较好的结果.此文则考虑带可分配工期的总误工问题的应急管理问题.对于不同模型,或给出其最优序,或给出其近似解.     

An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem

Based on the work by Congram, Potts and Van de Velde, we develop for the single-machine total weighted tardiness scheduling problem an enhanced dynasearch neighborhood obtained by the generalized pairwise interchange (GPI) operators. Despite of the wider neighborhood considered, a fast search procedure using also elimination criteria is developed. The computational results significantly improve over those of Congram, Potts and Van de Velde.     

A fully polynomial approximation scheme for the total tardiness problem

A fully polynomial approximation scheme is presented for the problem of sequencing jobs for processing by a single machine so as to minimize total tardiness. This result is obtained by modifying the author's pseudopolynomial algorithm for the same problem.     

Lower bounds for the earliness–tardiness scheduling problem on parallel machines with distinct due dates

This paper addresses the parallel machine scheduling problem in which the jobs have distinct due dates with earliness and tardiness costs. New lower bounds are proposed for the problem, they can be classed into two families. First, two assignment-based lower bounds for the one-machine problem are generalized for the parallel machine case. Second, a time-indexed formulation of the problem is investigated in order to derive efficient lower bounds throught column generation or Lagrangean relaxation. A simple local search algorithm is also presented in order to derive an upper bound. Computational experiments compare these bounds for both the one machine and parallel machine problems and show that the gap between upper and lower bounds is about 1.5%.     

Minimizing total tardiness in a scheduling problem with a learning effect

Minimizing of total tardiness is one of the most studied topics on single machine problems. Researchers develop a number of optimizing and heuristic methods to solve this NP-hard problem. In this paper, the problem of minimizing total tardiness is examined in a learning effect situation. The concept of learning effects describes the reduction of processing times arising from process repetition. A 0–1 integer programming model is developed to solve the problem. Also, a random search, the tabu search and the simulated annealing-based methods are proposed for the problem and the solutions of the large size problems with up to 1000 jobs are found by these methods. To the best of our knowledge, no works exists on the total tardiness problem with a learning effect tackled in this paper.     

Approximation algorithms for scheduling problems with a modified total weighted tardiness objective

We study the approximability of minimum total weighted tardiness with a modified objective which includes an additive constant. This ensures the existence of a positive lower bound for the minimum value. Moreover the new objective has a natural interpretation in just-in-time production systems.     

Fast neighborhood search for the single machine total weighted tardiness problem

Most successful heuristics for solving 1||∑w_jT_j are based on swap moves. We present an algorithm which improves the complexity of searching the swap neighborhood from O(n³) to O(n²). We show that this result also improves the complexity of the recently developed dynasearch heuristics.     

Complexity of flow time minimization in a crossdock truck scheduling problem with asymmetric handover relations

We address a novel truck scheduling problem arising in crossdocking logistics, in which inbound trucks carry items (pallets) which must be sorted and loaded onto outbound trucks. We minimize the utilisation of the warehouse by focusing on the synchronisation between the different related trucks. The problem is to assign the trucks to the doors of the warehouse and sequence them, in order to minimize the total time spent in the system by the pallets. We discuss the complexity of the problem, showing that even with a single door the problem is NP-hard in general, and discuss some special cases.     

A genetic algorithm for resource investment project scheduling problem,tardiness permitted with penalty

In this paper a genetic algorithm for solving a class of project scheduling problems, called Resource Investment Problem, is presented. Tardiness of project is permitted with defined penalty. Elements of algorithm such as chromosome structure, unfitness function, crossover, mutation, immigration and local search operations are explained.     

Preemptive scheduling of two uniform parallel machines to minimize total tardiness

We consider the problem of preemptive scheduling n jobs on two uniform parallel machines. All jobs have equal processing requirements. For each job we are given its due date. The objective is to find a schedule minimizing total tardiness ∑T_i. We suggest an O(n log n) algorithm to solve this problem.     

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.     

Tight bounds for break minimization in tournament scheduling

We consider round-robin sports tournaments with n teams and n−1 rounds. We construct an infinite family of opponent schedules for which every home-away assignment induces at least breaks. This construction establishes a matching lower bound for a corresponding upper bound from the literature.     

Bicriteria problems to minimize maximum tardiness and due date assignment cost in various scheduling environments

We study bicriteria problems of minimizing maximum tardiness and total due date assignment cost in various scheduling environments. We assume that each job can be assigned a different due date without any restriction, and that each due date assignment cost is a non-decreasing function of the quoted due date. We settle the complexity of most of the problems studied by either proving that they are NP-hard or finding a polynomial time solution for them. We also include approximation and non-approximability results for several parallel-machine problems.