A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties

DOI10.1016/j.apm.2015.01.069zbMath1443.90041OpenAlexW2074384335MaRDI QIDQ2285347

Nasser Salmasi, Taha Keshavarz, Savelsbergh, Martin W. P.

Publication date: 8 January 2020

Published in: Applied Mathematical Modelling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apm.2015.01.069

zbMATH Keywords

branch-and-bound algorithmLagrangian relaxationgroup schedulingtime-indexed formulationsequence-dependent setup timeminimization of earliness and tardiness

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35) Mathematical modeling or simulation for problems pertaining to operations research and mathematical programming (90-10)

Related Items (9)

Optimal due date assignment without restriction and convex resource allocation in group technology scheduling ⋮ Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times ⋮ When serial batch scheduling involves parallel batching decisions: a branch and price scheme ⋮ On optimal due date assignment without restriction and resource allocation in group technology scheduling ⋮ Just‐in‐time scheduling problem with due windows and release dates for precast bridge girders ⋮ Two-stage assembly scheduling problem for minimizing total tardiness with setup times ⋮ A mathematical model and two-stage heuristic for hot rolling scheduling in compact strip production ⋮ Decision model for the customer order decoupling point considering order insertion scheduling with capacity and time constraints in logistics service supply chain ⋮ Accelerated dynamic programming algorithms for a car resequencing problem in automotive paint shops

Uses Software

• Tabu search

Cites Work

• An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times
• Single-machine group scheduling with general deterioration and learning effects
• Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems
• A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem
• A hybrid genetic algorithm with dominance properties for single machine scheduling with dependent penalties
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• Single machine scheduling with batch set-up times to minimize maximum lateness
• Earliness-tardiness scheduling with setup considerations
• Single machine scheduling with symmetric earliness and tardiness penalties
• Batch scheduling to minimize total completion time
• Scheduling with batching: A review
• An exact algorithm for single-machine scheduling without machine idle time
• Branch and bound algorithms for single machine scheduling with batching to minimize the number of late jobs
• Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates
• Near-Optimal Solutions of Large-Scale Single-Machine Scheduling Problems
• Time-Indexed Formulations and the Total Weighted Tardiness Problem
• New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling
• An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• On the Complexity of Scheduling with Batch Setup Times
• A Branch-and-Bound Algorithm for Single-Machine Earliness–Tardiness Scheduling with Idle Time
• Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
• Optimal timing schedules in earliness-tardiness single machine sequencing
• Scheduling

This page was built for publication: A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties