A column generation approach to scheduling of parallel identical machines

Abstract: This thesis aims to implement a combination of Linear Programming Column Generation and a Large Neighbourhood Search heuristic to solve scheduling problems. The resulting method is named Integer Programming Column Search (IPCS). For computational evaluation, the IPCS method is applied to the problem Prize-Collecting Job Sequencing with One Common and Multiple Secondary Resources generalised to parallel identical machines. The interest of combining exact procedures with heuristic approaches is quickly growing since scheduling problems have many and complex real-world applications. Most of these problems are NP-hard and therefore very challenging to solve. By using a combination of heuristic strategies and exact procedures, it can be possible to find high-quality solutions to such problems within an acceptable time horizon. The IPCS method uses a greedy integer programming column generating problem introduced in a previous work. This problem is designed to generate columns that are useful in near-optimal integer solutions. A difference to previously introduced method is that we here build a master problem, an Integer Programming Column Search Master (IPCS-Master). This is used to update the dual solution that is provided to the greedy integer programming column generating problem. The computational performance of the IPCS method is evaluated on instances with 60, 70, 80, 90 and 100 jobs. The result shows that the combined design encourage the generation of columns that benefit the search of near-optimal integer solutions. The introduction of an IPCS-Master, which is used to update the dual variable values, generally leads to fewer pricing problem iterations than when no master problem is used.