Open shop problems with unit time operations

DOI10.1007/BF01415528zbMath0776.90033OpenAlexW2073377450MaRDI QIDQ4031970

Marion Jurisch, Bernd Jurisch, Peter Brucker

Publication date: 3 May 1993

Published in: [https://portal.mardi4nfdi.de/entity/Q3031760 ZOR Zeitschrift f�r Operations Research Methods and Models of Operations Research] (Search for Journal in Brave)

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

zbMATH Keywords

preemptive schedulingopen shop schedulingidentical parallel machinespolynomial transformation

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (22)

Shop scheduling problems with multiprocessor tasks on dedicated processors ⋮ On complexity of minimizing weighted number of late jobs in unit time open shops ⋮ Scheduling equal processing time jobs to minimize the weighted number of late jobs ⋮ Minimizing the total completion time in a unit-time open shop with release times ⋮ A branch \(\&\) bound algorithm for the open-shop problem ⋮ Open shop problem with zero-one time operations and integer release date/deadline intervals ⋮ The complexity of mean flow time scheduling problems with release times ⋮ On minimizing the weighted number of late jobs in unit execution time open-shops. ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity ⋮ On the complexity of minimizing the number of late jobs in unit time open shop ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ A new heuristic for open shop total completion time problem ⋮ Scheduling two-machine no-wait open shops to minimize makespan ⋮ Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Minimizing the weighted number of late jobs in UET open shops ⋮ A polynomial algorithm for an open shop problem with unit processing times and tree constraints ⋮ Open-shop scheduling for unit jobs under precedence constraints ⋮ Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop ⋮ Two-machine shop scheduling with zero and unit processing times ⋮ Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints ⋮ Scheduling unit time open shops to minimize the weighted number of late jobs

Cites Work

• Unnamed Item
• Unnamed Item
• NP-complete scheduling problems
• A polynomial algorithm for an open shop problem with unit processing times and tree constraints
• Optimal scheduling for two-processor systems
• Scheduling with Deadlines and Loss Functions
• A Note On The Complexity Of Openshop Scheduling Problems
• Scheduling Open Shops with Unit Execution Times to Minimize Functions of Due Dates
• The Two-Machine Maximum Flow Time Problem with Series-Parallel Precedence Constraints: An Algorithm and Extensions
• A New Algorithm for Preemptive Scheduling of Trees
• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
• Unit Execution Time Shop Problems
• Scheduling Tasks with Nonuniform Deadlines on Two Processors
• Two-Processor Scheduling with Start-Times and Deadlines
• Complexity of Scheduling under Precedence Constraints
• Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Some simple scheduling algorithms
• A Fast Algorithm for Multiprocessor Scheduling of Unit-Length Jobs
• Optimal Preemptive Scheduling on Two-Processor Systems
• Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems

This page was built for publication: Open shop problems with unit time operations