Treffer: Scheduling Intrees with Unavailability Constraints on Two Parallel Machines

This paper considers the two parallel-machine scheduling problem with intree-precedence constraints where machines are subject to non-availability constraints. In the literature, this problem is considered to be an open problem of unknown complexity. The proposed solution proves that the problem under consideration has polynomial complexity. Periods of machine unavailability are predetermined, and both task execution and inter-task communication are modeled as requiring one unit of time. The optimization criterion central to this study is the minimization of the makespan. Such a scheduling challenge is directly applicable to manufacturing environments, where production equipment can be intermittently offline for reasons such as unscheduled repairs or planned preventative maintenance. Adopting a unit-time task model offers a valuable framework for subsequently scheduling larger, preemptable jobs.This work presents a new method, called Scheduling Intrees with Unavailability Constraints (SIwUC), which operates by aggregating tasks into distinct groups. The analysis establishes that the SIwUC algorithm produces optimal schedules and reveals how the underlying problem architecture and its solutions demonstrate a symmetrical property in the distribution of tasks across the two parallel machines. This paper demonstrates that the proposed SIwUC algorithm builds optimal schedules and highlight how the problem structure and its solutions exhibit a form of symmetry in balancing task allocation between the two parallel machines.