缓冲器容量限制的Job-Shop调度问题的递归算法

Recursive Algorithm for Job-Shop Scheduling with Buffer Restriction

研究工序之间每个缓冲器容量限制的条件下,生成可行的计划调度方案的算法。其基本方法是形成初始排产方案,检查每个设备等待加工工件的体积,如果该堆积量没有超过该设备的容量限制值,则通过检验;反之,则反查造成超限的每一个工件在前一道工序的设备的缓冲器剩余量,用该剩余量冲销超限的体积,如果不可操作,则递归采用同样的办法检验造成此超限的更前面的设备组合的情况。当所有剩余量矩阵的元素都大于等于0,则该排产方案可行。主要创新在于提出了缓冲器容量流转方案的递归算法和缓冲器容量限制下的调度问题的极大极小代数法解法。

The algorithm of feasible plans of scheduling under the conditions that satisfy every buffer capacity restriction is studied. The algorithm is to develop an initial plan of scheduling, to calculate the volume of every part waiting for processing at the equipment, if it does not exceed the capacity restriction value of this equipment, it is normal; Otherwise, traces back to surplus quantity of the buffer capacity for each part which cause to exceed the buffer capacity limit at its previous equipment, eliminates the excess of volume with the surplus quantity; If the elimination is not successful, the more previous workpiece- equipment surplus quantity is examined by the recursive method. If every element of all surpluses matrixes is more than or equal to 0, the scheduling is eventually feasible. The main innovation is the recursive method of buffer filling circulation and scheduling algorithm for buffer capacity restriction on Maxim and Minimum Algebra.