2．分配问题的改进蚁群算法
（1）编码
采用加工任务序列随机排序的编码方式，每次迭代中每只蚂蚁都对所有的加工任务随机排序，并且蚂蚁都按照自身的排序进行加工任务的分配。
（2）状态转移方程
（3）信息素更新策略
蚁群算法中信息素的更新策略，M-Dorigo曾经提出了三种模型，蚁量系统模型、蚁密系统模型和蚁周系统模型。本研究将采用蚁周系统模型中的信息素更新方法。
（4）停机规则
本文采用迭代次数阀值作为停机规则，即当迭代次数达到预定的阀值时，便停止运算，输出运算结果。
4.2.算法流程
根据本文中对MDMS多目标生产计划模型的描述和算法的设计，分以下几个步骤对模型进行求解。
step1：计算本次装配作业的最大节拍和最小节拍，根据最大最小节拍运行Ⅰ类装配问题的模拟退火算法，求得最小、最大装配线条数。将最大装配线条数与PAC拥有装配线条数进行比较并取小，最后求得一个装配线条数的闭区间。
step2：由于装配线条数是离散变量，所以根据step1求的闭区间，将闭区间内所有的元素依次运行Ⅱ类装配问题的模拟退火算法，最后求得相对应的装配线节拍集合。
step3：根据step2中求得的装配线节拍，计算出对应的从CMC运送加工任务到PAC的时间，即。计算相应的制造时间。
step4：在生产制造时间内，运行分配问题的改进蚁群算法，对应每一个节拍给出一个分配方案和相应的制造成本。
step5：最后生成一个由制造成本和装配线条数构成的二维数组，便为本多目标模型的帕累托有效解。
5.仿真计算
假设某MDMS由制造级（4个CMC成员企业）和装配级（1个PA）组成，PAC中有装配线10条。有20个订单被分解为10个加工任务，假设初始时间为0，订单的交货时间为41，上批订单在PAC的完工时间是6。如果时间紧迫MDMS可以直接购买加工任务的产成品，但是其价格一般较高。
可以看出，本文算法具有以下优点：
（1）多解性。较好的实现了多目标优化，并给出了帕累托不同方向的效率解，为决策者提供多个选择。（2）近优性。通过对帕累托解集中（66，8）点的反复运算，正如其解的搜索过程所示，此结果已是最优结果。因而该算法具有较好的优化质量。（3）鲁棒性。尽管算法中均采用随即初始化，但是求解结果在帕累托意义下基本一致，由此说明了算法较好的初值鲁棒性。（4）时间可接受性。运行一次本算法的时间为58秒，因而在计算时间上是可以接受的。
6.结论
分布式制造系统的生产计划问题是目前生产管理中常见的决策问题，也得到了广泛的理论研究和实践应用。本文将多级生产制造过程统一到一个多目标模型中，模型求解出的帕累托解集可以为决策者提供多个选择，对生产经营有较大的实践意义。本文针对该模型提出了基于蚁群算法和模拟退火算法的分布式制造系统的生产计划求解方案，由于蚁群算法本身固有的一些缺陷，本文在以往文献的基础上对算法进行了改进，引入控制因子和退火扰动因子，从而增强了蚁群算法全局寻优的能力，仿真实例证明算法是有效的。本文算法也存在一个缺陷，那就是要求目标函数中至少有一个是离散的或者需要将目标函数中一个离散化。设计没有以上离散化要求的求解算法是下一步值得研究的问题，
参考文献
Kirkpatrick S，Gelatt C D，Jr Vechi M P.Optimization by simulated annealing [J].Science，1983，220：671-679
Attiya G，Hamam Y.Task allocation for maximizing reliability distributed systems：A simulated annealing approach [J]．Journal of Parallel an Distributed Computing，2006，66：1259-1266
Golderg D E．Genetic Algorithm in Search：Optimization and Machine Learning[M]．Reading：Addison Wesley Publishing Company，1989
钟求喜，谢涛．基于遗传算法的任务分配与调度[J].计算机研究与发展，2000，37（10）
王秀宏，王正欧，乔清理．用具有混沌特性的神经网络解任务分配问题[J]．系统工程学报，2001，l6（2）：146-150
Chen W H，Lin C S．A hybrid heuristic to solve a task allocation problem [J]．Computers and Operations Research，2000，27：287-303
高尚，杨静宇.智能群算法及其应用[M].北京：中国水利水电出版社，2007，24-28
Metropolis N，Rosenbluth A.Equation of state calculations by fast computing machines [J].Journal of Chemical Physics，1953，21，1087-1092
Kirkpatrick S，Gelatt Jr C D，Vecchi M P.Optimization by simulated annealing[J].Science，1983，220，671-680
赵良辉，邓飞其.用于车间作业调度的模拟退火算法[J].制造业自动化，2006（3）：10-12
Holsapple C W，Jacob V S，Pakath R，Zaveri J S.A genetics-based hybrid scheduler for generating static schedules in flexible manufacturing contexts [J].IEEE Trans.On System，Man，and Cybernetics，1993，Vol.23，No.4，953-972
Becker C，Scholl A、A survey on problems and methods in generalized assembly line balancing[J].European J．Operational Research，2006，168（3）：694-715
A Study on production planning for a multi-stage
distributed manufacturing system
WANG Xue-fengCHEN Zhi-xiang
（School of Business，Sun Yat-sen University，Guangzhou Guangdong 510275，China）
Abstract：The partner enterprises’ resources of the manufacturing enterprise alliances have the characteristics such as autonomous，distributed and heterogeneous.An effective solution is put forward for the production planning of a multi-stage distributed manufacturing system（MDMS）composed by many component manufacturing company（CMC）and a product assembling company（PAC）.This paper will focus on the task assignment based on the components manufacturing and assembling line balance based on the assembling process to formulate a mathematical model accordingly.Because the model is a NP-hard problem，an improved heuristics algorithm based on ant colony algorithm（ACA）and simulated annealing algorithm（SA）is presented.The numerical simulation shows the effectiveness of the algorithm.
Keywords：MDMS；task allocation；assembly line balancing；ant colony algorithm，simulated annealing algorithm
