Formulating the single machine sequencing problem with release dates as a mixed integer program
From MaRDI portal
Publication:909575
DOI10.1016/0166-218X(90)90104-KzbMath0694.90060DBLPjournals/dam/DyerW90OpenAlexW2159152246WikidataQ56324122 ScholiaQ56324122MaRDI QIDQ909575
Martin Dyer, Laurence A. Wolsey
Publication date: 1990
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(90)90104-k
single machinesequencinglower boundsrelease datessequence of relaxationsweighted sum of completion timesweighted sum of start times
Related Items (66)
Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs ⋮ Mixed integer formulations using natural variables for single machine scheduling around a common due date ⋮ Preemption in single machine earliness/tardiness scheduling ⋮ Exact algorithms for single-machine scheduling with time windows and precedence constraints ⋮ Exact and heuristic algorithms for the parallel machine total completion time scheduling problem with dual resources, ready times, and sequence-dependent setup times ⋮ Order acceptance and scheduling problems in two-machine flow shops: new mixed integer programming formulations ⋮ A mixed integer programming approach for the single machine problem with unequal release dates ⋮ An Exact Decomposition Approach for the Real-Time Train Dispatching Problem ⋮ An exact extended formulation for the unrelated parallel machine total weighted completion time problem ⋮ 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 ⋮ Unrelated parallel machine scheduling with new criteria: complexity and models ⋮ Minimizing late jobs in the general one machine scheduling problem ⋮ On the mass COVID-19 vaccination scheduling problem ⋮ Single machine batch scheduling with release times and delivery costs ⋮ 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 ⋮ A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem ⋮ An improved decision support model for scheduling production in an engineer-to-order manufacturer ⋮ Optimal Mechanism Design for a Sequencing Problem with Two-Dimensional Types ⋮ An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem ⋮ 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 ⋮ On the approximability of average completion time scheduling under precedence constraints. ⋮ Polytopes related to interval vectors and incidence matrices ⋮ A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time ⋮ A linear programming-based method for job shop scheduling ⋮ A time-indexed LP-based approach for min-sum job-shop problems ⋮ A Noncompact Formulation for Job-Shop Scheduling Problems in Traffic Management ⋮ Reducibility among single machine weighted completion time scheduling problems ⋮ A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching ⋮ The CLWS heuristic for single machine scheduling problem ⋮ On the strength of time-indexed formulations for the resource-constrained project scheduling problem ⋮ Lagrangian bounds for just-in-time job-shop scheduling ⋮ Approximation algorithms for scheduling problems with a modified total weighted tardiness objective ⋮ A supermodular relaxation for scheduling with release dates ⋮ Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds ⋮ Scheduling with release dates on a single machine to minimize total weighted completion time ⋮ Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems ⋮ A time indexed formulation of non-preemptive single machine scheduling problems ⋮ An integer programming approach to optimal basic block instruction scheduling for single-issue processors ⋮ The single machine weighted mean squared deviation problem ⋮ Exact solution of the single-machine scheduling problem with periodic maintenances and sequence-dependent setup times ⋮ Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem ⋮ Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms ⋮ Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates ⋮ Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates ⋮ Designing PTASs for MIN-SUM scheduling problems ⋮ An exact algorithm for single-machine scheduling without machine idle time ⋮ A family of inequalities valid for the robust single machine scheduling polyhedron ⋮ On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation ⋮ On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems ⋮ Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates ⋮ A job shop distributed scheduling based on Lagrangian relaxation to minimise total completion time ⋮ On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems ⋮ 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 ⋮ Structure of a simple scheduling polyhedron ⋮ Optimal solutions for a dock assignment problem with trailer transportation ⋮ Deterministic job-shop scheduling: Past, present and future ⋮ The single-processor scheduling problem with time restrictions: complexity and related problems ⋮ Hybrid Flow Shop Scheduling: Heuristic Solutions and LP-Based Lower Bounds ⋮ A cutting plane algorithm for MV portfolio selection model ⋮ A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems ⋮ A cutting plane algorithm for a single machine scheduling problem ⋮ The power of \(\alpha\)-points in preemptive single machine scheduling.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An algorithm for single machine sequencing with deadlines to minimize total weighted completion time
- An algorithm for single machine sequencing with release dates to minimize total weighted completion time
- Minimizing Weighted Completion Times with Deadlines
- On the facial structure of scheduling polyhedra
- A Sequencing Problem with Release Dates and Clustered Jobs
This page was built for publication: Formulating the single machine sequencing problem with release dates as a mixed integer program
