Randomized large neighborhood search for cumulative scheduling

Abstract

This paper presents a Large Neighborhood Search (LNS) approach based on constraint programming to solve cumulative scheduling problems. It extends ear-lier work on constraint-based randomized LNS for dis-junctive scheduling as reported in (Nuijten & Le Pape 1998). A breakthrough development in generalizing that approach toward cumulative scheduling lies in the presented way of calculating a partial-order schedule from a fixed start time schedule. The approach is ap-plied and tested on the Cumulative Job Shop Schedul-ing Problem (CJSSP). An empirical performance anal-ysis is performed using a well-known set of bench-mark instances. The described approach obtains the best known performance reported to date on the CJSSP. It not only finds better solutions than ever reported be-fore for 33 out of 36 open instances, it also proves to be very robust on the complete set of test instances. Fur-thermore, among these 36 open instances, one is now closed. As the approach is generic, it can be applied to other types of scheduling problems, for example prob-lems including resource types like reservoirs and state resources, and objectives like earliness/tardiness costs and resource allocation costs.