A Note On The Complexity Of Openshop Scheduling Problems

DOI10.1080/03155986.1991.11732176MaRDI QIDQ3142313zbMATH OpenOpenAlexFDO

Authors Kazimierz Zaras, Wieslaw Kubiak, Chelliah Sriskandarajah

Publication date 15 November 1993

Published in INFOR: Information Systems and Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/03155986.1991.11732176

zbMATH Keywords

maximum latenessNP-hardtotal weighted tardinessopenshop schedulingnumber of late jobspreemptive schedulesfinish timemean flow time in no-wait openshop

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the complexity of preemptive openshop scheduling problems
• The open shop scheduling problem
• On complexity of minimizing weighted number of late jobs in unit time open shops
• On the complexity of preemptive open-shop scheduling problems
• Some no-wait shops scheduling problems: Complexity aspect

Cited in

(31)

• A note on the complexity of the concurrent open shop problem
• The generalized shifting bottleneck procedure
• Open shop scheduling problems with late work criteria.
• An NP-Hard Open Shop Scheduling Problem with Polynomial Average Time Complexity
• A multi-level genetic algorithm for a multi-stage space allocation problem
• On the complexity of preemptive openshop scheduling problems
• scientific article; zbMATH DE number 4068593 (Why is no real title available?)
• Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops
• Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop
• Scheduling ordered open shops
• On the complexity of proportionate open shop and job shop problems
• Minimizing the weighted number of late jobs in UET open shops
• On the complexity of open shop scheduling with time lags
• Scheduling unit time open shops to minimize the weighted number of late jobs
• A contribution and new heuristics for open shop scheduling
• The open shop scheduling problem
• Open shops with jobs overlap
• Open shop scheduling with maximal machines
• Some no-wait shops scheduling problems: Complexity aspect
• OSGA: genetic-based open-shop scheduling with consideration of machine maintenance in small and medium enterprises
• Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• On complexity of minimizing weighted number of late jobs in unit time open shops
• On minimizing the weighted number of late jobs in unit execution time open-shops.
• An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
• Openshop scheduling under linear resources constraints
• Complexity results for flow-shop and open-shop scheduling problems with transportation delays
• Open shop problems with unit time operations
• Minimizing the weighted number of tardy jobs on multiple machines: a review
• A branch \(\&\) bound algorithm for the open-shop problem
• NP-hardness of compact scheduling in simplified open and flow shops.

This page was built for publication: A Note On The Complexity Of Openshop Scheduling Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3142313)