An Order Scheduling Heuristic to Minimize the Total Collation Delays and the Makespan in High-Throughput Make-to-Order Manufacturing Systems

This paper presents an order scheduling heuristic to minimize the total collation delays and the makespan in high-throughput make-to-order manufacturing systems. Order collation delay is the completion time difference between the first and the last processed items within the same order. Large order collation delays contribute to a reduced throughput, non-recoverable productivity loss, or even system deadlocks. In manufacturing systems with high throughput, this scheduling problem becomes computationally expensive to solve because the number of orders is very large; thus, efficient constructive algorithms are needed. To minimize both objectives efficiently, this paper proposes a novel workload balance with single-item orders (WBSO) heuristic while considering machine flexibility. Through a comparison with (1) the non-dominated sorting genetic algorithm II (NSGA-II), (2) priority-based longest processing rule (LPT-P), (3) priority-based least total workload rule (LTW-P), and (4) multi-item orders first rule (MIOF), the effectiveness of the proposed method is evaluated. Experimental results for different scenarios indicate that the proposed WBSO heuristic provides 33% fewer collation delays and 6% more makespan on average when compared to the NSGA-II. The proposed method can work on both small and large problem sizes, and the results also show that for large size problems, the WBSO generates 74%, 89%, and 62% fewer collation delays on average than LPT-P, LTW-P, and MIOF rules respectively.