Publication:3824090

{{DISPLAYTITLE:One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties

DOI10.1287/moor.13.2.330zbMath0671.90033OpenAlexW1992198745MaRDI QIDQ3824090

Michael R. Garey, Gordon Wilfong, Robert Endre Tarjan

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1287/moor.13.2.330

zbMATH Keywords

polynomial time algorithm NP-hard nonpreemptive scheduling maximum earliness total earliness Two objectives

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Related Items

Unnamed Item, An empirical study of policies to integrate reactive scheduling and control in just-in-time job shop environments, A dual criteria sequencing problem with earliness and tardiness penalties, Minimizing the sum of completion times on a single machine with health index and flexible maintenance operations, Boundary Labeling with Octilinear Leaders, AN EXACT APPROACH FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH LINEAR EARLY AND QUADRATIC TARDY PENALTIES, Recent progress of local search in handling the time window constraints of the vehicle routing problem, Recent progress of local search in handling the time window constraints of the vehicle routing problem, Minmax earliness-tardiness costs with unit processing time jobs, Algoritmo de programação de máquinas individuais com penalidades distintas de adiantamento e atraso, Scheduling with periodic availability constraints and irregular cost functions, Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs, BEAM SEARCH HEURISTICS FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH LINEAR EARLINESS AND QUADRATIC TARDINESS COSTS, An empirical study of policies to integrate reactive scheduling and control in just-in-time job shop environments, Application of genetic algorithm to stochastic single machine scheduling problem with earliness and tardiness costs, The stochastic single machine scheduling problem with earliness and tardiness costs, Scheduling with monotonous earliness and tardiness penalties, A note on one-processor scheduling with asymmetric earliness and tardiness penalties, Minimizing variation of production rates in just-in-time systems: A survey, Preemption in single machine earliness/tardiness scheduling, A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem, Machine scheduling with earliness, tardiness and non-execution penalties, Genetic search with dynamic operating disciplines, A comment on ``A simple sequencing algorithm for mixed-model assembly lines in just-in-time production systems, Minimizing the sum of absolute deviations about a common due date for the two-machine flow shop problem, Single machine \(\text{MAD}/T_{\max}\) problem with a common due date, Inverse chromatic number problems in interval and permutation graphs, Single machine rescheduling for new orders with maximum lateness minimization, Minimizing flowtime and missed due-dates in single-machine sequencing, Minmax scheduling with job-classes and earliness-tardiness costs, Complexity of two dual criteria scheduling problems, Iterated local search based on multi-type perturbation for single-machine earliness/tardiness scheduling, Algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties, Improving schedule stability in single-machine rescheduling for new operation insertion, A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights, A comparison of lower bounds for the single-machine early/tardy problem, On the existence of schedules that are near-optimal for both makespan and total weighted completion time, Focused simulated annealing search: An application to job shop scheduling, An improved earliness--tardiness timing algorithm, Minimizing total earliness and tardiness on a single machine using a hybrid heuristic, Lower bounds for minimizing total completion time in a two-machine flow shop, Modelling and solving the production rate variation problem (PRVP), A fixed interval due-date scheduling problem with earliness and due-date costs, Just-in-time single-batch-processing machine scheduling, Just-in-Time Scheduling with Equal-Size Jobs, Just-in-Time Scheduling in Modern Mass Production Environment, A composite heuristic for the single machine early/tardy job scheduling problem., Scheduling with returnable containers, Complexity results for an integrated single machine scheduling and outbound delivery problem with fixed sequence, The complexity of two-job shop problems with multi-purpose unrelated machines., Scheduling with time-dependent discrepancy times, Total completion time minimization in two-machine flow shop scheduling problems with a fixed job sequence, Dynamic programming approach to the single-machine sequencing problem with different due-dates, Scheduling jobs with a V-shaped time-dependent processing time, Earliness and tardiness scheduling problems on a batch processor, 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, Equivalence of mean flow time problems and mean absolute deviation problems, Multicriteria models for just-in-time scheduling, Minimizing the maximal ergonomic burden in intra-hospital patient transportation, Exponential neighborhood search for a parallel machine scheduling problem, Scheduling around a small common due date, Efficient algorithms for machine scheduling problems with earliness and tardiness penalties, Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time, An iterated local search algorithm for the vehicle routing problem with convex time penalty functions, Parallel-machine scheduling under potential disruption, Single machine scheduling with family setups to minimize total earliness and tardiness, An iterated local search algorithm for the time-dependent vehicle routing problem with time windows, Supply planning models for a remanufacturer under just-in-time manufacturing environment with reverse logistics, Preemptive multiprocessor order scheduling to minimize total weighted flowtime, Capacitated two-parallel machines scheduling to minimize sum of job completion times, A note on a due-date assignment on a two-machine flow-shop, Boundary labeling with octilinear leaders, A recovering beam search algorithm for the single machine just-in-time scheduling problem, Multicriteria scheduling problems: a survey, 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, Unnamed Item, An algorithm for insertion of idle time in the single-machine scheduling problem with convex cost functions, Optimal timing of a sequence of tasks with general completion costs, Earliness-tardiness scheduling with setup considerations, Minimizing the earliness--tardiness costs on a single machine, A job shop distributed scheduling based on Lagrangian relaxation to minimise total completion time, Algorithms for a class of single-machine weighted tardiness and earliness problems, Single-machine scheduling with an external resource, Single-machine common due date total earliness/tardiness scheduling with machine unavailability, A functional equation that arises in problems of scheduling with priorities and lateness/earliness penalties, The one-machine just-in-time scheduling problem with preemption, A genetic algorithm approach for the single machine scheduling problem with linear earliness and quadratic tardiness penalties, The single-processor scheduling problem with time restrictions: complexity and related problems, The transportation problem with exclusionary side constraints, Single-machine scheduling with time windows and earliness/tardiness penalties, A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems, Scheduling with batch setup times and earliness-tardiness penalties, Non-approximability of just-in-time scheduling, A branch and bound procedure to minimize mean absolute lateness on a single processor, Vehicle scheduling with combinable delivery and pickup operations, Earliness and tardiness single machine scheduling with proportional weights, A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems, Multicriteria scheduling, Punctuality and idleness in just-in-time scheduling, Time-indexed formulations for scheduling chains on a single machine: an application to airborne radars, An adaptive TS approach to JIT sequencing with variable processing times and sequence-dependent setups, Single machine earliness-tardiness scheduling with resource-dependent release dates, Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties, On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates, A heuristic for single machine scheduling with early and tardy costs, PERT scheduling with convex cost functions., A survey of the state-of-the-art of common due date assignment and scheduling research, Parallel machine scheduling to minimize costs for earliness and number of tardy jobs, Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard., Single machine flow-time scheduling with scheduled maintenance, Single machine scheduling with symmetric earliness and tardiness penalties, Scheduling two agent task chains with a central selection mechanism, Minimizing earliness and tardiness costs in stochastic scheduling