Open shop problem with zero-one time operations and integer release date/deadline intervals

DOI10.1016/S0166-218X(96)00126-6zbMath0883.90066OpenAlexW2068042178MaRDI QIDQ1363753

Marek Kubale

Publication date: 11 August 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

bipartite graphedge-coloringNP-completenessdeadlinesmaximum latenessmaximum tardiness\(n\)-job \(m\)-machine open shopinteger release datesminimum makespan schedule

Mathematics Subject Classification ID

Applications of graph theory (05C90) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Stochastic network models in operations research (90B15) Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15)

Related Items (3)

Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Extensions of coloring models for scheduling purposes ⋮ Complexity of some special types of timetabling problems

Cites Work

• Unnamed Item
• Some results concerning the complexity of restricted colorings of graphs
• Scheduling unit-time tasks with integer release times and deadlines
• Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops
• On Edge Coloring Bipartite Graphs
• Unit Execution Time Shop Problems
• Open shop problems with unit time operations
• Open Shop Scheduling to Minimize Finish Time
• Some graph‐theoretical models for scheduling in automated production systems
• Note: Open-shop scheduling with release dates to minimize maximum lateness
• Lattice Polyhedra II: Generalization, Constructions and Examples

This page was built for publication: Open shop problem with zero-one time operations and integer release date/deadline intervals