车间作业调度的可行化判定及不可行解的纠正  

Feasibility Verification of Job Shop Schedules and the Correction of Infeasible Schedules

作　　者：赵良辉[1] 王天擎[1] 

机构地区：[1]五邑大学经管学院,广东江门529020

出　　处：《数学的实践与认识》2013年第11期12-19,共8页Mathematics in Practice and Theory

基　　金：广东省自然科学基金(8452902001001552)

摘　　要：生产调度过程中出现不可行解是调度研究经常遇到的问题之一.提出了对JSP调度方案进行可行化判定和纠正不可行解的可行算子,算子包括了基于有向图拓扑排序原理对车间作业调度方案进行可行判定的方法和将不可行解纠正为可行解的算法.证明了该纠正算法总能成功,并对算子的功能进行了拓展使之还可应用于不完备调度.最后讨论了可行算子的特点、时间效率和应用前景.The existence of infeasible schedules is a familiar problem in solving Job shop problems. A feasibility operator is proposed, which includes two parts： the one is the method of verifying the feasibility of job shop schedules based on directed graph theory, the other is the correcting algorithm for infeasible schedules, whose validity is also proved in the paper. The operator＇s function is still expanded to deal with incomplete schedules. The rear part of this paper analyzes its efficiency, application and factors that need to be improved.

关 键 词：作业车间调度问题 可行解 析取图 拓扑排序 

分 类 号：O157.5[理学—数学] O223[理学—基础数学]