SCHEDULING TWO-MACHINE FLOW SHOPS WITH EXACT DELAYS

DOI10.1142/S0129054107004711zbMath1112.68015MaRDI QIDQ3434279

Hairong Zhao, Joseph Y.-T. Leung, Haibing Li

Publication date: 25 April 2007

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmmakespanflow shopNP-hardtotal completion timeexact delay

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed systems (68M14) Approximation algorithms (68W25)

Related Items

The no-wait job shop with regular objective: a method based on optimal job insertion ⋮ Approximating the 2-machine flow shop problem with exact delays taking two values ⋮ Approximation algorithms for coupled task scheduling minimizing the sum of completion times ⋮ Coupled task scheduling with exact delays: literature review and models ⋮ Minimizing total completion time in two-machine flow shops with exact delays ⋮ Scheduling coupled tasks with exact delays for minimum total job completion time ⋮ Coupled task scheduling with time-dependent processing times ⋮ Minimizing Total Completion Time in Two-Machine Flow Shops with Exact Delays

Cites Work

• Unnamed Item
• Unnamed Item
• Inapproximability results for no-wait job shop scheduling.
• Two-machine flow shop scheduling problems with minimal and maximal delays
• Two-machine flow shop scheduling problems with no-wait jobs
• Simple algorithms for gilmore-gomory's traveling salesman and related problems
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• Two-machine flow shop no-wait scheduling with machine maintenance
• Permutation flowshop scheduling problems with maximal and minimal time lags
• Two-Machine No-Wait Flow Shop Scheduling with Missing Operations
• Sequencing n Jobs on Two Machines with Arbitrary Time Lags
• Some new results in flow shop scheduling
• Heuristic algorithms for continuous flow-shop problem
• The Three-Machine No-Wait Flow Shop is NP-Complete
• Complexity of Scheduling Shops with No Wait in Process
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
• Shop Problems With Two Machines and Time Lags
• Makespan Minimization in No-Wait Flow Shops: A Polynomial Time Approximation Scheme
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• Minimizing Makespan in No-Wait Job Shops
• Solution of the Flowshop-Scheduling Problem with No Intermediate Queues
• A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process
• On the complexity of coupled-task scheduling