A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem

DOI10.1007/S10951-007-0048-2MaRDI QIDQ835579zbMATH OpenOpenAlexFDO

Authors Francis Sourd, S. Kedad-Sidhoum

Publication date 28 August 2009

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10951-007-0048-2

zbMATH Keywords

branch-and-boundearliness-tardinessLagrangean relaxationone-machine scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Interior-point methods (90C51)

Recommendations

• A branch-and-bound algorithm for the single machine earliness and tardiness scheduling problem
• A Branch-and-Bound Algorithm for Single-Machine Earliness–Tardiness Scheduling with Idle Time
• The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm
• New exact algorithms for one-machine earliness-tardiness scheduling
• A branch-and-bound algorithm for single machine scheduling with quadratic earliness and tardiness penalties

Cites work

• A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
• A branch and bound approach for single machine scheduling with earliness and tardiness penalties
• A branch and bound procedure to minimize mean absolute lateness on a single processor
• A Branch-and-Bound Algorithm for Single-Machine Earliness–Tardiness Scheduling with Idle Time
• A branch-and-bound algorithm for the single machine earliness and tardiness scheduling problem
• A dual algorithm for the one-machine scheduling problem
• A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time
• A recovering beam search algorithm for the single machine just-in-time scheduling problem
• A survey of the state-of-the-art of common due date assignment and scheduling research
• A time indexed formulation of non-preemptive single machine scheduling problems
• An algorithm for single machine sequencing with deadlines to minimize total weighted completion time
• An exact approach to early/tardy scheduling with release dates
• Dynasearch for the earliness-tardiness scheduling problem with release dates and setup constraints
• Efficient neighborhood search for the one-machine earliness-tardiness scheduling problem
• scientific article; zbMATH DE number 40477 (Why is no real title available?)
• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates
• Machine scheduling with earliness, tardiness and non-execution penalties
• Minimizing mean tardiness and earliness in single-machine scheduling problems with unequal due dates
• Minimizing weighted earliness and tardiness penalties in single-machine scheduling with idle time permitted
• Multicriteria scheduling
• Near-optimal solutions of large-scale single-machine scheduling problems
• One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
• Optimal timing of a sequence of tasks with general completion costs
• Preemption in single machine earliness/tardiness scheduling
• Project scheduling with resource constraints: A branch and bound approach. Note by Frederik Kaefer
• Scheduling identical parallel machines to minimize total weighted completion time
• Scheduling with common due date, earliness and tardiness penalties for multimachine problems: a survey
• Sequencing with Earliness and Tardiness Penalties: A Review
• Single-machine scheduling of unit-time jobs with earliness and tardiness penalties
• Solving project scheduling problems by minimum cut computations
• Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties
• The continuous assignment problem and its application to preemptive and non-preemptive scheduling with irregular cost functions
• The one-machine problem with earliness and tardiness penalties
• Using short-term memory to minimize the weighted number of late jobs on a single machine.

Cited in

(39)

• The one-machine just-in-time scheduling problem with preemption
• A new model for the preemptive earliness-tardiness scheduling problem
• Lagrangian domain reductions for the single machine earliness-tardiness problem with release dates
• Time-indexed formulations for scheduling chains on a single machine: an application to airborne radars
• A neighbourhood scheme with a compressed solution space for the early/tardy scheduling problem
• A branch-and-bound algorithm for the single machine earliness and tardiness scheduling problem
• An exact algorithm for the bi-objective timing problem
• Integrated production and delivery scheduling for multi-factory supply chain with stage-dependent inventory holding cost
• Scheduling with time-dependent discrepancy times
• Earliness-tardiness scheduling with setup considerations
• Improved heuristics for the early/tardy scheduling problem with no idle time
• Minimizing weighted earliness-tardiness on a single machine with a common due date using quadratic models
• \textit{Branch} \& \textit{memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees
• Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers
• On the exact solution of a large class of parallel machine scheduling problems
• A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties
• A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems
• Fast neighborhood search for the single machine earliness-tardiness scheduling problem
• A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
• The one-machine problem with earliness and tardiness penalties
• New exact algorithms for one-machine earliness-tardiness scheduling
• An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem
• Optimal restricted due date assignment in scheduling
• Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties
• Improving schedule stability in single-machine rescheduling for new operation insertion
• Solving the earliness tardiness scheduling problem by DC programming and DCA
• New dominance rules and exploration strategies for the \(1|r _{i}|\sum U _{i }\) scheduling problem
• scientific article; zbMATH DE number 1051033 (Why is no real title available?)
• A Branch-and-Bound Algorithm for Single-Machine Earliness–Tardiness Scheduling with Idle Time
• A note on ‘Single-machine scheduling for minimizing total cost with identical, asymmetrical earliness and tardiness penalties’
• On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation
• The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm
• Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems
• Just‐in‐time scheduling problem with due windows and release dates for precast bridge girders
• Just-in-time scheduling problem with affine idleness cost
• A hybrid genetic algorithm with dominance properties for single machine scheduling with dependent penalties
• A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem
• Minimizing total earliness and tardiness on a single machine using a hybrid heuristic
• Scheduling with returnable containers

This page was built for publication: A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q835579)