摘要
讨论 Job shop排序问题不可行解的构造情况 ,给出了不可行解的一个充要条件以及 2台机器n个加工工件的 Job shop问题不可行解和可行解的计算公式 ,并由此得到一种概率模型的计算方法。通过计算发现 ,Job
Job 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.
出处
《控制与决策》
EI
CSCD
北大核心
2001年第1期33-36,共4页
Control and Decision
基金
国家自然科学基金项目 !(79430 0 2 2 )
