考慮維護且加工時間可變的單機調度問題研究

作者：蔣志高,董明

摘要：解決了考慮多階段時間窗（Time-window）[u,v]周期性維護的情況下,因工件加工存在學習效應,加工時間可變時目標函數為最小makespan的單機調度問題。證明了維護次數θ的上界θUB,首次提出虛擬維護的概念,在此基礎上給出了兩階段模型來描述該問題。然后,本文給出了多項式時間復雜度的啟發式算法,LPT-SPT算法;以及將初始解群和接受概率等概念引入變領域搜索算法（Variable Neighborhood Search,VNS）,提出了改進的VNS算法,基于群的變領域搜索（Populated Variable Neighborhood Search,P-VNS）。最后,大量的實例驗證了LPT-SPT算法和P-VNS有著較高的時間效率和很好的解精度。

發文機構：上海交通大學工業工程與物流管理系

關鍵詞：時間窗維護學習效應虛擬維護LPT-SPTP-VNStime-window maintenancelearning effectvirtual maintenanceVNSP-VNS

分類號： F224[經濟管理—國民經濟]