Time-Indexed Formulations for Machine Scheduling Problems: Column Generation

DOI10.1287/IJOC.12.2.111.11896zbMath1034.90004OpenAlexW2039823842MaRDI QIDQ4427325

Savelsbergh, Martin W. P., J. M. van den Akker, Cor A. J. Hurkens

Publication date: 2000

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

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35)

Related Items (74)

Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs ⋮ Layered graph approaches for combinatorial optimization problems ⋮ Dynamic resource allocation: a flexible and tractable modeling framework ⋮ Scheduling evacuation operations ⋮ Consistency Cuts for Dantzig-Wolfe Reformulations ⋮ Order acceptance and scheduling problems in two-machine flow shops: new mixed integer programming formulations ⋮ Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals ⋮ A branch-and-price algorithm for scheduling of deteriorating jobs and flexible periodic maintenance on a single machine ⋮ Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems ⋮ Integrated Charge Batching and Casting Width Selection at Baosteel ⋮ Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling ⋮ Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time ⋮ A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry ⋮ Unrelated parallel machine scheduling with new criteria: complexity and models ⋮ A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness ⋮ Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date ⋮ Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems ⋮ An improved decision support model for scheduling production in an engineer-to-order manufacturer ⋮ Simultaneous scheduling of replacement and repair of common components in operating systems. A multi-objective mathematical optimization model ⋮ An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem ⋮ A branch and price solution approach for order acceptance and capacity planning in make-to-order operations ⋮ On the exact solution of a large class of parallel machine scheduling problems ⋮ A branch-and-price-and-cut algorithm for operating room scheduling under human resource constraints ⋮ Integrated production and delivery scheduling for multi-factory supply chain with stage-dependent inventory holding cost ⋮ A global constraint for total weighted completion time for unary resources ⋮ A stabilized column generation scheme for the traveling salesman subtour problem ⋮ A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time ⋮ A 0-1 integer linear programming approach to schedule outages of nuclear power plants ⋮ Mixed-integer programming models for optimal constellation scheduling given cloud cover uncertainty ⋮ A time-indexed LP-based approach for min-sum job-shop problems ⋮ Column generation for extended formulations ⋮ A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching ⋮ An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems ⋮ Branch-and-price approach for the multi-skill project scheduling problem ⋮ Column generation heuristics for multiple machine, multiple orders per job scheduling problems ⋮ Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation ⋮ Arc flow formulations based on dynamic programming: theoretical foundations and applications ⋮ Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems ⋮ Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems ⋮ A branch and price algorithm to solve the integrated production planning and scheduling in bulk ports ⋮ Changeover formulations for discrete-time mixed-integer programming scheduling models ⋮ Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem ⋮ Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates ⋮ Decomposition and dynamic cut generation in integer linear programming ⋮ Shipment planning at oil refineries using column generation and valid inequalities ⋮ A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes ⋮ Robust branch-and-cut-and-price for the capacitated vehicle routing problem ⋮ Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment ⋮ An exact algorithm for single-machine scheduling without machine idle time ⋮ A generic view of Dantzig--Wolfe decomposition in mixed integer programming ⋮ Scheduling projects with labor constraints ⋮ Earliness-tardiness scheduling with setup considerations ⋮ A Lagrangian heuristic for satellite range scheduling with resource constraints ⋮ On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems ⋮ On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems ⋮ Valid inequalities for a time-indexed formulation ⋮ A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties ⋮ A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems ⋮ Optimal solutions for a dock assignment problem with trailer transportation ⋮ The single-processor scheduling problem with time restrictions: complexity and related problems ⋮ Using short-term memory to minimize the weighted number of late jobs on a single machine. ⋮ Multi-Product Inventory Logistics Modeling in the Process Industries ⋮ The asymmetric traveling salesman problem with replenishment arcs ⋮ Non-binary quantified CSP: Algorithms and modelling ⋮ Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers ⋮ The vehicle routing problem with time windows and temporal dependencies ⋮ A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems ⋮ Time-indexed formulations for scheduling chains on a single machine: an application to airborne radars ⋮ A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times ⋮ An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems ⋮ Resource-Constrained Scheduling with Non-constant Capacity and Non-regular Activities ⋮ Two alternative models for farm management: Discrete versus continuous time horizon ⋮ Parallel machine scheduling with additional resources: notation, classification, models and solution methods ⋮ On a fix-and-relax framework for a class of project scheduling problems

This page was built for publication: Time-Indexed Formulations for Machine Scheduling Problems: Column Generation