2023年7月24日发(作者：)

第２５卷第ｌ２期　计算机仿真　２ｏｏ８年ｌ２月　文章编号：１０ｏ６—９３４８（２０ｏ８）１２—０３２１—０４　基于分支定界和神经网络的实时调度策略　宋晔，杨根科　（上海交通大学自动化系，上海２Ｏ０２４０）　摘要：为解决一些对精度和实时性要求较高的调度问题，设计一个基于分枝定界算法和人工神经网络的实时调度算法。策　略先使用分枝定界算法来找到ｍ个作业的最佳排序。在生成足够多的排序以后，将排序作为训练样本来训练一个ｍ维人　工神经网络，从而得到一个ｍ维的人工神经网络主矩阵。在实际的生产环境中，先对实际到达的ｎ（ｎ＞ｍ）个作业进行分　组，再利用离线生成的人工神经网络主矩阵对每个分组进行初始排序。最后将每个分组看作一个整体，根据Ｐａｌｍｅｒ算法得　到ｎ个作业的最终排序。仿真表明疚策略具有较好的实时性，同时也能达到较高的精确性。　关键词：分支定界法；神经网络；启发式算法；实时调度　中图分类号：１　９１．９　文献标识码：Ｂ　Ｒｅａｌ　Ｔｉｍｅ　ＳｃＩｈｅｄｕＩｉｎｇ　Ｕｓｉｎｇ　Ｂｒａｎｃｈ—Ｂ０ｕｎｄ　Ａｌｇ０ｒｉｔｈｍ　ａｎｄ　Ａｒｔｉｆｉｃｉａｌ　Ｎｅｕｒａｌ　Ｎｅｔｗ０ｒｋ　Ｓ０ＮＧ　Ｙｅ．ＹＡＮＧ　Ｇｅｎ—ｋｅ　（Ａｕｔ０ｍａｔｉｏｎ瞻ｐａｒｔｍｅｎｔ，Ｓｈａｎｇｈａｉ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓ　Ｓｈａｎｇｈａｉ２００２４Ｏ，Ｃｈｉｎａ）　ＡＢＳＴＲＡＣＴ：Ａ　ｓｃｈｅｄｕｌｉｎｇ　ｍｅｔｈｏｄ　ｂａｓｅｄ　０ｎ　ｂｒａｎｃｈ—ｂｏｕｎｄ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ａｎｉ６ｃｉａｌ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ　ｉｓ　ｄｅｓｉｇｎｅｄ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｓｃｈｅｄｕ１ｉｎｇ　ｐｍｂｌｅｍ　ｗｉ吐Ｉ　ｓｔｒｉｃｔ　ｒｅｑｕｉｒｅｍｅｎｔ　ｆ０ｒ　ｒｅａｌ　ｔｉｍｅ　ａｎｄ　ａｃｃｕｒａｃｙ．　Ｉｎ　ｔｈｉｓ　ｍｅｔｈｏｄ，ｂｒａｎｃｈ　ｂｏｕｎｄ　ａｌｇ０－　一￡ｈｍ　ｊｓ　ｕｓｅｄ　ｔ０　ｆｉｎｄ　ａ　ｓｅｑｕｅｎｃｅ　ｆｏｒ　ｍ　ｊｏｂｓ．　Ａｆｔｅｒ　ｅｎｏｕｇｈ　ｓｅｑｕｅｎｃｅｓ　ａｒｅ　０ｂｔａｊｎｅｄ，ｆｈｏｓｅ　ｓｅｑｕｅ玎ｃｅｓ　ａｒｅ　ｕ　ｚｅｄ　ａｓ　ｔｒａｉｎｉｎｇ　ｅｘａｍｐｌｅｓ　ｔｏ　ｔｍｉｎ　ｎｅｕｒａｌｌ　ｅｔｗｏｒｋ．　Ｔｈｅｎ，ａ　ｍａｔｒｉｘ　ｃａｌｌｅｄ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ　ｍａｔ　ｘ　ｉｓ　ｏｂｔａｉｎｅｄ．　Ｉｎ　ｔｈｅ　ｒｅａｌ　ｐｍ－　ｄｕｃｔｉｏｎ　ｅｎｖｉｍｎｍｅｎｔ，ｎ（ｎ＞ｍ）ｊｏｂｓ　ａｒｅ　ｄｉｖｉｄｅｄ　ｉｎｔｏ　ｓｅｖｅｒａ１　ｓｍａＵ　ｇｒ０ｕｐｓ．　Ａｓ　ｔ０　ｅａｃｈ　ｓｍａＩＩ　ｇｍｕｐ，ｎｅｕｒａ【ｎｅｔｗｏｒｋ　ｍａｓｔｅｒ　ｍａ　ｘ　ｉｓ　ｕｓｅｄ　ｔｏ　ｆｉｎｄ　ｍ　ｊ（＇ｂｓ’ｓｅｑｕｅｎｃｅ．　Ｆｉｎａｌ１ｙ，ｅａｃｈ　ｇｒｏｕｐ　ｉｓ　Ｉｅ＿ｇａｒｄｅｄ　ａｓ　ａ　ｗｈｏｌｅ　ａｎｄ　Ｐａｌｍｅｒ　ａｌｇ０ｒｉｔｈｍ　ｉｓ　ｕｓｅｄ　ｔｏ　ｆｉｎｄ　ｔｈｅ　６ｎａｌ　ｓｅｑｕｅｎｃｅ　’ｎ　ｊｏｂｓ．　Ｓｔｉｍｕｌａｔｉ０ｎ　ｄｅｍｏｎｓｔｒａｔｅｓ　ｔｈａｔ　ｔｈｉｓ　ｍｅｔｈｏｄ　ｃｏｓｔｓ　ｆｅｗｅｒ　ｔｉｍｅ　ｔｈａｎ　ｂｒａｎｃｈ—　ｂｏｕｎｄ　ａｌｇ０ｒｉｔｈｍ　ａｎｄ　ｐｅｒｆ０丌ｎｓ　ｗｅＩ１　ｉｎ　ａｃｃｕｒａｃｙ．　ＫＩ　，ｏＲＤＳ：Ｂｒａｎｃｈ—ｂｏｕｎｄ　ａｌｇ０ｒｉｔｈｍ；Ｎｅｕｍｌ　ｎｅｔｗｏｒｋ；Ｈｅｕｒｉｓｔｉｃ　ａ１ｇｏｒｉｔｈｍ；Ｒｅａｌ　ｔｉｍｅ　ｓｃｈｅｄｕｌｉｎｇ　法　等）和分枝定界法０　。启发式算法的计算量相对较小，　１　引言　可以满足一些实时性要求较高的调度，但通常只能求得近　在流水线的实际调度问题中，为了给生产企业带来更大　优解。　的经济效益，管理者一般希望作业的调度算法具有较高的精　为了同时满足实时性和精确性Ｉｎ　Ｉ艘和Ｍｉｃｈａｅｌ　Ｊ．　确性和实时性。但是如果实际问题中需要被调度的作业数　ｓｈ．ｄｗ提出了利用精确算法离线训练人工神经网络并在线利　量达到一定的规模，要同时满足精确性　阳实时性往往是非常　用该人工神经网络进行实时调度的方法　Ｊ。在这以后Ａ．　困难的。　Ｎｏｏｒｕｌ　Ｈａｑ・Ｔ．Ｒａｄｈａ　Ｒａｍａｎａｎ又将这个思想运用到多目　目前对于ｎ０Ｗｓｈｏｐ排序问题，常见的目标函数是极小化　标调度问题上　Ｊ。但是这些算法针对的调度问题的维数大　Ｍａｋｅｓｐａｎ完工时间和加权总完成时间，当处理机数多于２　都被离线训练时人工神经网络的维数所限制。　台时，这些问题往往不存在多项式算法　对于这些问题常用　为了解决大维数的调度算法，在调度算法中加入了分组　的方法是启发式算法（Ｐ８ｌｍｅｒ算法　，（：ＤＳ算法¨】，Ｇｕｐｔａ算　的思想，利用离线训练好的人工神经网络矩阵对各个分组进　基金项目：国家自然科学基金（６ｏ５７４０６３）　行排序。最后将每个分组看作一个整体，对这些整体应刚　收稿日期：２０ｏ７一ｌＯ一０８修回日期：２０ｏ７一Ｉ１一ｌ９　Ｐａｌｍｅｒ算法，得到整个序列的近优解。　一３２１～