Level schedules for mixed-model JIT production lines: characteristics of the largest instances that can be solved optimally

Takt time and cycle time are design variables in JIT production. Actual production is a performance variable. The level production scheduling problem constructs a schedule that matches actual production to takt time and cycle time. The problem can be solved optimally by constructing a network of nodes and arcs in which each path through the network corresponds to a production schedule and the shortest path corresponds to the optimal level production schedule. When a problem instance is large the number of nodes and arcs is very large. It is critically important to (i) eliminate from the network nodes and arcs that cannot be on the shortest path and (ii) evaluate the remaining nodes and arcs efficiently. This paper examines the best algorithm for finding an optimal schedule and analyses, by solving previously unsolved instances from the literature, characteristics of the largest instances that can be solved optimally.