关键词: 设备预约, 启发式算法, 背包问题, 回溯调整, 邻域搜索

Abstract: To solve the job scheduling problem caused by parallel equipment appointments, based on analysis on the appointing process and the sharing rules, a quantitative model of the problem was achieved, which was NP-complete. Because it is nondeterministic and many parallel appointments existed in the actual system, an effective heuristic algorithm based on problem decomposition was proposed. Zones solving order was determined by Spare First (SF) strategy, then every single zone problem was solved by improved Dantzig algorithm, and local trace back was used in every step, finally local search was used to improve the result further. The quantitative simulation showed the better performance of the presented algorithm, which could bring out the satisfied result in few time.

Key words: equipment appointment, heuristic algorithm, knapsack problem, trace back, local search