下载掌阅APP，畅读海量书库
立即打开
逆调度（Inverse Scheduling Problem，ISP）可以被定义为：如何对给定加工参数的估计值进行尽可能“小”的调整，在此基础上得到这些参数的改变值，从而使得一个原先的可行调度在该情况下变成最优调度。
最近几年，逆优化在计算机技术飞速发展的基础上被提出，并逐渐被应用于不同领域，取得了许多研究成果。这些研究工作对系统管理科学和计算机科学的理论与实践有着十分重要的意义。借鉴逆优化问题（或称反问题）的理论与方法，“逆调度”作为一种新的调度方法被提出，并逐渐引起部分学者的关注。为了更加具体地说明车间逆调度问题，下面以带交货期的单机逆调度问题为例进行说明。某单机生产车间接到一批特殊加工订单，每种产品的加工时间已知，生产加工前客户和生产者依据经验或估计的交货期制订了相应最优加工路线，然而在实践生产中往往有许多不确定因素，使得真实的加工参数与估计值不同，当前的调度顺序很可能导致无法按时交货，而后续工序约束使得产品加工顺序无法随意调整。为了解决此问题，生产者可以与客户沟通协商，通过调整某些产品的交货期来保证按期交货，使得客户满意度达到要求。此问题可以通过逆调度解决。
在生产管理中，车间的状况经常不确定，这就使得初始优化的调度方案往往由于车间状态的变化而失去最优性，有时甚至变为不可行，优化失去意义。以往的解决思路是进行重调度或动态调度，这些方法通过不断调整调度方案适应环境的变化，有时会忽略调度的变化对车间其他活动造成的影响，并且频繁调度对系统的稳定性产生较大影响。针对以上情况，逆调度的思路通过调整加工参数来保证调度方案满足期望。目前，逆调度的研究刚刚起步。通过逆调度研究现状分析可以发现，早在2005年，Koulamas首次研究了加工参数可控的单机逆调度问题，随后Brucke教授于2009年在一篇论文中将此类问题定义为逆调度问题，但之后鲜有关于逆调度的研究成果。这并不是由于逆调度缺少实际应用，而是由于问题本身的复杂性，以及逆调度问题的研究背景不足等，限制了对逆调度问题的深入研究。
通过调查研究分析发现，现实生产中存在一定的应用场景可以采用逆调度去解决，可将其概括为以下两大类：
（1）调度顺序受制约的情况。在某些实际生产中，生产调度是生产制造系统的功能模块之一，它负责将制造资源分配给由工艺加工计划所决定的零件加工工序，以满足加工性能指标。因此，调度功能受到工艺加工计划和制造资源的双重制约，考虑到零件的制造加工路线是计算机集成制造系统中的关键问题，一旦调度系统进行扩展和重构，就可能导致生产计划的变更或工艺路线的调整，这样的组织方式忽略了真实生产对调度顺序的制约。
（2）加工参数不确定的情况。以前车间调度问题的研究大多集中于纯确定性的问题，在确定的车间调度问题中，工件的加工时间和交货期都是已知的精确量，生产也处于理想状态；而实际生产调度系统中往往存在大量不确定因素，如因工人技术状况、身体状况、原材料差异、机床状态与刀具情况不同带来的时间不确定，工件到达时间的不确定，交货期的不确定等。针对加工参数可变、可控的调度问题，可以采用逆调度进行优化。
综上所述，通过逆调度的研究可以改善既有调度方案的性能，并能快速响应车间调度中出现的状况，以最小的改变实现最优的调度调整。本书对逆调度问题进行深入研究，不仅能推动车间调度理论和方法的新发展、丰富逆优化问题的研究，还能解决实际生产调度中所面临的关键问题，具有重要的科学意义和较大的工程应用价值。
目前，国际上对逆调度的研究刚刚起步，其研究成果还很有限。从模型研究来看，只是研究了单机供应链逆调度及两台机器流水车间逆调度等简单问题，主要以加工完成时间和最小为目标。下面将对已有逆调度问题模型进行介绍，本书的模型都是在此基础上进行拓展的。
1.单机逆调度问题
逆调度的核心思想是最小限度地调整参数值，使得原定的工件排序达到最优，这与参数可控的排序问题在某种程度上有共同之处。虽然逆调度问题的研究成果较少，但国际上很多学者对参数可控的排序问题进行了研究。Vickson（1980年）讨论了工件加工时间可控的单机问题，该问题的目标是通过最小化调整加工时间，来确定一个最优调度顺序。Nowicky和Zdrzalka（1990年）对加工时间可控的排序问题进行了比较深入的调查研究，分析了加工参数可控问题的研究现状。Chand和Chhajed（1992年）则研究了参数可控的单机问题模型，通过调整交货期来满足调度期望。另外，Trick（1994年）等人也对加工参数可控的排序问题进行了不同程度的研究。2005年，Koulamas发表了一篇关于加工参数可控的逆排序的论文，并基于John规则讨论了FSP逆排序问题。此外，国内学者陈荣军等人对单台机器总完工时间逆排序问题也进行了探讨。
针对以上研究，虽然有些研究并非真正意义上的单机逆调度问题，但是它们具有一个共同特点，即都是考虑加工参数可控的一类调度问题，因此在模型的建立和问题求解方法上可以为我们提供一些启发。首先从模型上进行分析，现在已有的单机逆调度模型包括以最大拖期为目标的单机逆调度模型及单台机器总完工时间逆调度问题模型。
以最大拖期为目标的单机逆调度模型1|| L max 如下：
假设 N 个工件在一台机器上加工，给出不同工件的加工时间 P j 及交货期 d j ，同时给出在这台机器上的一个工件排序 π 。假设不考虑工件加工的优先权，且在0时刻每个工件都可以开始加工。要求最小限度地调整 P j 或 d j ，使得给定的工件排序 π 最优。这里对两种情况进行分析，一种是 P j 不变调整 d j ，另一种是 d j 不变调整 P j 。下面分别针对这两种情况给出相应的模型：
（1）固定 P j 调整 d j ，使得工件排序 π 最优
对于这种情况，每个工件的交货期
d
j
都有一个变化区间
，且
，调整后的交货期为
，且
，
j∈ N
，目标函数要求最小限度地调整
d
j
，使得给定的排序
π
最优，同时满足调整后最大超期不大于调整前，即
（2）固定 d j 调整 P j ，使得工件排序 π 最优
与上面情况类似，每个工件的加工时间
P
j
也都有一个变化区间
且
，调整后的加工时间为
，且
，
j∈ N
要求最小限度地调整
P
j
，使得给定的排序
π
最优，即
2.流水车间逆调度问题
国内外关于流水车间逆调度的研究刚刚开始。2009年，陈荣军和唐国春研究了流水车间的逆排序问题，根据调整参数的不同，利用排序理论把这些逆问题表示为相应的数学规划形式。2011年，Brucker和Shakhlevich对这类问题进行了进一步研究，重点探讨了两台机器的流水车间逆调度问题。
这个问题的描述如下：机器A和机器B上对应的工件加工时间分别为 a 和 b ，两台机器上的工件排序分别为 π 和 σ （ π 和 σ 可能相同，也可能不同）。同时工件的序号与工件在机器上的排序相对应，即 π =（1，2，…， n ）。对于给出的 a j 和 b j ， π 和 σ 可能不是最优排序，目标为最小限度地调整加工时间 a j 和 b j ，使得工件的排序成为最优排序。
在相关文献中，Brucker和Shakhlevich用
F
2
|adjustablea
j
，
b
j
，
π
，
σ|C
max
表示该逆问题。需要调整的加工时间
和
，加工时间需要在给定的范围内调整，即
。因此，该问题要使目标值和加工参数调整量最小，并且让机器A和机器B上的工件排序达到最优，同时满足调整后的最大完工时间小于调整前。模型如下：
