Fixed order scheduling with deadlines

This paper studies a scheduling problem where machines must follow a predetermined fixed order for processing jobs. Given n jobs, each with processing times and deadlines, we aim to minimize the number of machines used while meeting deadlines and maintaining the order. We show that the first-fit algorithm is a 2-approximation when the order aligns with non-increasing slacks, non-decreasing slacks, or non-increasing deadlines. In general, we provide an O ( log ⁡ n ) -approximation.