Long Chen, Lindong Liu, and Lan Lu*. "Extended Arc-Time-Indexed Formulation and Exact Approach for Flow Shop Scheduling." Submitted, 2025. [abstract] [paper] [slides] This study addresses the classical flow shop scheduling problem, involving a finite set of jobs and machines, where each job must be processed on all machines in a fixed order. The objective is to determine a non-preemptive schedule that minimizes the makespan, defined as the maximum job completion time. This problem arises frequently in industrial settings, such as photolithography in semiconductor manufacturing and production lines in the automotive industry. However, it becomes strongly NP-hard when the number of machines is three or more, and additional practical constraints further exacerbate its complexity. Traditional approaches typically adopt the Position-Based Formulation (PBF), which is effective only for small to medium-sized instances. This paper introduces the Arc-Time-Indexed Formulation (ATIF) for flow shop scheduling for the first time, leveraging a network flow representation. By modifying the network structure (such as incorporating virtual initial arcs and idle arcs), the model is adapted to capture the sequential nature of flow shop operations. A branch-and-price algorithm is then developed to solve medium-scale instances exactly. Extensive computational experiments demonstrate that ATIF significantly outperforms the PBF in both modeling flexibility and solution efficiency.