Makespan Minimization in Job Shops: A Linear Time Approximation Scheme: The Interval LP Is Feasible at the Restricted OptimumResearch Paper
The job shop scheduling problem asks for a nonpreemptive schedule of jobs on machines, each job a fixed sequence of operations with prescribed machines and processing times, that minimizes the time at which the last operation completes. It is one of the most studied hard problems of combinatorial optimization: even very constrained versions are strongly…