Self-adaptive large neighborhood search algorithm for parallel machine scheduling problems

作     者：Pei Wang Gerhard Reinelt Yuejin Tan 

作者机构：College of Information Systems and Management National University of Defense Technology Changsha 410073 P. R. China Discrete Optimization Research Group Ruprecht-Karls Universitaeit Heidelberg Heidelberg 69120 Germany 

出 版 物：《Journal of Systems Engineering and Electronics》 (系统工程与电子技术（英文版）)

年 卷 期：2012年第23卷第2期

页      面：208-215页

核心收录：

学科分类：12[管理学] 0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 07[理学] 08[工学] 070105[理学-运筹学与控制论] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081203[工学-计算机应用技术] 0802[工学-机械工程] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the National Natural Science Foundation of China (70601035 70801062) 

主　　题：non-identical parallel machine scheduling problem with multiple time windows (NPMSPMTW) oversubscribed self- adaptive large neighborhood search (SALNS) machine learning. 

摘      要：A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.