下载掌阅APP，畅读海量书库
立即打开
由逆调度的概念可知，在某种意义上，正调度的研究有助于最优调度方案的生成，逆调度的研究则有助于改善既有调度方案的性能。当前，国内外对逆调度的研究较少，主要包括简单的车间类型及小规模的问题，并且缺乏相应的求解方法。
近年来，国内许多学者陆续对逆调度进行了初步研究。例如，陈荣军、唐国春等人采用数学规划方法，讨论了单台机器的逆调度问题，该问题的优化目标是总加权完工时间最小，讨论不同范数距离情况下的求解方法，最后设计了多项式时间算法进行求解。同时他们还研究了无加权情况下，加工时间和最小的逆问题及其求解策略；2009年，陈荣军、唐国春研究了单台机器供应链逆排序问题和流水作业逆排序问题，根据调整参数的不同，利用排序理论将不同的逆问题表示为相应的数学规划形式，给出了三个供应链逆排序问题的数学模型及两台机器的流水作业逆问题数学模型，但如何有效地求出这些逆排序问题的解，仍没有确定方法，值得我们继续研究。2012年，越南学者Pham和华南理工大学学者鲁习文研究了不同距离下的平行机逆排序问题，考虑以最小化总加权完工时间为目标，即针对已给的调度顺序，在同时保证目标函数值不超过原来值的条件下，通过调整工件的权重值来满足原始顺序最优，针对此类问题，利用线性规划和二次规划求得逆问题的最优解。此外，还有几篇相关文献中提到了关于加工参数调整的逆调度问题。
车间逆调度问题是一个困难的NP-hard问题。2009年，Brucke教授在一篇论文中首次研究逆调度问题，并讨论了单机逆调度问题，涉及的参数分别是加工时间、交货期，以最小化最大拖期为目标，分别讨论了该问题在五种距离下的求解方法，最后证明此问题在不同情况下都是NP-hard问题。随后，2011年，Brucke和Shakhlevich进一步研究较为复杂的车间环境，以及两台机器的流水车间逆调度问题，提出了关于两台设备的流水车间逆调度问题模型，采用线性规划的方法简化模型，并针对模型分析了有效的求解条件，最后证明了流水车间逆调度问题中求得最优解的充要条件，同时证明两台机器的流水车间逆调度问题也是一个NP-hard问题。研究表明，在Brucke提出逆调度概念之前，已有几位学者对逆调度问题进行了初步研究。2005年，Koulamas研究了关于加工时间可控（Controllable Job Processing Times）的逆排序问题，同时基于John规则探讨了流水作业（Flow-Shop Problem，FSP）的逆排序问题，针对这两类问题，分别建立了相应的数学模型，提出时间多项式求解方法。