Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date

DOI10.1287/OPRE.39.5.847zbMath0762.90037OpenAlexW2091164478MaRDI QIDQ3988911

Nicholas G. Hall, Wiesław X. Kubiak, Suresh P. Sethi

Publication date: 28 June 1992

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.39.5.847

zbMATH Keywords

optimality conditionssingle machinecommon due dateNP-completepseudopolynomial dynamic programmingcost penaltiessum of unweighted earliness and tardiness

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items (87)

Single machine scheduling with assignable due dates ⋮ Two-machine flow shop scheduling with two criteria: maximum earliness and makespan ⋮ Simultaneous minimization of total completion time and total deviation of job completion times ⋮ Mixed integer formulations using natural variables for single machine scheduling around a common due date ⋮ The stochastic single machine scheduling problem with earliness and tardiness costs ⋮ A single machine scheduling with generalized and periodic due dates to minimize total deviation ⋮ A branch-and-bound algorithm for the early/tardy machine scheduling problem with a common due-date and sequence-dependent setup time ⋮ Machine scheduling with earliness, tardiness and non-execution penalties ⋮ Due window scheduling for parallel machines ⋮ Minimizing earliness and tardiness penalties in a single-machine problem with a common due date ⋮ Earliness-tardiness scheduling problems with a common delivery window ⋮ Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs ⋮ Optimal restricted due date assignment in scheduling ⋮ Minimizing weighted number of tardy jobs and weighted earliness-tardiness penalties about a common due date ⋮ Minimizing the sum of earliness/tardiness in identical parallel machines schedule with incompatible job families: An improved MIP approach ⋮ A sequential exchange approach for minimizing earliness-tardiness penalties of single-machine scheduling with a common due date ⋮ An improved dynamic programming algorithm for the single-machine mean absolute deviation problem with a restrictive common due date ⋮ Just-In-Time Scheduling with Generalized Due Dates and Identical Due Date Intervals ⋮ Single machine scheduling with discretely controllable processing times ⋮ Using tabu search to solve the common due date early/tardy machine scheduling problem ⋮ Single machine scheduling to minimize weighted earliness subject to maximum tardiness ⋮ The complexity of scheduling job families about a common due date ⋮ The weighted common due date single machine scheduling problem revisited ⋮ Minimizing total earliness and tardiness on a single machine using a hybrid heuristic ⋮ A fixed interval due-date scheduling problem with earliness and due-date costs ⋮ Total absolute deviation of job completion times on uniform and unrelated machines ⋮ The symmetric quadratic knapsack problem: approximation and scheduling applications ⋮ Minimizing weighted earliness-tardiness on a single machine with a common due date using quadratic models ⋮ Just-in-Time Scheduling with Equal-Size Jobs ⋮ A composite heuristic for the single machine early/tardy job scheduling problem. ⋮ Just‐in‐time scheduling problem with due windows and release dates for precast bridge girders ⋮ Scheduling with time-dependent discrepancy times ⋮ Scheduling with controllable release dates and processing times: total completion time minimization ⋮ Scheduling jobs with a V-shaped time-dependent processing time ⋮ A branch and bound approach for single machine scheduling with earliness and tardiness penalties ⋮ Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard ⋮ Group sequencing around a common due date ⋮ Scheduling around a small common due date ⋮ Scheduling to minimize weighted earliness and tardiness about a common due-date ⋮ Scheduling jobs on a machine subject to stochastic breakdowns to minimize absolute early-tardy penalties ⋮ Scheduling in a two-machine flowshop for the minimization of the mean absolute deviation from a common due date ⋮ MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK ⋮ Single-machine scheduling with a common due window ⋮ On the general solution for a class of early/tardy problems ⋮ Capacitated two-parallel machines scheduling to minimize sum of job completion times ⋮ Heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties ⋮ Scheduling in a two-machine flowshop with batch processing machine(s) for earliness/tardiness measure under a common due date ⋮ Minmax earliness-tardiness costs with unit processing time jobs ⋮ Scheduling of storage/retrieval orders under a just-in-time environment ⋮ A recovering beam search algorithm for the single machine just-in-time scheduling problem ⋮ On scheduling around large restrictive common due windows ⋮ Single machine weighted earliness-tardiness penalty problem with a common due date ⋮ Minimizing the Earliness and Tardiness Cost of a Sequence of Tasks on a Single Machine ⋮ Efficient neighborhood search for the one-machine earliness-tardiness scheduling problem ⋮ Scheduling with a common due-window: polynomially solvable cases ⋮ Stochastic single machine scheduling with an exponentially distributed due date ⋮ Minimizing total completion time and total deviation of job completion times from a restrictive due-date ⋮ Permutation flow shop scheduling with earliness and tardiness penalties ⋮ Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates ⋮ On the complexity of the single machine scheduling problem minimizing total weighted delay penalty ⋮ Minimizing total earliness and tardiness for common due date single-machine scheduling with an unavailability interval ⋮ Heuristic and exact algorithms for the two-machine just in time job shop scheduling problem ⋮ Single-machine common due date total earliness/tardiness scheduling with machine unavailability ⋮ Integrated production and transportation scheduling problem under nonlinear cost structures ⋮ Just-in-time scheduling problem with affine idleness cost ⋮ Strong NP-hardness of minimizing total deviation with generalized and periodic due dates ⋮ Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty ⋮ Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs ⋮ BEAM SEARCH HEURISTICS FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH LINEAR EARLINESS AND QUADRATIC TARDINESS COSTS ⋮ \(V\)-shape property for job sequences that minimize the expected completion time variance ⋮ A note on the complexity of single-machine scheduling with a common due date, earliness-tardiness, and batch delivery costs ⋮ A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems ⋮ Scheduling with batch setup times and earliness-tardiness penalties ⋮ A note on minimizing the weighted sum of tardy and early completion penalties in a single machine: A case of small common due date ⋮ Scheduling about a common due date with job-dependent asymmetric earlines and tardiness penalties ⋮ Multicriteria scheduling ⋮ Punctuality and idleness in just-in-time scheduling ⋮ Single machine earliness-tardiness scheduling with resource-dependent release dates ⋮ A filtered beam search method for the \(m\)-machine permutation flowshop scheduling problem minimizing the earliness and tardiness penalties and the waiting time of the jobs ⋮ Determination of fault-tolerant fabric-cutting schedules in a just-in-time apparel manufacturing environment ⋮ On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date ⋮ A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems ⋮ A survey of the state-of-the-art of common due date assignment and scheduling research ⋮ Unary NP-hardness of minimizing the total deviation with generalized or assignable due dates ⋮ Scheduling with generalized and periodic due dates under single- and two-machine environments ⋮ Minimizing earliness and tardiness costs in stochastic scheduling

This page was built for publication: Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date