井下机车运输调度的资源分配模型及无死锁优化调度  

Resource allocation model and deadlock-free optimization scheduling for underground locomotive transportation

作　　者：方欢[1,2] 陆阳[1] 徐自军[3] 杨娟[1] 

机构地区：[1]合肥工业大学计算机与信息学院,合肥230009 [2]安徽理工大学理学院,淮南232001 [3]合肥工大高科信息技术有限责任公司,合肥230088

出　　处：《系统工程理论与实践》2013年第8期2087-2096,共10页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(60873195;61070220);高等学校博士点基金(20090111110002);安徽省高等学校省级自然科学研究重大项目(ZD200905)

摘　　要：对井下机车运输系统进行无死锁调度和性能优化,首先,建立三种不同调度策略下的资源分配Petri网模型,设计对应调度策略下无死锁标识的最大边界设置算法,证明了调度策略在最大标识边界设置下的无死锁性.然后,以最小化时耗和能耗为优化目标,利用遗传算法,采用变迁标号的自然编码方式,通过检查变迁的引发条件检测染色体的可行性,修复不可行的染色体使其对应的调度满足资源约束,从而保证了算法所利用的所有染色体均可对应系统的可行调度,最后进行实例仿真.设计的无死锁调度的最大标识边界设置算法和遗传算法为井下机车的运输调度提供了可靠的理论基础.A deadlock-free scheduling scheme and optimization for underground locomotive transportation system are presented. Firstly, three resource allocation Petri net models under different dispatching policies are modeled, their corresponding maximM makings boundary setting algorithms are designed, and the deadlock-free property of dispatching under maximal marking boundary setting is proved. Then, a genetic algorithm is proposed to minimize the time cost and energy cost, in which the transitions sequence is encoded as a chromosome, the feasibility of chromosomes are tested and amended by judging the transition firing condition, so that each chromosome can be decoded into a feasible schedule to satisfy all resource allocation constraints. Finally, an experimental example is simulated. The designed maximal marking boundary setting algorithm of deadlock-free schedule and genetic algorithm provide reliable theoretical foundation for underground locomotive transportation dispatching.

关 键 词：运输调度 资源分配模型 无死锁调度 调度优化 PETRI网 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]