Job Shop排序问题解空间定量分析  

Quantitative Analysis of Infeasible Solution to Job Shop Scheduling Problem

作　　者：王波[1] 张群[2] 王飞[1] 韦有双[1] 

机构地区：[1]北京航空航天大学经管学院,北京100083 [2]北京科技大学管理学院,北京100083

出　　处：《控制与决策》2001年第1期33-36,共4页Control and Decision

基　　金：国家自然科学基金项目 !(79430 0 2 2 )

摘　　要：讨论 Job shop排序问题不可行解的构造情况 ,给出了不可行解的一个充要条件以及 2台机器n个加工工件的 Job shop问题不可行解和可行解的计算公式 ,并由此得到一种概率模型的计算方法。通过计算发现 ,JobJob Shop scheduling problem (JSSP) is a well-known NP-hard problem. The construction of infeasible solution to JSSP was analyzed and a necessary and sufficient condition of infeasible solution was given. For a JSSP with 2 machines and n jobs., a recurrence formula was proposed for calculating the infeasible solution, thus a calculating method in terms of probability was obtained. The proportion of infeasible solution is over 90% if the number of n is small. If there are more than 2 machines, the proportion of infeasible solution would be still high, and the calculation for infeasible solution becomes more complex due to the formation of deadlock pair.

关 键 词：排序 死锁 不可行解 JoBShop问题 

分 类 号：O223[理学—运筹学与控制论]