针对带交货期的单机逆调度问题，建立以最小化系统调整为目标函数的单机逆调度数学优化模型；利用互补性能，采用串行、并行和嵌入等结构，将遗传算法与变邻域搜索算法相结合，设计出遗传-变邻域搜索算法、遗传-变邻域搜索交替算法和遗传-变邻域搜索协同算法3种混合算法。为产生逆调度激发机制，采用非最优调度法，将随机初始化与局部初始化进行结合，创造逆调度环境；此外，为提高算法的局部搜索能力，基于交叉变异操作等思想来构建四种搜索邻域，通过邻域结构的切换，加强局部搜索能力；最后，将提出的混合算法用于求解不同规模的问题实例，与其他算法的求解结果进行比较，证明提出的混合算法是可行的和有效的。
Aiming at the single-machine inverse scheduling problem with due-dates(SISPD), a mathematical model with the minimal adjustment of system as a target is constructed. Using complementary properties, three hybrid algorithms combining genetic algorithm with variable neighborhood search algorithm are proposed by using serial, parallel and embedded structure. In the algorithm, a double scheduling method which combines heuristic non-optimal scheduling method with random initial population and local initial population is designed to construct inverse scheduling mechanism. Then, based on the features of problem and encoding, four neighborhood structures are put forward to improve the local search ability by changing the neighborhood structure. Finally, the proposed algorithms are used to solve numerical instances. The computational results show that the proposed method could solve SISPD effectively.
[1] NGUYEN S,ZHANG M,JOHNSTON M,et al. Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming[J]. Evolutionary Computation,IEEE Transactions on,2014,18(2):193-208.
[2] XU Y,WANG L,WANG S,et al. An effective teaching–learning-based optimization algorithm for the flexible job-shop scheduling problem with fuzzy processing time[J]. Neurocomputing,2015,148:260-268.
[3] HE T,LIU F,MA Y,et al. Study on shop-floor scheduling[J]. Journal of Mechanical Engineering,2000,36(5):97-102.
[4] TANG,D B. Energy-efficient approach to minimizing the energy consumption in an extended job-shop scheduling problem[J]. Chinese Journal of Mechanical Engineering,2015,28(5):1048-1055.
[5] GAO K Z,SUGANTHAN P N,TASGETIREN M F,et al. Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion[J]. Computers & Industrial Engineering,2015,90:107-117.
[6] BRUCKER P,SHAKHLEVICH N V. Inverse scheduling with maximum lateness objective. Journal of Scheduling,2009,12(5):475-488.
[7] BRUCKER P,SHAKHLEVICH N V. Inverse scheduling:two-machine flow-shop problem[J]. J. Sched.,2011,14(3):239-256.
[8] KOULAMAS C. Inverse scheduling with controllable job parameters[J]. International Journal of Services and Operations Management,2005,1(1):35-43.
[9] ZHANG FENG,NG T C,TANG G C. Inverse scheduling:Applications in shipping[J]. International Journal of Shipping and Transport Logistics,2011,3(3):312-322.
[10] 陈荣军,陈峰,唐国春. 单台机器总完工时间排序问题的反问题[J]. 上海第二工业大学学报,2005,22(2):1-7. CHEN Rongjun,CHEN Feng,TANG Guochun. Inverse problems of a single machine scheduling to minimize the total completion time[J]. J. Shanghai Second Polytechnic University,2005,22(2):1-7.
[11] 陈荣军. 单台机器总完工时间随机排序问题的反问题[J]. 常州工学院学报,2006,19(6):1-5. CHEN Rongjun. Inverse scheduling problem on a single machine stochastic scheduling to minimize the total completion time[J]. Journal of Changzhou of technology,2006,19(6):1-5.
[12] 陈荣军,唐国春. 单机供应链排序及流水作业的反问题模型[J]. 运筹与管理,2009,18(2):80-84. Chen Rongjun,Tang Guochun. Inverse problems of supply chain scheduling and flowshop scheduling[J]. Operations research and management science,2009,18(2):80-84.
[13] Pham Hongtruong,鲁习文. 平行机上单位加工时间加权总完工时间排序问题的反问题[J]. 华东理工大学学报,2012,38(6):757-761. Pham Hongtruong,Lu Xiwen. Inverse problem of total weighted completion time objective with unit processing time on identical parallel machines[J]. Journal of East China University of Science and Technology,2012,38(6):757-761.
[14] VERELA R,VELA C R,PUENTE J. GOMEZ A. A knowledge-based evolutionary strategy for scheduling problems with bottlenecks[J]. European Journal of Operational Research,2003,145:57-71.
[15] SHAPIRO J F. A survey of Lagrangian techniques for discrete optimization[J]. Annals of Discrete Mathematics,1979,5:113-138.
[16] HANSEN P,MLADENOVIC N. Variable neighborhood search[M]. New York:Springer,2014.
[17] XIA W,WU Z,ZhANG W,et al. Applying particle swarm optimization to job-shop scheduling problem[J]. Chinese Journal of Mechanical Engineering,2004,17(3):437-441.
[18] 潘全科,王文宏,朱剑英,等. 基于粒子群优化和变邻域搜索的混合调度算法[J]. 计算机集成制造系统,2007,13(2):323-328. PAN Quanke,WANG Wenhong,ZHU Jianying,et al. Hybrid heuristics based on particle swarm optimization and variable neighborhood search for job shop scheduling. Computer integrated manufacturing system,2007,13(2):323-328.
[19] RANTALANKILA P,KANNALS J,RAHTU E. Generating object segmentation proposals using global and local search[C]// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2014:2417-2424.
[20] MOU J H,GAO L,LI X Y,et al. Optimization of the reverse scheduling problem by a modified genetic algorithm. International Journal of Production Research,2015,53(23):6980-6993.
[21] MOU J H,LI X Y,GAO L,et al. An improved genetic algorithm for single-machine inverse scheduling problem[J]. Mathematical Problems in Engineering,2014,2014(4):1-14.
[22] MOU J H,GAO L,LI X Y,et al. An effective L-MONG for solving multiobjective flow shop inverse scheduling problems[J]. Journal of Intelligent Manufacturing,2015:1-19.
[23] 王松. 基于遗传算法的单机逆调度方法研究[D]. 武汉:华中科技大学,2014. WANG Song. Research on the solution method of single machine inverse scheduling based on genetic algorithm[D]. Wuhan:Huazhong University of Science and Technology,2014
[24] 牟健慧,郭前建,高亮,等. 基于混合的多目标遗传算法的多目标流水车间逆调度问题求解方法[J]. 机械工程学报,2016,52(22):186-197. MU Jianhui,GUO Qianjian,GAO Liang et al. Hybrid HMGA algorithm for solving multi-objective flow-shop inverse scheduling problems[J]. Journal of Mechanical Engineering,2016,52(22):186-197.
