An FPTAS for Two-Machine Open-Shop Scheduling with a Single Unavailability Interval

1 Introduction

• Each job has two operations that cannot overlap, and their order may be chosen independently; the fixed maintenance period occupies [s, e] on one machine.Source: §1 · p. 2
• A single fixed maintenance period makes the two-machine open-shop problem NP-hard; resumable interruptions continue without penalty after the machine becomes available.Source: §1 · p. 2
• Existing resumable results include a 4/3-approximation and PTASs for single- and multiple-period variants, while related flow-shop work has an FPTAS.Source: §1 · p. 2
• The authors give the first FPTAS for the resumable problem via a seven-dimensional pseudo-polynomial dynamic program followed by scaling and rounding.The dynamic program runs in O(nsV^5), and the FPTAS runs in O(n^7/ε^6).Source: §1 · p. 3

• The unavailability interval [s, e] is on M1, with positive integer processing times and 0 < s < a(N); boundary cases s = 0 or s ≥ a(N) are solvable in O(n) time.Source: §2 · p. 3
• An optimal schedule has one of two forms: M1 orders XP/XS/YS and M2 orders YS/XP/XS, or M1 orders XP/YP/YS and M2 orders YP/YS/XP.Source: §2 · p. 4
• Interchanging jobs between XS and YP yields an optimal schedule in which either YP or XS is empty, without increasing makespan.Source: §2 · p. 4
• A canonical optimal schedule can also order XP/YP/XS/YS on M1 and YP/YS/XP/XS on M2, with identical job order within each subset.Source: §2 · p. 4
• XP and XS follow Johnson’s rule, while YP and YS follow its reverse; Johnson’s rule orders jobs by comparing min{ai, bj} values.Source: §2 · pp. 3, 6

• Seven state dimensions and O(nsV^5) running time improve on Lorigeon et al.’s ten-dimensional, O(ns^2V^7) dynamic program.Source: §3 · p. 6
• Rather than minimizing makespan directly, the program minimizes a(XP) using the original processing times.Source: §3 · p. 6
• Retaining this unrounded value after rounding preserves feasibility with respect to s, while the state variables recover the makespan.Source: §3 · p. 6

3.1 Computing the makespan from XP , XS, Y P , and Y S

• The last-operation machine determines which of two observations gives the makespan as a maximum of completion-time bounds.The proof combines the M1 and M2 cases to evaluate a fixed partition.Source: §3.1 · pp. 7, 9
• When the last operation completes on M1, the bounds capture total M1 work plus the interruption, reverse-Johnson makespans, and the post-unavailability start constraint for Y S.The formula is max{a(N) + d, Cmax(Y S), e + a(Y S)}; it remains valid when XS is empty.Source: §3.1 · p. 7
• When the last operation completes on M2, the bounds capture XP and XS flow-shop completion, the interruption between them, and total M2 work.The three bounds correspond to an idle interval between Y S and XP, an idle interval between XP and XS, or continuous M2 processing.Source: §3.1 · pp. 7–8, Figure 8 · p. 8
• For XS = ∅, the M2 completion formula remains valid because the interruption-related term is redundant when the last operation finishes on M2.The remaining possibilities are completion at b(N) or at Cmax(XP), depending on whether an idle interval separates Y S and XP.Source: §3.1 · pp. 8–9, Figure 9 · p. 8

3.2 Dynamic program

• Three flow-shop subproblems contribute two state variables each, and the job index makes the dynamic program seven-dimensional.The state value tracks a(Nk ∩ XP) using original processing times, while the subproblems omit the unavailability interval handled during global makespan reconstruction.Source: §3.2 · p. 10

3.2.1 Case A: Y P = ∅

• In Case A, where Y P = ∅, the recurrence assigns each Johnson-ordered job to XP, XS, or Y S using state variables for processing totals and subproblem makespans.The state value retains a(Nk ∩ XP) on original processing times so feasibility against the original bound s remains checkable after rounding.Source: §3.2 · p. 10, §3.2.1 · pp. 10–11

3.2.2 Case B: XS = ∅

• Case B corresponds to XS = ∅ and assigns each job among XP, Y P, and Y S with six subproblem coordinates plus the job index.Its state coordinates record processing totals and makespans for the three subsets; transitions (a), (b), and (c) assign jobs to XP, Y P, and Y S.Source: §3.2 · p. 10, §3.2.2 · p. 13

Part (a): assigning job k to XP.

• Assigning job k to XP updates XP’s processing-time and makespan coordinates, with the transition condition accounting for the resulting schedule boundary.The XP transition is described by recurrence (a), and the boundary case uses Observation 5 to delay preceding jobs on M2.Source: §3.2.1 · p. 11, Part (a): assigning job k to XP · p. 11

Part (b): assigning job k to XS.

• Assigning job k to XS updates XS’s state coordinates using the same boundary argument as the XP assignment.The recurrence assigns job k to XS through transition (b).Source: §3.2.1 · p. 11, Part (b): assigning job k to XS · p. 12

Part (c): assigning job k to Y S.

• When job k is assigned to Y S, it is the last job in that subset to begin processing.The Y S assignment is transition (c) in Case A.Source: §3.2.1 · p. 11, Part (c): assigning job k to Y S · p. 12

3.2.3 Makespan

• After all jobs are processed, feasible terminal states are evaluated using the case-specific makespan propositions, and backtracking recovers the partition and schedule.The selected partition is combined with the prescribed Johnson orders.Source: §3.2.3 · pp. 13–14

• The rounded instance floors each processing time and the interval start after scaling by δ; the algorithm runs the rounded dynamic program and backtracks from a minimum-makespan terminal state.Source: §4 · pp. 14–15
• Although state coordinates are rounded, transition (a) adds the original processing time, keeping the condition f_n ≤ s valid after mapping the schedule back.Source: §4 · p. 15
• Each rounded time parameter differs from its scaled counterpart by less than one, while a critical completion-time expression contains at most n + 1 operation lengths and one unavailability interval.Source: §4 · p. 15
• Rounding down cannot increase makespan, and the lower bound satisfies LB ≥ OPT/2.Source: §4 · pp. 14–15
• The rounded dynamic program has O(n(V^0)^6) states and runs in O(n^7/ε^6) time, so Algorithm FP is an FPTAS.Source: §4 · pp. 15–16

• A four-way job partition lets a compact collection of flow-shop states recover the makespan, yielding a seven-dimensional pseudo-polynomial dynamic program and the first FPTAS for the resumable problem.Source: §5 · p. 16
• Whether the corresponding non-resumable problem also admits an FPTAS remains an open direction for future work.Source: §5 · p. 16