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

DOI10.1016/j.ejor.2006.05.052zbMath1146.90030OpenAlexW2060346111MaRDI QIDQ2482802

Yasmin Rios Solis, Safia Kedad-Sidhoum, Francis Sourd

Publication date: 24 April 2008

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2006.05.052

zbMATH Keywords

earliness-tardinesslower boundsjust-in-timeparallel machine schedulingIP time-indexed formulation

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem, Fast neighborhood search for the single machine earliness-tardiness scheduling problem, Minimizing total tardiness and earliness on unrelated parallel machines with controllable processing times, Minimizing weighted earliness-tardiness on parallel machines using hybrid metaheuristics, An exact extended formulation for the unrelated parallel machine total weighted completion time problem, Scheduling preparation of doses for a chemotherapy service, Just-in-time single-batch-processing machine scheduling, Capacity allocation in a service system with preferred service completion times, Dynamic scheduling of patients in emergency departments, Scheduling Unrelated Parallel Machines with Sequence Dependent Setup Times and Weighted Earliness–Tardiness Minimization, Exponential neighborhood search for a parallel machine scheduling problem, Scheduling with earliness-tardiness penalties and parallel machines, Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems, An intelligent water drop algorithm to identical parallel machine scheduling with controllable processing times: a just-in-time approach, A multi-agent system for the weighted earliness tardiness parallel machine problem, Online scheduling of malleable parallel jobs with setup times on two identical machines, A Lagrangian heuristic for satellite range scheduling with resource constraints, A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties, Optimal solutions for a dock assignment problem with trailer transportation, Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers, A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems, Lagrangian domain reductions for the single machine earliness-tardiness problem with release dates, A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times

Uses Software

• SolvOpt

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Preemption in single machine earliness/tardiness scheduling
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems
• A time indexed formulation of non-preemptive single machine scheduling problems
• Parallel machine scheduling with earliness--tardiness penalties and additional resource con\-straints.
• An implementation of Shor's \(r\)-algorithm
• A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem
• Optimal timing of a sequence of tasks with general completion costs
• Using short-term memory to minimize the weighted number of late jobs on a single machine.
• On the \(k\)-coloring of intervals
• The one-machine problem with earliness and tardiness penalties
• Efficient neighborhood search for the one-machine earliness-tardiness scheduling problem
• Multicriteria scheduling
• Multicriteria scheduling problems: a survey
• The Continuous Assignment Problem and Its Application to Preemptive and Non-Preemptive Scheduling with Irregular Cost Functions
• An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems
• Solving Project Scheduling Problems by Minimum Cut Computations
• Generating Experimental Data for Computational Testing with Machine Scheduling Applications
• Coordinating Aggregate and Detailed Scheduling Decisions in the One-Machine Job Shop: Part I. Theory
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Improved Algorithms for Bipartite Network Flow
• A Branch-and-Bound Algorithm for Single-Machine Earliness–Tardiness Scheduling with Idle Time
• Time-Indexed Formulations for Machine Scheduling Problems: Column Generation