This chapter presents a novel idea for the general case of the Common Due-Date (CDD) scheduling problem. The problem is about scheduling a certain number of jobs on a single or parallel machines where all the jobs possess different processing times but a common due-date. The objective of the problem is to minimize the total penalty incurred due to earliness or tardiness of the job completions. This work presents exact polynomial algorithms for optimizing a given job sequence for single and identical parallel machines with the run-time complexities of O(nlogn) for both cases, where n is the number of jobs. Besides, we show that our approach for the parallel machine case is also suitable for non-identical parallel machines. We prove the optimality for the single machine case and the run-time complexities of both. Henceforth, we extend our approach to one particular dynamic case of the CDD and conclude the chapter with our results for the benchmark instances provided in the OR library.
The Common due-date problem has been studied extensively during the last @math years with several variants and special cases @cite_0 @cite_16 . In @math , Kanet presented an O( @math ) algorithm for minimizing the total absolute deviation of the completion of jobs from the due date for the single machine, @math being the number of jobs @cite_16 . Panwalkar considered the problem of common due-date assignment to minimize the total penalty for one machine @cite_5 . The objective of the problem was to determine the optimum value for the due-date and the optimal job sequence to minimize the penalty function, where the penalty function also depends on the due-date along with earliness and tardiness. An algorithm of O( @math ) complexity was presented but the special problem considered by them consisted of symmetric costs for all the jobs @cite_0 @cite_5 .
@cite_0 @cite_5 @cite_16
2009357368 2027120502 2084068443 1964447957 2032069874 2117416910 2963356083 2043295707 2091164478 2002352006 2124388232 2056177557 2081954069 2070993566 2117135110 2062701203 1995073517 1852354434 1485083952 2014369282
This paper investigates the single-machine multiple common due dates assignment and scheduling problems in which the processing time of a job depends on its position in a job sequence and its resource allocation. We examine the general position-dependent deterioration effect and two models of resource allocation. The objective function is to minimize a total penalty function containing earliness, tardiness, due date, and resource consumption costs. We introduce two polynomial time algorithms to solve the considered problems. Since the two algorithms solve the problems in polynomial time, they can solve large-scale instances of the problem under study in little time. This paper addresses the single machine scheduling problem with a common due date aiming to minimize earliness and tardiness penalties. Due to its complexity, most of the previous studies in the literature deal with this problem using heuristics and metaheuristics approaches. With the intention of contributing to the study of this problem, a branch-and-bound algorithm is proposed. Lower bounds and pruning rules that exploit properties of the problem are introduced. The proposed approach is examined through a computational comparative study with 280 problems involving different due date scenarios. In addition, the values of optimal solutions for small problems from a known benchmark are provided. Mathematical subject classification: 90C11, 62P30, 90B35. We consider a one-machine scheduling problem with earliness and tardiness penalties. All jobs are assigned a common due date and the objective is to minimize the total penalty due to job earliness and tardiness. We are interested in finding the optimal combination of the common due-date value and the job sequence. Despite the fact that this problem in general is very hard to solve, we prove that there exists at least a common property for all optimal solutions: The first job in an optimal sequence is one of the longest jobs. We also prove that this property holds for a general class of unimodal penalty functions. Abstract We consider the NP-hard problem of scheduling jobs on a single machine against common due dates with respect to earliness and tardiness penalties. The paper covers two aspects: Firstly, we develop a problem generator and solve 280 instances with two new heuristics to obtain upper bounds on the optimal objective function value. Secondly, we demonstrate computationally that our heuristics are efficient in obtaining near-optimal solutions for small problem instances. The generated problem instances in combination with the upper bounds can be used as benchmarks for future approaches in the field of common due-date scheduling. Scope and purpose In connection with just-in-time production and delivery, earliness as well as tardiness penalties are of interest. Thus scheduling against common due dates has received growing attention during the last decade. Many algorithms have been developed to solve the different variants of this problem. But whenever a new algorithm for scheduling against common due dates is proposed, its quality is assessed only on a few self-generated examples. Hence it is difficult to evaluate the various approaches, particularly in comparison with each other. Therefore the goal of this paper is to present numerous benchmark problems together with some upper bounds on the optimal objective function value. We consider the problem of scheduling a number of jobs on a single machine against a restrictive common due date. The paper consists of two parts: firstly a new and appropriate problem representation is developed. As the restrictive common due date problem is known to be intractable we decided, secondly, to apply meta-heuristics, namely evolutionary strategies, simulated annealing and threshold accepting. We demonstrate that our application of these meta-heuristics is efficient in obtaining near-optimal solutions by solving 140 benchmark problems with up to 1000 jobs. Furthermore, we compare their solution quality and find that a new variant of threshold accepting is superior to the other approaches. We consider an n job, one machine scheduling problem in which all jobs have a common due date. The objective is to determine the optimal value of this due date and an optimal sequence to minimize a total penalty function. This penalty function is based on the due date value and on the earliness or the lateness of each job in the selected sequence. We present a polynomial bound scheduling algorithm for the solution of this problem along with the proof of optimality, a numerical example and discuss some extensions. This paper considers the problem of scheduling jobs on single and parallel machines where all the jobs possess different processing times but a common due date. There is a penalty involved with each job if it is processed earlier or later than the due date. The objective of the problem is to find the assignment of jobs to machines, the processing sequence of jobs and the time at which they are processed, which minimizes the total penalty incurred due to tardiness or earliness of the jobs. This work presents exact polynomial algorithms for optimizing a given job sequence for single and parallel machines with the run-time complexities of O(n log n) and O(mn2 log n) respectively, where n is the number of jobs and m the number of machines. The algorithms take a sequence consisting of all the jobs (J_i, i = 1,2,...,n) as input and distribute the jobs to machines (for m>1) along with their best completion times so as to get the least possible total penalty for this sequence. We prove the optimality for the single machine case and the runtime complexities of both. Henceforth, we present the results for the benchmark problems and compare with previous work for both single and parallel machine cases, up to 200 jobs. Abstract This paper considers due-date assignments and sequencing of n jobs in a single- machine shop in which each job is given a constant waiting allowance. The objective is to find the optimal value of the waiting allowance and the optimal job sequence to minimize a cost function based on the waiting allowance and the job earliness and tardiness values. We formulate the problem as an LP and find the optimal solution via considering the LP dual problem and show that the optimal waiting allowance is independent of the job sequence. A companion paper Part I considers the problem of minimizing the weighted earliness and tardiness of jobs scheduled on a single machine around a common due date, d, which is unrestrictively late. This paper Part II considers the problem of minimizing the unweighted earliness and tardiness of jobs, allowing the possibility that d is early enough to constrain the scheduling decision. We describe several optimality conditions. The recognition version of the problem is shown to be NP-complete in the ordinary sense, confirming a well known conjecture. Moreover, this complexity definition is precise, since we describe a dynamic programming algorithm which runs in pseudopolynomial time. This algorithm is also extremely efficient computationally, providing an improvement over earlier procedures, of almost two orders of magnitude in the size of instance that can be solved. Finally, we describe a special case of the problem which is polynomially solvable. Given processing times of n jobs on a single machine with penalties for earliness and tardiness and penalties associated with assignment of due-dates, the objective is to select optimal due-dates and optimal sequence. Scheduling procedure for the solution of this problem is presented along with proof of optimality and illustrative numerical examples. This paper considers a single-machine scheduling problem in which penalities occur when a job is completed early or late. The objective is to minimize the total penalty subject to restrictive assumptions on the due dates and penalty functions for jobs. A procedure is presented for finding an optimal schedule. A set of n jobs has to be scheduled on a single machine which can handle only one job at a time. Each job requires a given positive uninterrupted processing time and has a positive weight. The problem is to find a schedule that minimizes the sum of weighted deviations of the job completion times from a given common due date d, which is smaller than the sum of the processing times. We prove that this problem is NP-hard even if all job weights are equal. In addition, we present a pseudopolynomial algorithm that requires O(n2d) time and O(nd) space. The scheduling problem 1|pmtn, r j |Σw j U j calls forn jobs with arbitrary release dates and due dates to be preemptively scheduled for processing by a single machine, with the objective of minimizing the sum of the weights of the late jobs. A dynamic programming algorithm for this problem is described. Time and space bounds for the algorithm are, respectively,O(nk2W2) andO(k2W), wherek is the number of distinct release dates andW is the sum of the integer job weights. Thus, for the problem 1|pmtn, r j |ΣU j , in which the objective is simply to minimize the number of late jobs, the pseudopolynomial time bound becomes polynomial, i.e.O(n3k2). Suppose that there are n jobs and n machines and it costs cij to execute job i on machine j. The assignment problem concerns the determination of a one-to-one assignment of jobs onto machines so as to minimize the cost of executing all the jobs. When the cij are independent and identically distributed exponentials of mean 1, Parisi [Technical Report cond-mat 9801176, xxx LANL Archive, 1998] made the beautiful conjecture that the expected cost of the minimum assignment equals @math . Coppersmith and Sorkin [Random Structures Algorithms 15 (1999), 113–144] generalized Parisi's conjecture to the average value of the smallest k-assignment when there are n jobs and m machines. Building on the previous work of Sharma and Prabhakar [Proc 40th Annu Allerton Conf Communication Control and Computing, [2002], 657–666] and Nair [Proc 40th Annu Allerton Conf Communication Control and Computing, [2002], 667–673], we resolve the Parisi and Coppersmith-Sorkin conjectures. In the process we obtain a number of combinatorial results which may be of general interest.© 2005 Wiley Periodicals, Inc. Random Struct. Alg. 2005Supported by the Stanford Graduate Fellowship and Stanford Networking Research Center Grant 1005544-1-WAAXI.Supported in part by the NSF Grant ANI-9985446.Supported by Stanford Office of Technology Grant 2DTA112, Stanford Networking Research Center Grant 1005545-1-WABCJ, and NSF Grant ANI-9985446. Chen (1994) develops an attractive variant of the classical problem of preemptively scheduling independent jobs with release dates and due dates. Chen suggests that in practice one can often pay to reduce the processing requirement of a job. This leads to two parametric max flow problems. Serafini (1996) considers scheduling independent jobs with due dates on multiple machines, where jobs can be split among machines so that pieces of a single job can execute in parallel. Minimizing the maximum tardiness again gives a parametric max flow problem. A third problem of this type is deciding how many more games a baseball team can lose part way through a season without being eliminated from finishing first (assuming a best possible distribution of wins and losses by other teams). A fourth such problem is an extended selection problem of (1995a), where we want to discount the costs of "tree-structured" tools as little as possible to be able to process all jobs at a profit. It is tempting to try to solve these problems with the parametric push-relabel max flow methods of (GGT) (1989). However, all these applications appear to violate the conditions necessary to apply GGT. We extend GGT in three ways that allow it to be applied to all four of the above applications. We also consider some other applications where these ideas apply. Our extensions to GGT yield faster algorithms for all these applications. This article uses tabu search to solve the restricted, common-due-date, early tardy machine scheduling problem generalised earliness and tardiness penalties. Different forms of the tabu search are tested, including one based on a sequence of jobs solution space and another based on an early tardy solution space. Results show that a search which uses an early tardy solution space with a neighbourhood scheme which eliminates infeasible areas of the solution space is the most efficient and effective solution method. In 1966, Graham showed that a simple procedure called list scheduling yields a 2-approximation algorithm for the central problem of scheduling precedence constrained jobs on identical machines to minimize makespan. To date this has remained the best algorithm, and whether it can or cannot be improved has become a major open problem in scheduling theory. We address this problem by establishing a quite surprising relation between the approximability of the considered problem and that of scheduling precedence constrained jobs on a single machine to minimize weighted completion time. More specifically, we prove that if the single machine problem is hard to approximate within a factor of @math , then the considered parallel machine problem, even in the case of unit processing times, is hard to approximate within a factor of @math , where @math tends to 0 as @math tends to 0. Combining this with Bansal and Khot's recent hardness result for the single machine problem gives that it is NP-hard to improve upon the approximation ratio obtained by Graham, assuming a new variant of the unique games conjecture. We consider the classical problem of scheduling a set of independent jobs on a set of unrelated machines with costs. We are given a set of n monoprocessor jobs and m machines where each job is to be processed without preemptions. Executing job j on machine i requires time pij ≥ 0 and incurs cost cij . Our objective is to find a schedule obtaining a tradeoff between the makespan and the total cost. We focus on the case where the number of machines is a fixed constant, and we propose a simple FPTAS that computes for any Ɛ > 0 a schedule with makespan at most (1+Ɛ)T and cost at most Copt(T), in time O(n(n Ɛ)m), given that there exists a schedule of makespan T, where Copt(T) is the cost of the minimum cost schedule which achieves a makespan of T. We show that the optimal makespan-cost trade-off (Pareto) curve can be approximated by an efficient polynomial time algorithm within any desired accuracy. Our results can also be applied to the scheduling problem where the rejection of jobs is allowed. Each job has a penalty associated to it, and one is allowed to schedule any subset of jobs. In this case the goal is the minimization of the makespan of the scheduled jobs and the total penalty of the rejected jobs. We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. We aim for a universal solution that performs well without adaptation for any possible machine behavior. For the objective of minimizing the total weighted completion time, we design a polynomial time deterministic algorithm that finds a universal scheduling sequence with a solution value within 4 times the value of an optimal clairvoyant algorithm that knows the disruptions in advance. A randomized version of this algorithm attains in expectation a ratio of e. We also show that both results are best possible among all universal solutions. As a direct consequence of our results, we answer affirmatively the question of whether a constant approximation algorithm exists for the offline version of the problem when machine unavailability periods are known in advance. When jobs have individual release dates, the situation changes drastically. Even if all weights are equal, there are instances for which any universal solution is a factor of Ω(logn loglogn) worse than an optimal sequence. Motivated by this hardness, we study the special case when the processing time of each job is proportional to its weight. We present a non-trivial algorithm with a small constant performance guarantee. The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine; processing jobj on machinei requires timep ij and incurs a cost ofc ij ; each machinei is available forT i time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a valueC, either proves that no feasible schedule of costC exists, or else finds a schedule of cost at mostC where each machinei is used for at most 2T i time units.