Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
From MaRDI portal
Publication:2464428
DOI10.1023/B:JOSH.0000036858.59787.c2zbMath1154.90506MaRDI QIDQ2464428
Jan Karel Lenstra, Wen-Ci Yu, Hoogeveen, J. A.
Publication date: 20 December 2007
Published in: Journal of Scheduling (Search for Journal in Brave)
Related Items (54)
An efficient heuristic method for joint optimization of train scheduling and stop planning on double-track railway systems ⋮ Exact method for the two-machine flow-shop problem with time delays ⋮ Polynomial time algorithms for the UET permutation flowshop problem with time delays ⋮ Computational complexity of manipulation: a survey ⋮ The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays ⋮ The coupled unit-time operations problem on identical parallel machines with respect to the makespan ⋮ Polynomial-time approximation schemes for scheduling problems with time lags ⋮ Approximating the 2-machine flow shop problem with exact delays taking two values ⋮ Two-machine interval shop scheduling with time lags ⋮ Flowshop scheduling with interstage job transportation ⋮ Optimal control of a two-server flow-shop network ⋮ A note on scheduling coupled tasks for minimum total completion time ⋮ Strategic voting in the context of stable-matching of teams ⋮ A historical note on the complexity of scheduling problems ⋮ On the complexity of open shop scheduling with time lags ⋮ Mapping filtering streaming applications ⋮ Approximation algorithms for coupled task scheduling minimizing the sum of completion times ⋮ Preemptive scheduling on two identical parallel machines with a single transporter ⋮ Strategic voting in negotiating teams ⋮ Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules ⋮ Manipulation can be hard in tractable voting systems even for constant-sized coalitions ⋮ On the complexity of the unit commitment problem ⋮ Approximation algorithms for UET scheduling problems with exact delays ⋮ Scheduling problems in master-slave model ⋮ Distance restricted manipulation in voting ⋮ Profit-based latency problems on the line ⋮ Control complexity in Borda elections: solving all open cases of offline control and some cases of online control ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Minimizing flowtime for paired tasks ⋮ Multigraph realizations of degree sequences: Maximization is easy, minimization is hard ⋮ Frugal bribery in voting ⋮ Analysis of heuristics for the UET two-machine flow shop problem with time delays ⋮ A note on the hardness of Skolem-type sequences ⋮ Unnamed Item ⋮ Scheduling coupled-operation jobs with exact time-lags ⋮ Efficient reallocation under additive and responsive preferences ⋮ Unnamed Item ⋮ A 3/2-Approximation for the Proportionate Two-Machine Flow Shop Scheduling with Minimum Delays ⋮ Coupled task scheduling with exact delays: literature review and models ⋮ Minimizing total completion time in two-machine flow shops with exact delays ⋮ Two machines flow shop with reentrance and exact time lag ⋮ Transporting jobs through a two‐machine open shop ⋮ Improved analysis of an algorithm for the coupled task problem with UET jobs ⋮ Mixed integer linear programming models for flow shop scheduling with a demand plan of job types ⋮ Scheduling coupled tasks with exact delays for minimum total job completion time ⋮ Coupled task scheduling with time-dependent processing times ⋮ On-line two-machine job shop scheduling with time lags ⋮ Optimizing consolidation processes in hubs: the hub-arrival-departure problem ⋮ The two-machine open-shop problem with unit-time operations and time delays to minimize the makespan ⋮ Two-machine flowshop scheduling problem with coupled-operations ⋮ Minimizing Total Completion Time in Two-Machine Flow Shops with Exact Delays ⋮ SCHEDULING TWO-MACHINE FLOW SHOPS WITH EXACT DELAYS ⋮ Permutation flowshop scheduling problems with maximal and minimal time lags ⋮ The focus of attention problem
This page was built for publication: Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
