Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem

DOI10.1007/BF02085647zbMath0812.90067OpenAlexW2013157254MaRDI QIDQ1339135

Youngho Lee, Hanif D. Sherali

Publication date: 1 December 1994

Published in: Annals of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

Lagrangian relaxationbranch-and-boundlower and upper boundsbranch-and-cutLagrangian dual formulationmachine downtimetime-window job availabilitytotal weighted flow timeunrelated machine scheduling

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Deterministic scheduling theory in operations research (90B35)

Related Items

RLT insights into lift-and-project closures ⋮ A new approximation algorithm for unrelated parallel machine scheduling with release dates ⋮ Interleaving two-phased jobs on a single machine ⋮ MIP modelling of changeovers in production planning and scheduling problems ⋮ Scheduling target illuminators in naval battle-group anti-air warfare ⋮ Unrelated parallel machine scheduling with multiple time windows: an application to Earth observation satellite scheduling ⋮ Two alternative models for farm management: Discrete versus continuous time horizon

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The generalized assignment problem: Valid inequalities and facets
• (1,k)-configuration facets for the generalized assignment problem
• A block approach for single-machine scheduling with release dates and due dates
• A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems
• A time indexed formulation of non-preemptive single machine scheduling problems
• Easily Computable Facets of the Knapsack Polytope
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Multiprocessor Scheduling of Unit-Time Jobs with Arbitrary Release Times and Deadlines
• An improved branching scheme for the branch and bound procedure of schedulingnjobs onmparallel machines to minimize total weighted flowtime
• Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• On scheduling with ready-times, due-dates and vacations
• A Multiplier Adjustment Approach for the Set Partitioning Problem
• An Algorithm for Large Set Partitioning Problems
• Facet of regular 0–1 polytopes
• Two-Processor Scheduling with Start-Times and Deadlines
• A Fast Algorithm for Multiprocessor Scheduling of Unit-Length Jobs
• Validation of subgradient optimization
• On the facial structure of set packing polyhedra