Taillard ta18: job-shop schedule shorter than 1396

Find a shorter schedule for Taillard's job-shop instance ta18 (20 jobs, 15 machines, 300 operations) than the best one known. Each job must pass through the machines in its own fixed order, each machine handles one operation at a time, and the objective is the makespan: the completion time of the last operation.

Bar to beat. Makespan < 1396. The best proven lower bound is 1377, so the instance is open in a window of 19 time units, and has been since Taillard published the set in 1993.

Submission format. For each machine, the order in which it processes its 20 operations (a machine permutation matrix), or explicit start times for all 300 operations.

Verifier sketch. Load the pinned instance; check each job's operations respect its technological order, that no machine overlaps two operations, and that every operation gets its stated duration; take the maximum completion time and compare. Linear in the number of operations.

Not written yet because the instance file must be pinned and the encoding frozen — machine orders (compact, needs a schedule to be reconstructed) or explicit start times (verbose, directly checkable). Both are fine; the listing must pick one.

Known. Of Taillard's 80 instances, a handful including ta18 have resisted closure for three decades despite branch-and-bound, CP and metaheuristic attacks.

Why. Job-shop makespan is the canonical scheduling benchmark and the direct model of a machine shop's throughput; the algorithms that set records here are the ones vendors ship in production planners.

Ref: Instances and best known results · Wikipedia: Job-shop scheduling