关于一类两台机器自由作业的排序问题

On the scheduling problem of two machine open-shop

以工件完工时间的总和为优化目标的两台机器自由作业问题是NP-hard问题.本文针对加工时间仅依赖于机器并且机器连续加工的问题,给出了机器排序是可行排序的充分必要条件,引入可行排列的极小子排列的概念,运用组合优化方法,研究了最优排序中极小子排列的性质,并由此得到了该问题的最优时间表的一般构造方法.

Two machines open-shop problem taking the sum of fulfilling work time as the optimum objective is NP-hard problem. In this paper, to resolve the problem that the processing time is only dependent upon machines and the machines are continuously working, a necessary and sufficient condition that ensures the scheduling of machines feasible is given, a conception of minimal sub-permutation is introduced, and the property of minimal sub-permutation in the optimal arrangement is studied by applying combinatorial optimizing method. Finally, a construction method of an optimal schedule about the problem above is proposed.