A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems

DOI10.1287/ijoc.2015.0661zbMath1338.90159OpenAlexW2292895089MaRDI QIDQ2806861

Riley Clement, Hamish Waterer, Natashia Boland

Publication date: 19 May 2016

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2015.0661

zbMATH Keywords

single machine schedulingmixed-integer linear programmingtime indexed formulations

Mathematics Subject Classification ID

Mixed integer programming (90C11) Deterministic scheduling theory in operations research (90B35)

Related Items (9)

Layered graph approaches for combinatorial optimization problems ⋮ An iterative time‐bucket refinement algorithm for a high‐resolution resource‐constrained project scheduling problem ⋮ An improved decision support model for scheduling production in an engineer-to-order manufacturer ⋮ Exact solution of the single-machine scheduling problem with periodic maintenances and sequence-dependent setup times ⋮ Perspectives on integer programming for time-dependent models ⋮ Modeling single machine preemptive scheduling problems for computational efficiency ⋮ A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems ⋮ A matheuristic for the generalized order acceptance and scheduling problem ⋮ Corrigendum to “A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems,” INFORMS Journal on Computing 28(1):14–30, 2016

Uses Software

• CPLEX
• OR-Library
• bc-prod

Cites Work

• Unnamed Item
• On solving continuous-time dynamic network flows
• Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems
• 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
• A survey of algorithms for the single machine total weighted tardiness scheduling problem
• The relation of time indexed formulations of single machine scheduling problems to the node packing problem
• An improved branch and bound algorithm for single machine scheduling with deadlines to minimize total weighted completion time.
• A polyhedral approach to single-machine scheduling problems.
• Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates
• The fleet assignment problem: Solving a large scale integer program
• Scheduling jobs of equal length: Complexity, facets and computational results
• An exact algorithm for single-machine scheduling without machine idle time
• A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
• A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems
• A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows
• An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems
• 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
• Modelling Practical Lot-Sizing Problems as Mixed-Integer Programs
• bc — prod: A Specialized Branch-and-Cut System for Lot-Sizing Problems
• A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
• On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation
• Quickest Flows Over Time

This page was built for publication: A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems