On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems

DOI10.1007/s10107-006-0013-4zbMath1205.90133OpenAlexW2137215422MaRDI QIDQ985311

Yunpeng Pan, Shi, Leyuan

Publication date: 21 July 2010

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0013-4

zbMATH Keywords

schedulingcombinatorial optimizationtime-indexing

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (16)

Scheduling lower bounds via AND subset sum ⋮ Weighted tardiness for the single machine scheduling problem:an examination of precedence theorem productivity ⋮ An exact extended formulation for the unrelated parallel machine total weighted completion time problem ⋮ Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems ⋮ A space-indexed formulation of packing boxes into a larger box ⋮ An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems ⋮ Exploiting Packing Components in General-Purpose Integer Programming Solvers ⋮ Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems ⋮ Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates ⋮ Iterated local search and very large neighborhoods for the parallel-machines total tardiness 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 Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems ⋮ A new model for the preemptive earliness-tardiness scheduling problem ⋮ Time-indexed formulations for scheduling chains on a single machine: an application to airborne radars ⋮ An exact algorithm for the precedence-constrained single-machine scheduling problem

Uses Software

• OR-Library
• JOBSHOP

Cites Work

• Unnamed Item
• Preemption in single machine earliness/tardiness scheduling
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• A time indexed formulation of non-preemptive single machine scheduling problems
• A survey of algorithms for the single machine total weighted tardiness scheduling 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.
• The one-machine problem with earliness and tardiness penalties
• Approximation Techniques for Average Completion Time Scheduling
• An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem
• Near-Optimal Solutions of Large-Scale Single-Machine Scheduling Problems
• Time-Indexed Formulations and the Total Weighted Tardiness Problem
• A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
• A Computational Study of the Job-Shop Scheduling Problem
• Coordinating Aggregate and Detailed Scheduling Decisions in the One-Machine Job Shop: Part I. Theory
• Disjunctive Programming
• Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
• Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm

This page was built for publication: On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems