A time indexed formulation of non-preemptive single machine scheduling problems

DOI10.1007/BF01586059zbMath0768.90041OpenAlexW2060552317MaRDI QIDQ1196724

Laurence A. Wolsey, Jorge Pinho de Sousa

Publication date: 16 January 1993

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

Full work available at URL: https://doi.org/10.1007/bf01586059

zbMATH Keywords

branch-and-boundvalid inequalitiesrelease datesweighted tardinesscutting plane algorithmweighted completion timesdead linesnon-preemptive, single machine scheduling

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (71)

Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs ⋮ Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem ⋮ Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem ⋮ A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem ⋮ Scheduling evacuation operations ⋮ Network construction problems with due dates ⋮ Exact and heuristic algorithms for the parallel machine total completion time scheduling problem with dual resources, ready times, and sequence-dependent setup times ⋮ Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties ⋮ A mixed integer programming approach for the single machine problem with unequal release dates ⋮ Bicriteria scheduling problem for unrelated parallel machines with release dates ⋮ Integrating restoration and scheduling decisions for disrupted interdependent infrastructure systems ⋮ Scheduling jobs of equal length: Complexity, facets and computational results ⋮ 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 ⋮ Minimizing total earliness and tardiness on a single machine using a hybrid heuristic ⋮ Unrelated parallel machine scheduling with new criteria: complexity and models ⋮ An exact framework for the discrete parallel machine scheduling location problem ⋮ Just-in-time single-batch-processing machine scheduling ⋮ Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date ⋮ An exact algorithm for the service network design problem with hub capacity constraints ⋮ 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 ⋮ Novel formulations and modeling enhancements for the dynamic berth allocation problem ⋮ An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem ⋮ Resource leveling in a machine environment ⋮ A composite heuristic for the single machine early/tardy job scheduling problem. ⋮ Mathematical model applied to single-track line scheduling problem in Brazilian railways ⋮ A space-indexed formulation of packing boxes into a larger box ⋮ A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time ⋮ Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines ⋮ A Branch-and-Bound Algorithm for the Prize-Collecting Single-Machine Scheduling Problem with Deadlines and Total Tardiness Minimization ⋮ Lateness Minimization in Pairwise Connectivity Restoration Problems ⋮ On the strength of time-indexed formulations for the resource-constrained project scheduling problem ⋮ An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems ⋮ Exploiting Packing Components in General-Purpose Integer Programming Solvers ⋮ Arc flow formulations based on dynamic programming: theoretical foundations and applications ⋮ A new approach to computing optimal schedules for the job-shop scheduling problem ⋮ A branch and cut heuristic for a runway scheduling problem ⋮ Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems ⋮ Changeover formulations for discrete-time mixed-integer programming scheduling models ⋮ The single machine weighted mean squared deviation problem ⋮ Optimal spacecraft support in remote sensing missions ⋮ Restoring infrastructure systems: an integrated network design and scheduling (INDS) problem ⋮ 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 ⋮ An exact approach for scheduling jobs with regular step cost functions on a single machine ⋮ An exact algorithm for single-machine scheduling without machine idle time ⋮ Scheduling projects with labor constraints ⋮ 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 ⋮ Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates ⋮ On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems ⋮ New MIP model for multiprocessor scheduling problem with communication delays ⋮ A time-dependent multiple criteria single-machine scheduling problem ⋮ Interval-indexed formulation based heuristics for single machine total weighted tardiness problem ⋮ Modeling single machine preemptive scheduling problems for computational efficiency ⋮ A Bucket Indexed Formulation for Nonpreemptive Single Machine Scheduling Problems ⋮ On stochastic dynamic programming for solving large-scale planning problems under uncertainty ⋮ Optimal solutions for a dock assignment problem with trailer transportation ⋮ The single-processor scheduling problem with time restrictions: complexity and related problems ⋮ MIP modelling of changeovers in production planning and scheduling problems ⋮ A cutting plane algorithm for MV portfolio selection model ⋮ Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers ⋮ Polyhedral Results and Branch-and-Cut for the Resource Loading Problem ⋮ Scheduling interfering job sets on parallel machines ⋮ 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 ⋮ LP models for bin packing and cutting stock problems ⋮ A cutting plane algorithm for a single machine scheduling problem ⋮ Two alternative models for farm management: Discrete versus continuous time horizon ⋮ On a fix-and-relax framework for a class of project scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Formulating the single machine sequencing problem with release dates as a mixed integer program
• Single machine scheduling to minimize weighted sum of completion times with secondary criterion - A branch and bound approach
• The one-machine sequencing problem
• 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
• Project scheduling with resource constraints: A branch and bound approach. Note by Frederik Kaefer
• A mixed integer programming model for scheduling orders in a steel mill
• Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints
• Minimizing Weighted Completion Times with Deadlines
• The Shifting Bottleneck Procedure for Job Shop Scheduling
• Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
• Resource-Constrained Project Scheduling with Time-Resource Tradeoffs: The Nonpreemptive Case
• Facets of the knapsack polytope
• Minimizing Total Costs in One-Machine Scheduling
• Scheduling a Project to Maximize Its Present Value: A Zero-One Programming Approach
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• The Schedule-Sequencing Problem
• On the N-Job One-Machine, Sequence-Independent Scheduling Problem with Tardiness Penalties: A Branch-Bound Solution

This page was built for publication: A time indexed formulation of non-preemptive single machine scheduling problems