初始工件带有释放时间的返工工件重调度的分段插入方法

摘要

初始工件带有释放时间的返工工件重调度的分段插入方法，根据初始调度有机器空闲的特点，有效的利用了机器空闲时间和初始工件可延迟的最大时间。根据返工工件和生产一个新工件相比通常具有初始时间较短的特点，将返工工件按照SPT(越短处理时间越早加工)的规则，尽可能多的插入初始调度，无法插入的返工工件则追加到最后按照SPT规则依次调度。该算法保证了决策的有效性，在保持了原生产系统稳定的前提下，极大的提高了生产效率。本发明针对RRJS生产问题提供了切实可行的重调度算法，该算法的提出对于RRJS生产问题中返工工件的重调度有一定的参考价值，对提高我国这类生产系统领域中的返工重调度算法具有重要的指导意义。

主权项

初始工件带有释放时间的返工工件重调度的分段插入方法，其特征是具体步骤如下：第1步：将返工工件按照处理时间的非降序排列，得到一个调度ω，使得为包含在调度ω中且已经按照处理时间非降序排列的n_R个返工工件，[j]表示第j个位置的工件号，计算第j个位置之前的所有返工工件的处理时间和B_[j]，其中为工件号为[j]的返工工件的处理时间，n_O为初始工件的数量；第2步：i＝1按下列步骤执行：第2.1步：如果并且执行第2.1.1步；如果则σ＝σ|υ；如果则σ＝σ|ω；第2.1.1步：如果且初始调度υ中初始工件的开始加工时间等于它的释放时间r_[i]，即$s_{\left[i\right]}^O\left(\upsilon \right)=r_{\left[i\right]},$则计算${\Delta }_{min}^O\left(\upsilon \right)=\underset{n=1,\mathrm{...},j-1}{\min }\left\{{\Delta }_{\left[n\right]}^O\left(\upsilon \right)\right\},$$\Delta =\min \{{\Delta }_{\min }^O\left(\upsilon \right),r_{\left[i\right]}-C_{[i-1]}^O\left(\upsilon \right)\};$选择执行第2.2步，否则i＝i+1；如果i≤n_O执行第2.1步，如果i＞n_O则执行第2.2步；第2.2步：如果B_[j+1]＞Δ+I^％，I^％表示在前一段插入返工工件之后紧挨着当前段之前的剩余空闲，在υ之前插入包含了调度ω中工件号为[1]至[j]返工工件的集合为调度ω中工件号为[j]的返工工件，否则更新υ中工件的所有开始时间,使的开始时间等于如果为初始工件在初始调度υ中可以延迟的最大时间；否则$J_O^{\%}=\{j_{\left[1\right]}^O\left(\upsilon \right),...,j_{\left[m\right]}^O\left(\upsilon \right)\};$$\sigma =\sigma \left|J_R^{\%}\right|J_O^{\%},$$\upsilon =\upsilon -J_O^{\%},$$I^{\%}=[(r_{\left[i\right]}-C_{[i-1]}^o(\upsilon \left)\right)-{\Delta }_{\min }^O\left(\upsilon \right)],$返回到第2.1步；第1步和第2步中上角标表示工件类型，即O表示初始工件，R表示返工工件，小括号内符号表示调度类型，即υ表示初始调度，σ表示重调度，w_max(σ)表示重调度中返工工件的最大等待时间；C_i和s_i分别表示工件j_i的完工时间与开始时间，表示初始工件可以延迟的最大时间，I表示机器空闲时间和；α|β表示子调β紧接着子调度α后执行的调度。