A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems

We consider the dynamic single-machine scheduling problem where the objective is to minimize the sum of weighted earliness and weighted tardiness costs. A single pass heuristic, based on decision theory, is developed for constructing schedules. The heuristic permits schedules with idle time between jobs and behaves like a dispatching procedure. The performance of the new heuristic is examined using 116 published problems for which the optimum solution is known. Its performance is also investigated using 540 randomly generated problems covering a variety of conditions by comparing it to two well known dispatching procedures, adapted for dynamic early/tardy problems. The results indicate that the heuristic performs very well.     

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.     

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.     

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.     

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 multi-start dynasearch algorithm for the time dependent single-machine total weighted tardiness scheduling problem

We extend the dynasearch technique, recently proposed by Congram et al., in the context of time-dependent combinatorial optimization problems. As an application we consider a general time-dependent (idleness) version of the well known single-machine total weighted tardiness scheduling problem, in which the processing time of a job depends on its starting time of execution. We develop a multi-start local search algorithm and present experimental results on several types of instances showing the superiority of the dynasearch neighborhood over the traditional one.     

Minimizing the sum of maximum earliness and maximum tardiness in the single-machine scheduling problem with sequence-dependent setup time

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize the sum of maximum earliness and maximum tardiness when sequence-dependent setup times exist (1∣ST _sd ∣ET_max). In this paper, an optimal branch-and-bound algorithm is developed that involves the implementation of lower and upper bounding procedures as well as three dominance rules. For solving problems containing large numbers of jobs, a polynomial time-bounded heuristic algorithm is also proposed. Computational experiments demonstrate the effectiveness of the bounding and dominance rules in achieving optimal solutions in more than 97% of the instances.     

An efficient algorithm for minimizing barrier and penalty functions

Constrained minimization is often done via interior penalty functions. Such functions can be very difficult to minimize using existing algorithms. In this paper, a new algorithm is described which is specially constructed to deal with such functions. It generates search directions by linearizing the objective and constraints about the current (interior) point, substituting these linearizations into the penalty function, and minimizing the result. Properties of the algorithm are derived, an efficient method for solving the direction finding problem is suggested, and computational results are presented. Preliminary results are also given on an extension to quasibarrier and exterior penalty functions.This document may be reproduced in whole or in part for any non-commercial purpose of the United States Government. Its preparation was supported in part by funds allocated to Case Western Reserve University under contract DAHC 19-68-C-0007 (Project Themis) with the U.S. Army Research Office, Durham Army Materiel Command.     

具有学习效应的超前有奖延误受罚的排序问题(英)

本文考虑具有学习效应和共同交货期的单机排序问题.目标函数是加权超前有奖延误受罚总和.我们的目标是寻找一个最优序使得目标函数的值最小.由于该问题是NP-hard的,我们给出一些特殊情况下多项式时间可解的特例.同时在快速估计下界的基础上给出了分支定界算法来求一般情况下的最有排序.     

An algorithm for minimizing flow time and maximum earliness on a single machine

This study presents an algorithm for efficient scheduling in terms of total flow time and maximum earliness. All the algorithms in the literature for solving this problem are based on heuristic procedures, and cannot necessarily generate all efficient schedules. This study shows that this problem can actually be solved in pseudo-polynomial time, and develops an algorithm for so doing. The complexity of the algorithm is O (n²p? log n). Its computational performance in solving problems of various sizes is determined.     

A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times

In this paper we present a new Discrete Particle Swarm Optimization (DPSO) approach to face the NP-hard single machine total weighted tardiness scheduling problem in presence of sequence-dependent setup times. Differently from previous approaches the proposed DPSO uses a discrete model both for particle position and velocity and a coherent sequence metric. We tested the proposed DPSO mainly over a benchmark originally proposed by Cicirello in 2003 and available online. The results obtained show the competitiveness of our DPSO, which is able to outperform the best known results for the benchmark. In addition, we also tested the DPSO on a set of benchmark instances from ORLIB for the single machine total weighted tardiness problem, and we analysed the role of the DPSO swarm intelligence mechanisms as well as the local search intensification phase included in the algorithm.     

An exact algorithm for the precedence-constrained single-machine scheduling problem

This study proposes an efficient exact algorithm for the precedence-constrained single-machine scheduling problem to minimize total job completion cost where machine idle time is forbidden. The proposed algorithm is based on the SSDP (Successive Sublimation Dynamic Programming) method and is an extension of the authors’ previous algorithms for the problem without precedence constraints. In this method, a lower bound is computed by solving a Lagrangian relaxation of the original problem via dynamic programming and then it is improved successively by adding constraints to the relaxation until the gap between the lower and upper bounds vanishes. Numerical experiments will show that the algorithm can solve all instances with up to 50 jobs of the precedence-constrained total weighted tardiness and total weighted earliness–tardiness problems, and most instances with 100 jobs of the former problem.     

A branch-and-bound algorithm for single-machine scheduling with batch delivery minimizing flow times and delivery costs

This paper addresses scheduling a set of jobs on a single machine for delivery in batches to customers or to other machines for further processing. The problem is a natural extension of minimizing the sum of flow times by considering the possibility of delivering jobs in batches and introducing batch delivery costs. The scheduling objective adopted is that of minimizing the sum of flow times and delivery costs. The extended problem arises in the context of coordination between machine scheduling and a distribution system in a supply chain network. Structural properties of the problem are investigated and used to devise a branch-and-bound solution scheme. Computational experiments show significant improvements over an existing dynamic programming algorithm.     

Dual decomposition of a single-machine scheduling problem

We design a fast ascent direction algorithm for the Lagrangian dual problem of the single-machine scheduling problem of minimizing total weighted completion time subject to precedence constraints. We show that designing such an algorithm is relatively simple if a scheduling problem is formulated in terms of the job completion times rather than as an 0–1 linear program. Also, we show that upon termination of such an ascent direction algorithm we get a dual decomposition of the original problem, which can be exploited to develop approximative and enumerative approaches for it. Computational results exhibit that in our application the ascent direction leads to good Lagrangian lower and upper bounds.     

A time-dependent multiple criteria single-machine scheduling problem

We introduce a nonpreemptive single-machine scheduling model with time-dependent multiple criteria. We formulate the problem as a knapsack problem and propose a dynamic programming (DP)-based algorithm to finding all efficient schedules. An illustrative example is enclosed.     

Quality of move-optimal schedules for minimizing total weighted completion time

We study the minimum total weighted completion time problem on identical machines. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio . In a special case, the approximation ratio is .     

Inverse sorting problem by minimizing the total weighted number of changes and partial inverse sorting problems

In this paper, we consider two types of inverse sorting problems. The first type is an inverse sorting problem by minimizing the total weighted number of changes with bound constraints. We present an O(n ²) time algorithm to solve the problem. The second type is a partial inverse sorting problem and a variant of the partial inverse sorting problem. We show that both the partial inverse sorting problem and the variant can be solved by a combination of a sorting problem and an inverse sorting problem. Supported by the Hong Kong Universities Grant Council (CERG CITYU 103105) and the National Key Research and Development Program of China (2002CB312004) and the National Natural Science Foundation of China (700221001, 70425004).