一种邻域搜索算法在差异工件单机批调度问题中的应用研究
|
摘要
生产调度是一类重要的组合优化问题,在工业生产、制造系统等领域应用广泛。合理的调度方案有助于提高生产效率,减少生产成本,因此对调度问题研究有着重要的现实意义。
批调度是调度问题的一个重要分支。不同于经典调度问题,在批调度模型中,一台机器可以同时处理多个工件。差异工件批调度问题(Batch Processing Machines with Non-identical Job Sizes,NSBM)是对传统批调度问题的进一步扩展,即工件尺寸不同,且同一批中工件的总尺寸不能超过批的容量限制。邻域搜索算法是求解组合优化问题的一类重要优化方法,这类算法以进化的方式在解空间中进行寻优,具有简单、适用范围广和鲁棒性强等。本文将一种新的邻域搜索算法——自由搜索算法(Free Search,FS)应用于NSBM问题,主要工作如下:
首先,充分利用工件序列这一启发信息求解NSBM问题,即首先采用FS算法寻找一个较优的工件序列,然后将该工件序列按一定的启发式规则进行分批。论文针对生产调度问题的离散性,设计了向量形式的编码方式,并结合改进的Best-Fit启发式分批规则,构造了工件序列编码的自由搜索算法。根据本文的目标函数,对算法模型中的信息素重新定义,并设置三类不同数值的邻域半径,避免算法陷入局部最优。实验表明,FS的求解效果优于现有的启发式算法和智能算法。
其次,利用批序列的编码方式求解NSBM问题,即直接构造批,然后用邻域搜索算法对批序列优化。工件序列编码的方法在求解问题时结果会受到所选用的启发式分批规则的影响,若分批规则求解效果不好,则工件序列优化对结果的改进也很有限,且该方法不能在完备的解空间中寻优,不利于找到更好的解。论文提出了一种混合邻域搜索算法(Hybrid Neighborhood Search,HNS),根据FS算法在搜索过程中存在的停滞问题,加入差异演化算法和局部优化策略,并利用尖点灾变理论的精英保留机制进一步提高搜索效率,仿真实验验证了HNS算法的有效性。
最后,对全文进行了总结,讨论了进一步的研究方向和设想。
Scheduling is one of the most important combinatorial optimization problems. It is very important in industrial production, manufacturing systems and other fields. A reasonable scheduling scheme can improve production efficiency and reduce production costs,so the research on it has important practical significant.
Batch scheduling is an important branch of scheduling problems. Different from the classical ones, a number of jobs can be processed simultaneously by a batch machine. Batch scheduling problem with non-identical jobs sizes (NSBM), in which the jobs are non-identical in size and the total size of the jobs in a batch cannot exceed the capacity of the machine, is an extension of batch scheduling problem.
Neighborhood search algorithm is significant method of solving combinatorial optimization problems. Running as evolution in the solution space, it is simple, generic and robust. A novel algorithm called Free Search (FS) is firstly applied to solve the scheduling problems on NSBM in this paper. The main work is as follows: First, solving the problem based on the sequence of jobs. FS is used to search a superior jobs’sequence, then batching according to heuristic rules. A coding approach with vectors is designed due to the discrete of scheduling problems. A heuristic was then combined with FS and then an algorithm based on the sequence of jobs is constructed. By the features of NSBM, the pheromone in the model is redefined and three different values of radius are set to avoid premature convergence. Experiments show that FS is better than the previous method.
Secondly, solving the problem based on the sequence of batches. Batching directly, and then optimizing the sequence of batches by an algorithm. The results of the method based on the sequence of jobs will be affected by the heuristic algorithms. If the heuristic algorithms perform not well, the improvement of results based on the optimization of the sequence of jobs. Even the space is shrinking by that method and it isn’t conducive to search a better solution. A Hybrid Neighborhood Search is proposed to solve NSBM. In order to avoid stagnation of FS, we apply Differential Evolution and local optimal strategy to modify the algorithm. At last, cusp catastrophe theory is used as elitist reserving mechanism. Computational results are presented to show the better search ability of the algorithm, and testify the validity of HNS.
Finally, sum up the thesis, and give some further ideas and future research prospects.
批调度是调度问题的一个重要分支。不同于经典调度问题,在批调度模型中,一台机器可以同时处理多个工件。差异工件批调度问题(Batch Processing Machines with Non-identical Job Sizes,NSBM)是对传统批调度问题的进一步扩展,即工件尺寸不同,且同一批中工件的总尺寸不能超过批的容量限制。邻域搜索算法是求解组合优化问题的一类重要优化方法,这类算法以进化的方式在解空间中进行寻优,具有简单、适用范围广和鲁棒性强等。本文将一种新的邻域搜索算法——自由搜索算法(Free Search,FS)应用于NSBM问题,主要工作如下:
首先,充分利用工件序列这一启发信息求解NSBM问题,即首先采用FS算法寻找一个较优的工件序列,然后将该工件序列按一定的启发式规则进行分批。论文针对生产调度问题的离散性,设计了向量形式的编码方式,并结合改进的Best-Fit启发式分批规则,构造了工件序列编码的自由搜索算法。根据本文的目标函数,对算法模型中的信息素重新定义,并设置三类不同数值的邻域半径,避免算法陷入局部最优。实验表明,FS的求解效果优于现有的启发式算法和智能算法。
其次,利用批序列的编码方式求解NSBM问题,即直接构造批,然后用邻域搜索算法对批序列优化。工件序列编码的方法在求解问题时结果会受到所选用的启发式分批规则的影响,若分批规则求解效果不好,则工件序列优化对结果的改进也很有限,且该方法不能在完备的解空间中寻优,不利于找到更好的解。论文提出了一种混合邻域搜索算法(Hybrid Neighborhood Search,HNS),根据FS算法在搜索过程中存在的停滞问题,加入差异演化算法和局部优化策略,并利用尖点灾变理论的精英保留机制进一步提高搜索效率,仿真实验验证了HNS算法的有效性。
最后,对全文进行了总结,讨论了进一步的研究方向和设想。
Scheduling is one of the most important combinatorial optimization problems. It is very important in industrial production, manufacturing systems and other fields. A reasonable scheduling scheme can improve production efficiency and reduce production costs,so the research on it has important practical significant.
Batch scheduling is an important branch of scheduling problems. Different from the classical ones, a number of jobs can be processed simultaneously by a batch machine. Batch scheduling problem with non-identical jobs sizes (NSBM), in which the jobs are non-identical in size and the total size of the jobs in a batch cannot exceed the capacity of the machine, is an extension of batch scheduling problem.
Neighborhood search algorithm is significant method of solving combinatorial optimization problems. Running as evolution in the solution space, it is simple, generic and robust. A novel algorithm called Free Search (FS) is firstly applied to solve the scheduling problems on NSBM in this paper. The main work is as follows: First, solving the problem based on the sequence of jobs. FS is used to search a superior jobs’sequence, then batching according to heuristic rules. A coding approach with vectors is designed due to the discrete of scheduling problems. A heuristic was then combined with FS and then an algorithm based on the sequence of jobs is constructed. By the features of NSBM, the pheromone in the model is redefined and three different values of radius are set to avoid premature convergence. Experiments show that FS is better than the previous method.
Secondly, solving the problem based on the sequence of batches. Batching directly, and then optimizing the sequence of batches by an algorithm. The results of the method based on the sequence of jobs will be affected by the heuristic algorithms. If the heuristic algorithms perform not well, the improvement of results based on the optimization of the sequence of jobs. Even the space is shrinking by that method and it isn’t conducive to search a better solution. A Hybrid Neighborhood Search is proposed to solve NSBM. In order to avoid stagnation of FS, we apply Differential Evolution and local optimal strategy to modify the algorithm. At last, cusp catastrophe theory is used as elitist reserving mechanism. Computational results are presented to show the better search ability of the algorithm, and testify the validity of HNS.
Finally, sum up the thesis, and give some further ideas and future research prospects.
引文
程八一,陈华平,王栓狮. 2008.模糊制造系统中的不同尺寸工件单机批调度优化[J].计算机集成制造系统,14(7): 1322-1328.
程八一. 2009a.差异工件单机批调度问题的优化算法研究[D]: [博士].合肥:中国科学技术大学.
程八一,陈华平,王栓狮. 2009b.优化差异工件单机批调度问题的改进蚁群算法[J].系统仿真学报,21(9): 2687-2690.
杜长海,黄席樾,杨祖元,等. 2009.改进的FS算法选取支持向量回归机参数及应用[J].计算机应用研究,26(7): 2520-2523.
贾兆红. 2008a.粒子群优化算法在柔性作业车间调度中的应用研究[D]: [博士].合肥:中国科学技术大学.
贾兆红,陈华平,孙耀晖. 2007.混合粒子群算法在柔性工作车间调度中的应用[J].系统仿真学报,19(20): 4743-4747.
贾兆红,陈华平,孙耀晖. 2008b.多目标粒子群优化算法在柔性车间调度中的应用[J].小型微型计算机,29(5): 885-889.
贾兆红,陈华平,唐俊,等. 2008c.面向多目标的自适应动态概率粒子群优化算法[J].系统仿真学报,20(18): 4959-4963.
郭振宇,康龙云. 2006.一种动态改变权重因子和交叉率的混沌差异演化算法[J].哈尔滨工程大学学报,27(7): 523-526.
洪少春,毛恒,王永初. 2008.粒子群与差异演化的混合进化算法研究[J].泉州师范学院学报(自然科学),26(4): 9-15.
鞠彦兵,王爱华,李桂芬. 2006.生产作业计划仿真优化研究[J].微计算机信息(管控一体化),22(11-3): (4-6).
梁静,钱省三,马良. 2005.基于双层蚂蚁算法的半导体炉管制程批调度研究[J].系统工程理论与实践,12: 96-101.
李燕,陈华平,王栓狮,等. 2008.自适应蚁群算法在双向生产车间调度中的应用[J].运筹与管理,17(3): 160-163.
刘贵应,刘新喜,魏新颜. 2002.隧道塌方的尖点灾变模型[J].地质灾害与环境保护,13(2): 59-62.
陆子强,郭国雄,蒋金山. 2005.基于邻域搜索的混合遗传算法及其在对称TSP中的应用[J].计算机工程与应用,7: (79-81).
马建华. 2006.单机分批排序问题的变异蚁群算法[J].计算机工程与应用,03: 53-56.
唐国春,张峰,罗守成等. 2003.现代排序论区[M].上海:上海科学普及出版社.
王国新,宁汝新,王爱民. 2007.基于仿真的生产调度优化技术研究[J].计算机集成制造系统,13(7): 1419-1427.
王红梅. 2006.算法设计与分析[M].北京:清华大学出版社.
王栓狮. 2008.差异工件批调度问题研究与算法设计[D]: [硕士].合肥:中国科学技术大学.
王斌,张展羽,魏永霞,等. 2009.基于投影寻踪的农业基本旱情评估[J].农业工程学报,25(4): 157-162.
魏引尚,张俭让,常心坦. 2002.瓦斯爆炸的灾变模型[J].西安科技学院学报,22(3): 250-253.
武志峰. 2007.一种基于差异演化的特征子集选择算法[J].信息技术,4: 1-3. 刑文训,谢金星. 2005.现代优化算法[M].北京:清华大学出版社.
徐俊刚,戴国忠,王洪安. 2004.生产调度理论和研究方法综述[J].计算机研究与发展,41(2): 254-267.
袁俊刚,孙治国,曲广吉. 2007.差异演化算法的数值模拟研究[J].系统仿真学报,19(20): 4646-4649.
周晖,李丹美,邵世煌,等. 2007a.一种新的群集智能算法——自由搜索[J].东华大学学报,33(5): 579-583.
周晖,李丹美,邵世煌,等. 2008.一种新的群集智能优化及其改进研究[J].系统工程与电子技术,30(2): 337-340.
Artiba A.,Riane F. 1998. An application of a planning and scheduling multi-model approach in the chemical industry[J]. Computers in Industry,36(3): 209-229.
Azizoglu M., Webster S. 2000. Scheduling a batch processing machine with non-identical job sizes[J]. International Journal of Production Research,38(10): 2173-2184.
Blum Christian. 2003. Beam-ACO-hybridizing ant colony optimization with beam search: an application to open shop scheduling[J]. Computer and Operations Research,32 (2005) : 1565-1591.
Birrell N. D. 1983. Application of catastrophe theory to a slotted ALOHA communication system[J]. IEE Proceedings F (Communications, Radar and Signal Processing),130(4): 337-342.
Brest J.,Greiner S.,Boskovie B.,et al. 2006. Self-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems. In: IEEE Transactions on Evolutionary Computation,10(6): 646-657.
Brucker P.,Gladky A., Hoogeveen J.A,et al. 1998. Scheduling a batching machine[J]. Journalof Scheduling, 1 : 31-54.
Chen H. X.,Cheng B. C.,Proth J. M. 1995. A more efficient Lagrangian relaxation approach to job shop scheduling Problems[C]. In: Proceedings of IEEE International Conference on Robotics and Automation,Japan,pp.496-501.
Chandru V.,Lee C. Y.,Uzsoy R. 1993. Minimizing total completion time on batch processing machines[J].International Journal of Production Research,31(9): 2097-2121.
Coffman E. G.,Garey M. R.,Johnson D. S. 1984. Approximation time on a batch packing-an updated survey[J]. Algorithm Design for Computer System Design: 49-106.
Colorni A,Dorigo M,Maniezzo V,et al. 1991. Distributed optimization by ant colonies[C]. In: Proceeding of the first European Conference on Artificial Life,France,pp.134-142.
Damodaran P., Manjeshwar P. K.,Srihari K. 2006. Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms[J].International journal of Production Economics, 103(2): 882-891.
Dupont L.,Dhaenens-Flipo C. 2000. Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure[J]. Computers and Operations Research, 29(2002): 807-819.
Fan Hui-Yuan,Jouni Lampinen. 2003. A trigonometric mutation operation to differential evolution[C]. Journal of Global Optimization 27,Netherlands,pp.105-129.
Holland J. 1975. Adaptation in Natural and Artificial Systems[M].Ann Arbor: University of Michigan Press.
Kashan Ali Husseinzadeh, Karimi Behrooz, Jenabi Masoud. 2006. A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job size[sJ]. Computer and Operations Research,35 (2008): 1084–1098.
Kennedy J.,Ebethart R. C. 1995. PartieleswarmoPtimization[C]. In: Proeeedings of the IEEE Intemational Conference on Neural NetW0rks,Piscataway,NJ: IEEE Service Center,4: 1942-1948.
Melouk S.,Damodaran P.,Chang Ping-Yu. 2004. Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing[J]. International Journal of Production Economics,87: 141-147.
Monch Lars, Balasubramanian Hari, Fowler John W., et al. 2004. Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times[J]. Computer and Operations Research,32(2005): 2731–2750.
Monma C.L., Potts C.N. 1989. On the complexity of scheduling with batch setup times[J]. Operations Research,37: 798-804.
Lun P. B.,Hoitomt F. J.,Max E. 1990. Scheduling generation and reconfiguration for Parallel machines[J]. IEEE Transactions of Robotics and Automation,6(6): 687-697.
Omran M. G. H.,Engelbrecht A. P. 2009. Free Search Differential Evolution[C]. In: Evolutionary Computation, 2009. CEC '09. IEEE Congress on,Trondheim,pp. 110- 117.
Penev K. 2004. Adaptive computing in support of traffic management[J]. Adaptive Computing in Design and Manufacturing,20: 295-306.
Penev K.,Littlefair G. 2005. Free Search– a comparative analysis[J]. Information Sciences,172: 173-193.
Penev K.. 2006. Novel Adaptive Heuristic For Search And Optimisation[C]. In: Modern Computing, 2006. JVA '06. IEEE John Vincent Atanasoff 2006 International Symposium on,Sofia,pp. 149 - 154.
Price K. 1997. Differential evolution vs. the functions of the 2nd ICEC [C]. In: Proceedings of the IEEE Conference on Evolutionary Computation,USA,pp.153-157.
Price K.,Storn R. 1999. Differential Evolution (DE) for Continuous Function Optimization [EB/OL]. http://www.icsi.berkeley.edu/~storn/code.html.
Qin A. K.,Sugantlian P. N. 2005. Self-adaptive Differential Evolution Algorithm for Numerical Optimization[C]. In: The 2005 IEEE Congress on Evolutionary Computation(CEC’2005),Scotland,pp. 2:1785-1791.
Ray Tapabrata,Liew K. M. 2002. A Swarm Metaphor for Multiobjective Design Optimization[J]. Engineering optimization,34(2): 141-153.
Reklaitis G. V. 1995. Scheduling approaches for the batch process industries[J]. ISA Transactions,34(4): 349-358.
Salvendy Gavriel. 2005.调度:原理、算法和系统(第二版)(影印版)[M].北京:清华大学出版社.
Stewart I. 1983. Nonelementary catastrophe theory[J]. IEEE Transactions on Circuits and Systems,CAS-30(9): 663-670.
Stewart I. 1983. Applications of nonelementary catastrophe theory[J]. IEEE Transactions on Circuits and Systems,CAS-31(2): 165-174.
Storn R.,Price K. 1996. Minimizing the real functions of the ICEC’96 contest by differential evolution[C]. In: Proceedings of the IEEE Conference on Evolutionary Computation,Nagoya,pp. 842-844.
Sung C. S., Choung Y. I., Hong J M. 2000.Minimizing makespan on a single burn-in oven with job families and dynamic job arrival[sJ].Computer and Operations Research,29(2002): 995-1007.
Sung C. S.,Choung Y. I. 1998. Minimizing makespan on a single burn-in oven in semiconductor manufacturing[J]. European Journal of Operational Research,120(2000): 559-574.
Thom R. 1978. Towards a revival of natural philosophy[C]. In: Structural Stability in Physics,Tubingen,pp.5-11.
Thom R. 2006. The two-fold way of catastrophe theory[M]. Berlin: Springer press.
Uzsoy R. 1994. Scheduling a single batch processing machine with non-identical job sizes[J]. International Journal of Production Research,32(7): 1615-1635.
Veliev Erdoan,Penev Kalin. 2008. Visualization of free search process[C]. In: Artificial Intelligence Series, Proceedings of the 9th WSEAS International Conference on Evolutionary Computing ,Sofia,pp. 133 - 135.
Webster S., Baker K.R. 1995. Scheduling groups of jobs on a single machine[J]. Operations Research, 43(4): 692-703.
Wvong M. D.,Mihiring A. M. 1986. Catastrophe theory applied to transient stability assessment of power systems[J]. IEE Proceedings C (Generation, Transmission and Distribution),133(6): 314-318.
Xue F.,Sanderson A. C.,Graves R. J. 2005. Multi-objective differential evolution algorithm,convergence analysis, and applications[C]. In: The 2005 IEEE Congress on Evolutionary Computation (CEC’2005),Scotland,pp. 1: 743-750.
Yang Dongsheng,Mu Dong,Yao Mingzhi. 2009. Analysis of Financial Crisis: A Perspective Based on Catastrophe Theory[C]. In: Management and Service Science, MASS '09. International Conference onBeijing,pp. 1-4.
Zhang Guochuan, Cai Xiaoqiang, Lee C.-Y,et al. 2001. Minimizing makespan on a single batch processing machine with non-identical job sizes[J]. Naval Research Logistics, 48: 226-247.
Zhou Hui,Li Danmei,Shao Shihuang,et al. 2007. A Novel Intelligent Estimation Algorithm in WSN Location Based On Free Search[C]. In: Wireless Communications, Networking and Mobile Computing, 2007. WiCom 2007. International Conference on,Shanghai,pp. 2629- 2632.
Zhu Guangyu,Wang Jinbao,Guo Hong. 2009. Research and Improvement of Free Search Algorithm[C]. In: Artificial Intelligence and Computational Intelligence, 2009. AICI '09. International Conference on,Shanghai,pp. 235 - 239.
程八一. 2009a.差异工件单机批调度问题的优化算法研究[D]: [博士].合肥:中国科学技术大学.
程八一,陈华平,王栓狮. 2009b.优化差异工件单机批调度问题的改进蚁群算法[J].系统仿真学报,21(9): 2687-2690.
杜长海,黄席樾,杨祖元,等. 2009.改进的FS算法选取支持向量回归机参数及应用[J].计算机应用研究,26(7): 2520-2523.
贾兆红. 2008a.粒子群优化算法在柔性作业车间调度中的应用研究[D]: [博士].合肥:中国科学技术大学.
贾兆红,陈华平,孙耀晖. 2007.混合粒子群算法在柔性工作车间调度中的应用[J].系统仿真学报,19(20): 4743-4747.
贾兆红,陈华平,孙耀晖. 2008b.多目标粒子群优化算法在柔性车间调度中的应用[J].小型微型计算机,29(5): 885-889.
贾兆红,陈华平,唐俊,等. 2008c.面向多目标的自适应动态概率粒子群优化算法[J].系统仿真学报,20(18): 4959-4963.
郭振宇,康龙云. 2006.一种动态改变权重因子和交叉率的混沌差异演化算法[J].哈尔滨工程大学学报,27(7): 523-526.
洪少春,毛恒,王永初. 2008.粒子群与差异演化的混合进化算法研究[J].泉州师范学院学报(自然科学),26(4): 9-15.
鞠彦兵,王爱华,李桂芬. 2006.生产作业计划仿真优化研究[J].微计算机信息(管控一体化),22(11-3): (4-6).
梁静,钱省三,马良. 2005.基于双层蚂蚁算法的半导体炉管制程批调度研究[J].系统工程理论与实践,12: 96-101.
李燕,陈华平,王栓狮,等. 2008.自适应蚁群算法在双向生产车间调度中的应用[J].运筹与管理,17(3): 160-163.
刘贵应,刘新喜,魏新颜. 2002.隧道塌方的尖点灾变模型[J].地质灾害与环境保护,13(2): 59-62.
陆子强,郭国雄,蒋金山. 2005.基于邻域搜索的混合遗传算法及其在对称TSP中的应用[J].计算机工程与应用,7: (79-81).
马建华. 2006.单机分批排序问题的变异蚁群算法[J].计算机工程与应用,03: 53-56.
唐国春,张峰,罗守成等. 2003.现代排序论区[M].上海:上海科学普及出版社.
王国新,宁汝新,王爱民. 2007.基于仿真的生产调度优化技术研究[J].计算机集成制造系统,13(7): 1419-1427.
王红梅. 2006.算法设计与分析[M].北京:清华大学出版社.
王栓狮. 2008.差异工件批调度问题研究与算法设计[D]: [硕士].合肥:中国科学技术大学.
王斌,张展羽,魏永霞,等. 2009.基于投影寻踪的农业基本旱情评估[J].农业工程学报,25(4): 157-162.
魏引尚,张俭让,常心坦. 2002.瓦斯爆炸的灾变模型[J].西安科技学院学报,22(3): 250-253.
武志峰. 2007.一种基于差异演化的特征子集选择算法[J].信息技术,4: 1-3. 刑文训,谢金星. 2005.现代优化算法[M].北京:清华大学出版社.
徐俊刚,戴国忠,王洪安. 2004.生产调度理论和研究方法综述[J].计算机研究与发展,41(2): 254-267.
袁俊刚,孙治国,曲广吉. 2007.差异演化算法的数值模拟研究[J].系统仿真学报,19(20): 4646-4649.
周晖,李丹美,邵世煌,等. 2007a.一种新的群集智能算法——自由搜索[J].东华大学学报,33(5): 579-583.
周晖,李丹美,邵世煌,等. 2008.一种新的群集智能优化及其改进研究[J].系统工程与电子技术,30(2): 337-340.
Artiba A.,Riane F. 1998. An application of a planning and scheduling multi-model approach in the chemical industry[J]. Computers in Industry,36(3): 209-229.
Azizoglu M., Webster S. 2000. Scheduling a batch processing machine with non-identical job sizes[J]. International Journal of Production Research,38(10): 2173-2184.
Blum Christian. 2003. Beam-ACO-hybridizing ant colony optimization with beam search: an application to open shop scheduling[J]. Computer and Operations Research,32 (2005) : 1565-1591.
Birrell N. D. 1983. Application of catastrophe theory to a slotted ALOHA communication system[J]. IEE Proceedings F (Communications, Radar and Signal Processing),130(4): 337-342.
Brest J.,Greiner S.,Boskovie B.,et al. 2006. Self-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems. In: IEEE Transactions on Evolutionary Computation,10(6): 646-657.
Brucker P.,Gladky A., Hoogeveen J.A,et al. 1998. Scheduling a batching machine[J]. Journalof Scheduling, 1 : 31-54.
Chen H. X.,Cheng B. C.,Proth J. M. 1995. A more efficient Lagrangian relaxation approach to job shop scheduling Problems[C]. In: Proceedings of IEEE International Conference on Robotics and Automation,Japan,pp.496-501.
Chandru V.,Lee C. Y.,Uzsoy R. 1993. Minimizing total completion time on batch processing machines[J].International Journal of Production Research,31(9): 2097-2121.
Coffman E. G.,Garey M. R.,Johnson D. S. 1984. Approximation time on a batch packing-an updated survey[J]. Algorithm Design for Computer System Design: 49-106.
Colorni A,Dorigo M,Maniezzo V,et al. 1991. Distributed optimization by ant colonies[C]. In: Proceeding of the first European Conference on Artificial Life,France,pp.134-142.
Damodaran P., Manjeshwar P. K.,Srihari K. 2006. Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms[J].International journal of Production Economics, 103(2): 882-891.
Dupont L.,Dhaenens-Flipo C. 2000. Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure[J]. Computers and Operations Research, 29(2002): 807-819.
Fan Hui-Yuan,Jouni Lampinen. 2003. A trigonometric mutation operation to differential evolution[C]. Journal of Global Optimization 27,Netherlands,pp.105-129.
Holland J. 1975. Adaptation in Natural and Artificial Systems[M].Ann Arbor: University of Michigan Press.
Kashan Ali Husseinzadeh, Karimi Behrooz, Jenabi Masoud. 2006. A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job size[sJ]. Computer and Operations Research,35 (2008): 1084–1098.
Kennedy J.,Ebethart R. C. 1995. PartieleswarmoPtimization[C]. In: Proeeedings of the IEEE Intemational Conference on Neural NetW0rks,Piscataway,NJ: IEEE Service Center,4: 1942-1948.
Melouk S.,Damodaran P.,Chang Ping-Yu. 2004. Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing[J]. International Journal of Production Economics,87: 141-147.
Monch Lars, Balasubramanian Hari, Fowler John W., et al. 2004. Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times[J]. Computer and Operations Research,32(2005): 2731–2750.
Monma C.L., Potts C.N. 1989. On the complexity of scheduling with batch setup times[J]. Operations Research,37: 798-804.
Lun P. B.,Hoitomt F. J.,Max E. 1990. Scheduling generation and reconfiguration for Parallel machines[J]. IEEE Transactions of Robotics and Automation,6(6): 687-697.
Omran M. G. H.,Engelbrecht A. P. 2009. Free Search Differential Evolution[C]. In: Evolutionary Computation, 2009. CEC '09. IEEE Congress on,Trondheim,pp. 110- 117.
Penev K. 2004. Adaptive computing in support of traffic management[J]. Adaptive Computing in Design and Manufacturing,20: 295-306.
Penev K.,Littlefair G. 2005. Free Search– a comparative analysis[J]. Information Sciences,172: 173-193.
Penev K.. 2006. Novel Adaptive Heuristic For Search And Optimisation[C]. In: Modern Computing, 2006. JVA '06. IEEE John Vincent Atanasoff 2006 International Symposium on,Sofia,pp. 149 - 154.
Price K. 1997. Differential evolution vs. the functions of the 2nd ICEC [C]. In: Proceedings of the IEEE Conference on Evolutionary Computation,USA,pp.153-157.
Price K.,Storn R. 1999. Differential Evolution (DE) for Continuous Function Optimization [EB/OL]. http://www.icsi.berkeley.edu/~storn/code.html.
Qin A. K.,Sugantlian P. N. 2005. Self-adaptive Differential Evolution Algorithm for Numerical Optimization[C]. In: The 2005 IEEE Congress on Evolutionary Computation(CEC’2005),Scotland,pp. 2:1785-1791.
Ray Tapabrata,Liew K. M. 2002. A Swarm Metaphor for Multiobjective Design Optimization[J]. Engineering optimization,34(2): 141-153.
Reklaitis G. V. 1995. Scheduling approaches for the batch process industries[J]. ISA Transactions,34(4): 349-358.
Salvendy Gavriel. 2005.调度:原理、算法和系统(第二版)(影印版)[M].北京:清华大学出版社.
Stewart I. 1983. Nonelementary catastrophe theory[J]. IEEE Transactions on Circuits and Systems,CAS-30(9): 663-670.
Stewart I. 1983. Applications of nonelementary catastrophe theory[J]. IEEE Transactions on Circuits and Systems,CAS-31(2): 165-174.
Storn R.,Price K. 1996. Minimizing the real functions of the ICEC’96 contest by differential evolution[C]. In: Proceedings of the IEEE Conference on Evolutionary Computation,Nagoya,pp. 842-844.
Sung C. S., Choung Y. I., Hong J M. 2000.Minimizing makespan on a single burn-in oven with job families and dynamic job arrival[sJ].Computer and Operations Research,29(2002): 995-1007.
Sung C. S.,Choung Y. I. 1998. Minimizing makespan on a single burn-in oven in semiconductor manufacturing[J]. European Journal of Operational Research,120(2000): 559-574.
Thom R. 1978. Towards a revival of natural philosophy[C]. In: Structural Stability in Physics,Tubingen,pp.5-11.
Thom R. 2006. The two-fold way of catastrophe theory[M]. Berlin: Springer press.
Uzsoy R. 1994. Scheduling a single batch processing machine with non-identical job sizes[J]. International Journal of Production Research,32(7): 1615-1635.
Veliev Erdoan,Penev Kalin. 2008. Visualization of free search process[C]. In: Artificial Intelligence Series, Proceedings of the 9th WSEAS International Conference on Evolutionary Computing ,Sofia,pp. 133 - 135.
Webster S., Baker K.R. 1995. Scheduling groups of jobs on a single machine[J]. Operations Research, 43(4): 692-703.
Wvong M. D.,Mihiring A. M. 1986. Catastrophe theory applied to transient stability assessment of power systems[J]. IEE Proceedings C (Generation, Transmission and Distribution),133(6): 314-318.
Xue F.,Sanderson A. C.,Graves R. J. 2005. Multi-objective differential evolution algorithm,convergence analysis, and applications[C]. In: The 2005 IEEE Congress on Evolutionary Computation (CEC’2005),Scotland,pp. 1: 743-750.
Yang Dongsheng,Mu Dong,Yao Mingzhi. 2009. Analysis of Financial Crisis: A Perspective Based on Catastrophe Theory[C]. In: Management and Service Science, MASS '09. International Conference onBeijing,pp. 1-4.
Zhang Guochuan, Cai Xiaoqiang, Lee C.-Y,et al. 2001. Minimizing makespan on a single batch processing machine with non-identical job sizes[J]. Naval Research Logistics, 48: 226-247.
Zhou Hui,Li Danmei,Shao Shihuang,et al. 2007. A Novel Intelligent Estimation Algorithm in WSN Location Based On Free Search[C]. In: Wireless Communications, Networking and Mobile Computing, 2007. WiCom 2007. International Conference on,Shanghai,pp. 2629- 2632.
Zhu Guangyu,Wang Jinbao,Guo Hong. 2009. Research and Improvement of Free Search Algorithm[C]. In: Artificial Intelligence and Computational Intelligence, 2009. AICI '09. International Conference on,Shanghai,pp. 235 - 239.