CN101256401B - 用于确定钢板的加工顺序的系统和方法 - Google Patents

Abstract

提供了一种用于确定钢板的加工顺序的系统，该系统包括：约束存储单元，用于存储位置约束，该位置约束限定了当按所述加工顺序排列钢板时每类钢板要被插入到的位置的范围；选择单元，用于优选地选择在满足所述位置约束的同时具有可以被进一步插入到已经按所述加工顺序排列的钢板队列中的钢板的数量的较大期望值的位置，作为在所述钢板队列中新钢板要被插入到的位置；以及插入单元，用于将所述新钢板插入到所选位置，并用于输出指示插入后的钢板队列的数据。

Description

用于确定钢板的加工顺序的系统和方法

技术领域

本发明涉及用于确定产品的制造加工的技术。具体地，本发明涉及用于确定加工要被依次加工的多个钢板的顺序的技术。

背景技术

钢板通过热轧(hot rolling)加工来产生各种厚度和尺寸的钢片。在热轧加工中，通过轧压由轧钢厂的一组工作滚轮(work roll)从上和下夹住的称作厚板(slab)的厚钢板，来从该厚板中产生称作薄板(coil)的薄钢片。如此产生的薄板的表面质量取决于工作滚轮的表面状况。另外，使用某一组工作滚轮一个接一个地轧压多个厚板逐渐地恶化工作滚轮的表面状况。由于此原因，优选地在滚轮还是新的时用这组工作滚轮来进行要求高质量的钢板轧压。

此外，轧制钢板有时会在工作滚轮的表面留下与钢板一样宽的凹槽(groove)。因此，由在较早时轧压的较窄钢板留在工作滚轮表面上的凹槽可能有时可能在稍后轧压的较宽钢板的表面上留下瑕疵。另外，轧压装备等的规范将成功轧压的两个钢板之间的厚度差限制为某一范围。此外，尤其不能连续轧压大量较薄的钢板，以便防止工作滚轮耐用性的恶化。在这点上，已经使用了用于确定轧压钢板的顺序的技术，以便保持钢片的质量并提高产量，同时满足上述的各种约束。

[非专利文件1]

“Hot Mill Scheduling，”Tokyo Research Laboratory，IBM Japan，Ltd.，URL“http://www.research.ibm.com/trl/projects/optimization/hsm_e.htm，”搜索于2007年1月31日。

在前述技术中，称作局部改进(local improvement)的方法被用于进一步改进已经被试图确定的在一定程度上有效的草案轧压顺序。通过首先引入指示加工钢板的效率的估计值来进行局部改进处理。在此，该估计值随着可以被一组工作滚轮加工的钢板的数量和总长度的增加而增加，或者随着可以被一组工作滚轮加工的高质量钢板的数量的增加而增加。那么，当将另外的某一钢板插入已经按加工顺序排列的钢板的队列中时，判断估计值是否增加。当估计值增加时，插入该某一钢板，并且按新的顺序对新的钢板队列进行加工。估计值的增加的程度可能取决于该某一钢板插入的位置而不同。在这种情况下，将钢板插入到提供最高的估计值增加程度的位置。在这种插入处理中，检查要被加工的所有钢板。

当仅通过在该局部改进处理中使用这种估计值来确定插入位置时，如此确定的加工顺序在某些情况下的确不是有效的。这是因为在局部改进的较早阶段插入的钢板禁止将在稍后阶段插入的其他钢板满足约束。例如，假定存在约束：在加工顺序中的某种钢板的位置必须不大于某一上限数。在这种假设下，一旦将这类新钢板插入接近上限数的位置，则变得难以在该新钢板前再插入另一钢板。以这种方式，当仅通过使用指示加工效率的程度的估计值来进行局部改进时，在某些情况下局部改进可能会最终确定无效的加工顺序。

在这点上，本发明的目标是提供能够解决上述问题的系统、方法和程序。通过结合权利要求范围内的独立权利要求中所述特征来实现该目标。另外，从属权利要求限定了本发明的更有利的具体示例。

发明内容

用于解决前述问题的本发明的第一方面提供了一种用于确定钢板的加工顺序的系统。该系统包括约束存储单元、选择单元和插入单元。具体地，约束存储单元存储位置约束，该位置约束限定了当按加工顺序排列钢板时每类钢板将被插入的位置的范围。作为在已经按加工顺序排列了的钢板队列中插入新钢板的位置，选择单元优先选择在插入新钢板后可以进一步插入到钢板队列中的钢板数量的期望值更大同时满足位置约束的位置。然后，插入单元将新钢板插入所选位置中，并在插入后输出指示钢板队列的数据。另外，提供了一种使得信息处理装置运作为通过使用该系统确定钢板的加工顺序的系统的程序和方法。

注意，上述本发明的概要不是包括本发明的所有必要特征的穷举列表，并且本发明中可以包括这些特征的任意子组合。

附图说明

为了更全面地理解本发明及其优势，结合附图参考下面的描述。

图1示出钢板加工装置10的整体结构。

图2示出属性存储单元150的数据结构的例子。

图3a和3b示出问题存储单元160的数据结构的例子。

图4示出加工操作的加工顺序的例子。

图5a和5b是每个示出位置约束的例子的概念图。

图6示出在不受位置约束限制的钢板后可插入的钢板数量的变化。

图7示出在受位置约束限制的钢板后可插入的钢板数量的变化。

图8示出顺序确定系统140的功能结构。

图9示出分类部分800的功能结构。

图10示出详细调度(scheduling)部分830的功能结构。

图11示出组成一轮的多个块的具体例子。

图12是用于将多个集群分配给多个块的处理的概念图。

图13是用于生成满足集群间的约束的详细进度表的处理的概念图。

图14示出局部(local)搜索部分840的功能结构。

图15示出通过将加工操作分类为集群来排列加工操作的处理的流程图。

图16示出步骤S1500中的处理的细节。

图17示出步骤S1530中的处理的细节。

图18示出步骤S1540中的处理的细节。

图19示出基于多个约束而确定的可插入的钢板的数量。

图20示出可插入的位置和可插入的钢板的数量之间的关系。

图21示出用作顺序确定系统140的信息处理装置20的硬件配置的例子。

图22示出用于提供使用顺序确定系统140的服务的提供方法的例子。

具体实施方式

下面将通过使用实施例来描述本发明，虽然被限制在权利要求的范围内的本发明不限于该实施例。此外，在实施例中所描述的所有组合不是用于解决本发明的手段所不可缺少的。

图1示出钢板加工装置10的整体结构。钢板加工装置10是通过响应于用户的指令而顺序地加工多个钢板来产生多个钢片的装置。钢板加工装置10包括工作滚轮110、选择设备130、顺序确定系统140、属性存储单元150和问题存储单元160。工作滚轮110通过以工作滚轮110轧压经过其的厚板100同时从上下节夹住该厚板的方式加工厚板100来产生薄板200。选择设备130根据顺序确定系统140所确定的顺序，来在多个厚板200中选择厚板100。然后如此选择的厚板100经过工作滚轮110的轧压加工。

轧压多个厚板200的多个加工操作的每个具有多个属性。这些属性的例子是已经经过轧压加工(下文中简称为“轧压后”)得到的钢片的厚度、宽度和表面质量。可以在例如附于厚板200上的属性标签210中写入每个属性的属性值。同时，在属性存储单元150中，与多个加工操作中的对应的一个关联地记录各个属性的属性值。此外，在每对不同的加工操作之间限定顺序约束，并且如此限定的顺序约束是基于每个相关的加工操作具有的属性的。问题存储单元160将顺序约束存储在其中。

此外，问题存储单元160存储用于计算指示钢板加工的效率的指数值的函数。该函数用作当确定加工操作的顺序时找出要被最大化的索引的目标函数(objective function)。顺序确定系统140按满足问题存储单元160中所存储的顺序约束并最大化目标函数的值的顺序来排列多个加工操作。顺序确定系统140将加工操作的顺序输出给选择设备130。

图2示出属性存储单元150的数据结构的例子。属性存储单元150担任根据本发明的候选存储单元，并存储用于轧压被预定为要被加工的候选的基本数量的钢板的每个的加工操作的各种属性。更具体地，属性存储单元150存储关于每个加工操作的识别信息(操作ID)和每个加工操作的每个属性的属性值，同时将工程ID和属性值与多个加工的对应的一个相关联。每个加工操作的属性包括加工后的钢片的属性。这种属性的例子是加工后的钢片的类型、宽度、厚度、长度和抗张强度(tensile strength)。钢片的厚度是本发明的第二属性的例子，并且由在每个相应加工操作中所轧压的钢片的加工后的厚度来指示其属性值。钢片的宽度是本发明的第三属性的例子，并且由在每个相应加工操作中所轧压的钢片的加工后的宽度来指示其属性值。

此外，钢片的类型指示加工后的钢片意图的最后用途。在图2所示的例子中，在通过轧压加工的轧压后，钢板1和2被用于汽车的组件。然后，钢板n被用于轮船的组件。其他最后用途在很大范围内变化，比如其它类型的运输装备和精密仪器。在某些情况下，对钢板所要求的质量取决于其用途而变化。例如，对于要形成汽车外型的钢板，需要很高的表面质量，这是因为钢板在汽车的设计上具有很强的影响。在这种情况下，希望在工作滚轮110的表面温度足够高和工作滚轮110的表面状况没有严重恶化的情况下轧压该钢板。管理属性存储单元150中的钢板类型允许适当地确定当按加工顺序排列钢板时要把每个钢板排列到哪个位置。

另外，加工操作的属性可以包括用于检查加工后的钢板、钢板的交付日期和加工操作必须达到的质量类别的检查代码。质量类别是第一属性的例子，并通过使用每个相应加工操作来指示质量类别作为属性值，该相应加工操作包括：困难的加工操作(D)、恢复加工操作(R)、较高质量加工操作(S)和任何其它类型的加工操作(O)。为了更精确，困难加工操作(D)削弱了工作滚轮110的耐用性。恢复加工操作(R)恢复工作滚轮110的耐用性。较高质量加工操作(S)必须产生质量高于预定标准质量的钢板。注意，不需要将质量类别本身存储在属性存储单元150中，以及可以根据诸如钢板的厚度、抗张强度和检查代码的其他属性来确定质量类别。

图3A和图3B示出问题存储单元160的数据结构的例子。问题存储单元160担任根据本发明的约束存储单元的角色，并存储顺序约束和位置约束。顺序约束每个都指示排列要在每个加工操作中加工钢板的加工操作的次序，并且位置约束每个都限定当按加工顺序排列钢板时每类钢板要被排列的范围。首先，通过参考图3A将说明顺序约束。顺序约束是指示在每对不同的加工操作之间所确定的、且基于每个属性的次序的约束。例如，问题存储单元160存储对宽度变化的约束，作为基于第三属性的第三顺序约束。对宽度变化的约束是这样的约束：在按顺序较后排列的加工操作中所轧压的钢板的宽度应该比在按顺序较前排列的加工操作中所轧压的钢板的宽度窄。用这样的约束，能够防止在工作滚轮110上所留下的凹槽在钢板的表面上留下瑕疵。

另外，问题存储单元160存储对厚度变化的约束，作为基于第二属性的第二顺序约束。对厚度变化的这种约束是这样的约束：在两个连续的加工操作中所轧压的两个钢板之间的厚度差的值应该在预定的范围内。用这样的约束，能够降低厚度调整所需的时间，从而允许快速进行多个连续的加工操作。此外，问题存储单元160存储不同的制造厚板之间的约束、对恢复厚板的约束和对较高质量厚板的约束。不同的制造厚板之间的约束是阻止连续进行大于或等于预定数量的困难的加工操作的约束。另外，对恢复厚板的约束是这样的约束：必须在两个困难的加工操作之间进行恢复加工操作。对较高质量厚板的约束是这样的约束：应该在预定的块上进行对于较高质量钢板的加工操作。对于该块，将稍后通过参考图4给出描述。

注意，虽然出于说明方便，图3示出了指示每个约束的名字，但实际上问题存储单元160可以存储用于判断加工操作的顺序是否满足每个约束的函数等。此外，问题存储单元160存储当新钢板被插入到从已经排列的钢板加工顺序中随机选择的位置中时该新钢板满足这些顺序约束的满足概率p。该概率p可以是由用户输入的概率，或者可以是通过使用在过去实际排列的钢板的顺序而计算出的概率。但是，当被插入到从已经排列的钢板加工顺序中随机选择的位置中时新钢板满足这些顺序约束的概率p通常采用非常小的值，比如1％或更小，因为必须如上所述地满足各种约束。

其次，将参考图3B描述位置约束。问题存储单元160存储范围，其中当按加工顺序排列一类钢板时这类钢板要被排列到这些范围中的每个，同时问题存储单元160将该范围与钢板的类型相关联。例如，问题存储单元160可以存储对上限值和下限值的两个约束，或者对这些值的任意一个的约束。关于对上限值的约束是位置约束的例子，并且指示将要排列每类钢板的位置的上限值。具体地，根据图3B所示的位置约束，在高达工作滚轮110开始轧压之后的第60个钢板的范围内的位置中轧压用于汽车的钢板，并且不为该钢板提供下限值。另一方面，具体地，在工作滚轮110开始轧压之后的第60个和以后的钢板的范围内的位置中轧压用于轮船的钢板，并且不为该钢板提供上限值。此外，在工作滚轮110开始轧压之后的第30到第60个钢板的范围内的位置中轧压用于精密仪器的钢板。通过以这种方式提供位置信息，对每类最后用途可以适当地控制轧压后钢板的表面质量。

图4示出加工操作的顺序的例子。图4中所示的每个矩形区域示意性地表示轧压后钢板。图4中每个矩形区域在上下方向上的长度表示每个轧压后钢板的宽度。图4中的左右方向表示时间的流逝。例如，在就在工作滚轮更换后的时间段(称为热身主体(warm-up body))期间，按以便逐渐增加各个轧压后钢板的宽度的顺序来轧压多个钢板。因此，能够逐渐增加工作滚轮的温度，并能够使工作滚轮为了得到更高质量钢板而轧压钢板做准备。此外，在更换工作滚轮后完成某数量的轧压加工操作之后的时期(称作下降期(come-down period))时间段，按以便逐渐降低各个轧压后钢板的宽度的顺序轧压多个钢板。以这种方式，能够避免在稍后轧压的钢板的表面上留下瑕疵。

当在从开始用工作滚轮轧压的时刻到更换新的工作滚轮的时刻的之间的中如上所述轧压一系列钢板时，考虑棺材形状(coffin shape)作为由以加工顺序排列的钢板的变化的宽度形成的期望的形状。本发明的顺序确定系统140意图最大化钢板加工的效率，同时满足包括如图4所示的钢板宽度的变化在内的各种约束。此外，如果即使当确定达到某种程度的加工效率的加工顺序时、要被加工的候选钢板仍然存在，则要求顺序确定系统140进一步将另一新钢板插入指示加工顺序的钢板队列中。在此，优选的是，根据在将钢板插入该位置后整个轧压加工的效率是否增加来确定新钢板要插入的位置。由前述的位置约束将新钢板的这类可插入位置限制到某一范围。在下文中，通过参考图5到图7描述位置约束的限制。

图5A和5B是每个都示出位置约束的例子的概念图。图5A示出对上限值的约束。在此，钢板500表示当按加工顺序排列钢板时在某种钢板之中的最后位置上排列的钢板。这个钢板类型具有对上限值的约束，并且钢板500满足该位置约束。因此，在该钢板类型的上限值之前排列钢板500。在此，m表示上限值和钢板500排列的位置之间的差值。当在钢板500前插入另一钢板时，该差值是(m-1)。因此，m是在满足对上限值的约束的同时可以插入到钢板500前的位置的钢板的最大数量。

图5B示出了对下限值的约束。钢板510表示当以加工顺序排列钢板时排列在某种钢板中的第一位置上的钢板。该钢板类型具有对下限值的约束，并且钢板510满足该位置约束。因此，在该钢板类型的下限值之前排列钢板510。假定在确定加工顺序的同时，钢板510在某一时间点处不必满足对下限值的约束，存在一种情况：在该钢板类型的下限值之前排列钢板510。在此，k表示下限值和在上述情况中钢板510排列的位置之间的差值。当在钢板510前插入另一钢板时，差值是(k-1)。因此，必须将k个钢板插入钢板510前的位置，以便满足对下限值的约束。

在此，考虑这样的情况：首先暂时地(tentatively)确定加工顺序，并且然后将大量钢板进一步插入到暂时的加工顺序。在这种情况下，暂时的加工顺序在暂时确定的时刻不必满足对下限值的约束。此外，如果在暂时确定的时刻必须满足对下限值的约束，将比必要的约束更有限制性的约束强加到顺序确定上，并且这导致降低了加工在这种约束下生成的钢板队列的效率。由于这个原因，顺序确定系统140在临时放松对下限值的约束时，暂时确定加工顺序。其后，顺序确定系统140通过插入钢板使得加工顺序满足对下限值的约束。在此过程后将提供该实施例的描述。

图6示出在不受位置约束限制的钢板被插入到加工顺序中后可插入到该加工顺序中的钢板的数量的变化。在此，钢板600表示当以加工顺序排列钢板时在某种钢板中的最后位置中排列的钢板。另外，m表示排列钢板600的位置与该钢板类型的上限值之间的差。在这种情况下，如果在钢板600前插入不受该上限值限制的不同类型的钢板，则钢板600与上限值之间的差减小到m-1。另一方面，如果在钢板600后插入钢板610，则钢板600和上限值之间的差仍然是m。换句话说，在钢板600被排列在某种钢板的最后位置上时将不同类型的钢板610插入加工顺序中的情况下，当在钢板600前插入钢板610时比当在钢板600后插入钢板610时可以进一步插入其他钢板的位置的数量更大。

图7示出在受位置约束限制的钢板被插入到加工顺序后可插入到该加工顺序中的钢板的数量的变化。在此，钢板700表示当以加工顺序排列钢板时在某种钢板的最后位置中排列的钢板。另外，m表示排列钢板700的位置与该钢板类型的上限值之间的差。在这种情况下，如果在钢板700前插入与钢板700相同类型的钢板710，则钢板700与上限值之间的差减小到m-1。另一方面，如果在钢板700后插入钢板710，则最后的这类钢板从钢板700变为钢板710。此外，可插入钢板710之前的位置的钢板数量受钢板710与上限值之间的差值所限制。例如，如果被插入的钢板710的位置与上限值相同，则此后不能再将钢板插入到钢板710之前的任何位置。

如图6和图7所示，在将新钢板插入到已经按加工顺序排列的钢板队列中的情况下，在该插入后可插入的钢板的数量依据所插入的钢板的位置和类型有很大不同。由于这个原因，如果仅依据插入时的加工效率多高来做出确定，则有时会做出对钢板要插入的位置的不充分的确定。更精确地，即使当钢板的插入引起插入时的高加工效率时，该插入也可能导致此后可插入的钢板数量非常小，并且所得到的加工顺序可能仅仅具有不足的加工效率。与此有关，在通过依次插入钢板来改进加工效率的处理中，根据本实施例的顺序确定系统140不仅基于插入时的加工效率、还基于插入后可另外插入的钢板数量做出关于插入位置的确定。通过将稍后描述的局部搜索部分840的操作来做出该确定。以这种方式，可以进一步提高加工效率。下面将提供其详细描述。

图8示出顺序确定系统140的功能结构。顺序确定系统140包括分类部分800、粗略调度部分810、判断部分820、详细调度部分830、局部搜索部分840和输出部分850。分类部分800、粗略调度部分810、判断部分820和详细调度部分830彼此合作确定如图4所示的暂时加工顺序。然后，局部搜索部分840在试图将其他钢板插入到表示如此确定的加工顺序的钢板队列中的同时进一步改善加工效率。

首先，为了将多个加工操作分类为多个集群(cluster)，分类部分800依次选择至少一个加工操作作为一个集群。此时，根据第一属性的属性值将加工操作分类为集群。例如，在每个集群中的所有加工操作具有第一属性的相同的属性值。此外，按满足第二顺序约束和第三顺序约束的顺序排列每个集群中的加工操作。例如，每个集群中的加工操作的所有质量类别都是相同的，并且按满足对宽度变化的约束和对厚度变化的约束的顺序排列集群中的加工操作。

粗略调度部分810将第一顺序约束和第三顺序约束的每个看作多个集群之间的约束，并按最大化钢板加工效率的顺序排列多个加工操作。可以通过求解整数计划问题(integer programming problem)来实行加工操作的排序。例如，当从工作滚轮110开始轧压钢板时到连续轧压多个钢板后用新工作滚轮更换该工作滚轮110时的时间段被划分成多个块时，确定要在多个块的每个中进行加工操作的哪个集群的问题可以被用作整数计划问题。在这种情况下，粗略调度部分810可以求解该整数计划问题。当求解了该整数计划问题时，在考虑此后局部搜索部分840插入钢板时，如下设置位置约束。具体地，将对上限值的约束设置为稍微更有限制性的约束，同时将对下限值的位置约束设置为稍微更少限制性的约束。更精确地，当被存储在问题存储单元160中的位置约束具有下限值30和上限值60时，在对通过从下限值中减去某值而获得的较少限制性的下限值(例如，20)的位置约束和对通过从上限值中减去某值而获得的更有限制性的上限值的位置约束之下，计算整数计划问题的解。此外，从工作滚轮110开始轧压钢板时到连续轧压多个钢板后用新工作滚轮更换该工作滚轮110时的时间段被称为一轮(round)。另外，图11示出了通过划分一轮而得到的多个块的例子。

图11示出了组成一轮的多个块的具体例子。将该轮的下降期划分成每个被表示为图11中的矩形的多个块。与标识符关联地表示每个块。例如，多个块包括块SQ、块D1、块R1、块D2、块R2、块D3、块R3和块D4。在块SQ中，工作滚轮110的表面状况是足够好以用于轧压经过其的高质量钢片的。当在D1、D2、D3和D4的块中进行困难加工操作时，不可避免地在R1、R2和R3的块中进行恢复加工操作。

此外，图12是用于将多个集群分配给多个块的处理的概念图。图12的左边示出由分类部分800分类的多个集群。粗略调度部分810在所有集群中选择能够最大化加工效率的一些集群，并确定要通过使用多组工作滚轮中的哪组工作滚轮在哪个块中进行加工操作的哪个集群。不必将所有已分类的集群的每个都分配给任意一个块。可以在下一次机会中与将在下一次机会中由分类部分800分类的其他集群一起分配这些还没有分配的集群。如刚刚所述，不必分配所有集群，这使得能够增加顺序确定中的自由度。此外，要被分配集群的一轮不是固定的一轮，而是多轮中所选的一轮。这使得能够改善自由度，并增加加工效率。

在此，描述回到图8。判断部分820判断在第一集群的队列中的最后加工操作和第一集群之后排列的第二集群的队列中的第一加工操作之间是否满足第二顺序约束。在不满足第二顺序约束的情况下，详细调度部分830搜索与第一集群的队列中的最后加工操作和第二集群的队列中的第一加工操作之间满足第二顺序约束的另一加工操作。然后，详细调度部分830在第一集群之后并在第二集群之前排列搜索出的加工操作(必要时称为“第一搜索出的加工操作)。

在满足第二顺序约束的情况下，局部搜索部分840试图修改加工操作的顺序，以便进一步改善加工效率。例如，对于已经在属性存储单元150中存储其属性值并且还没有确定其在加工顺序中的位置的每个钢板，局部搜索部分840通过将该钢板插入由粗略调度部分810和详细调度部分830排列的钢板队列中来判断目标函数的值的变化。例如，局部搜索部分840判断该钢板的插入是否允许加工顺序满足顺序约束和允许目标函数的值增加。当满足顺序约束且当目标函数值增加时，局部搜索部分840插入该钢板。局部搜索部分840对每个钢板重复执行这个处理。

输出部分850输出在每个集群中所排列的多个加工操作和由详细调度部分830排列的加工操作的队列顺序。该顺序取决于由粗略调度部分810排列的集群的顺序、由详细调度部分830排列的加工操作的顺序、和由局部搜索部分840修改的顺序。

图9示出分类部分800的功能结构。分类部分800包括组生成部分900和集群生成部分910。组生成部分900从属性存储单元150依次读取第一属性的属性值，并且将具有第一属性的相同属性值的多个加工操作分类成组。换句话说，仅困难加工操作被分类为某个组，而不同类型的加工操作不被分类成组。同时，多个困难加工操作可以被分类成多个组。

集群生成部分910从属性存储单元150读取被分类成某个组的多个加工操作的每个的第二和第三属性的属性值。然后，集群生成部分910按满足第二顺序约束和第三顺序约束的顺序来重新排列这多个加工操作。具体地，集群生成部分910按钢片轧压后的宽度递减的顺序来重新排列多个钢板，并判断多个重新排列的加工操作的每个是否满足第三顺序约束。在不满足第三顺序约束的情况下，例如，在存在对于具有明显不同的厚度的钢板的加工操作的情况下，可以从重新排列的顺序排除该加工操作。然后，集群生成部分910选择多个重新排列的加工操作的每个部分作为一个集群。由于不满足第三顺序约束而被排除的加工操作可以本身形成一个集群，或与对于具有相似厚度的钢板的另一加工操作一起形成一个集群。

图10示出详细调度部分830的功能结构。详细调度部分830包括初始搜索部分1000、满足判断部分1010和递归搜索部分1020。初始搜索部分1000搜索与第一集群的队列中的最后加工操作和在第一集群之后排列的第二集群的队列中的第一加工操作中的任意一个之间满足第二顺序约束的另一加工操作(称为“第一匹配加工操作”)。例如，为了找到这种加工操作，初始搜索部分1000可以在由用户指定用于加工多个厚板200的多个加工操作中搜索被包括在不是由粗略调度部分830排列的集群中的加工操作。另外，希望要被搜索的加工操作使第一匹配加工操作满足所有其他约束。

图13是用于生成满足集群间约束的详细进度表的处理的概念图。存在被排列在两个块的边界(图13中的阴影区)上的两个加工操作不满足第二顺序约束的情况。在这种情况下，初始搜索部分1000扫描块之间的每个边界，并且如果需要，依次搜索出要被插入边界中的加工操作，以便被排列在每个边界处的第一集群和第二集群可以满足第二顺序约束。对于每个边界，满足判断部分1010和递归搜索部分1020执行以下处理。

描述回到图10。满足判断部分1010判断在第一搜索出的加工操作和第一集群中的最后加工操作的另一个(称为“第二匹配加工操作”)与第二集群中的第一加工操作之间是否满足第二顺序约束。在不满足第二顺序约束的情况下，递归搜索部分1020进一步搜索出与第一搜索出的加工操作之间满足第二顺序约束的另一加工操作(称作“第二搜索出的加工操作”)，并将该第二搜索出的加工操作发给满足判断部分1010。当接收到该第二搜索出的加工操作时，满足判断部分1010判断在第二搜索出的加工操作和第二匹配加工操作之间是否满足第二顺序约束。在不满足第二顺序约束的情况下，递归搜索部分1020进一步搜索出与第二搜索出的加工操作之间满足第二顺序约束的加工操作。

一旦满足判断部分1010判断满足第二顺序约束，详细调度部分830在第一集群之后并在第二集群之前排列由初始搜索部分1000和递归搜索部分1020依次搜索出的加工操作的至少一个。

图14示出局部搜索部分840的功能结构。局部搜索部分840包括选择单元1400和插入单元1450。选择单元1400从详细调度部分830接收关于按钢板的加工顺序排列的钢板队列的信息。按已经由粗略调度部分810、判断部分820和详细调度部分830确定的加工顺序来排列该队列中的钢板。换句话说，该钢板队列满足所有的顺序约束和对上限值的位置约束，但不总是满足对下限值的约束。

选择单元1400优选地选择在满足位置约束的同时最大化在将新钢板插入钢板队列后可以被进一步插入该钢板队列中的钢板数量的期望值的位置，作为新钢板将被插入该钢板队列中的位置。然后，插入单元1450将新钢板插入所选位置中，并输出表示插入后的钢板队列的数据。当属性存储单元150仍然存储着没有确定其在加工顺序中的位置且还没有试图其插入的钢板时，插入单元1450可以将表示插入后的钢板队列的数据输出到选择单元1400，从而可以使得在该钢板队列中插入另一个新钢板。优选地，对于还没有确定其在加工顺序中的位置的基本数量的钢板中的所有钢板，选择单元1400重复执行选择用于插入还没有确定其在加工顺序中的位置的钢板的位置的处理。

选择单元1400包括生成部分1405、第一计算部分1410、第二计算部分1420、第三计算部分1430和选择处理部分1440，作为具体结构。生成部分1405从问题存储单元160读取对与将被插入已经按加工顺序排列的钢板队列中的新钢板的类型对应的上限值的约束。之后，通过在钢板队列中上限值之前的多个位置的每个中插入新钢板，生成部分1405生成代表用于插入后的钢板队列的候选的多个钢板队列。然后，生成部分1405将代表这些钢板队列的数据输出到第一计算部分1410。

第一计算部分1410对所生成的钢板队列的每个执行以下处理。首先，第一计算部分1410选择在每类钢板的最后位置中排列的钢板，并从问题存储单元160读取对每个所选类型的钢板的上限值的约束。然后，第一计算部分1410计算可插入由所选钢板分隔的每个区段(segment)中的钢板的数量的期望值。这种期望值的计算是基于每个所选钢板的位置与所选钢板类型的上限值之间的差值的。该差值等于例如图4中的钢板的数量m给出的数值。数值m越大，在插入后可插入的钢板数量的期望值越大。

接下来，选择处理部分1440选择使新钢板被插入以便生成具有对相应的区段所计算的每个期望值的更大总和的钢板队列的位置，作为新钢板要被插入的位置。然后，选择处理部分1440通知插入单元1450所选择的位置。顺便提及，希望可插入位置的选择是基于除上述可插入钢板的数量的期望值以外的对下限值的约束和插入后的加工效率的。第二计算部分1420判断是否满足对下限值的约束，并且第三计算部分1430估计加工效率多高。其后，将描述这些部分的操作。

第二计算部分1420对由生成部分1405生成的每个钢板队列执行以下处理。首先，第二计算部分1420选择在每类钢板的第一位置处排列的第一钢板，并读取对所选钢板类型的下限值的约束。之后，第二计算单元1420计算每个所选钢板的位置与所选钢板类型的下限值之间的差值。然后，通过使用所计算的差值，第二计算部分1420计算指示钢板队列违反对下限值的位置约束的程度有多大的指数值(index value)。例如，随着所计算的差值增加，队列违反对下限值的约束达到更大的程度。相反，既不具有已确定的加工顺序中的位置也不试图被插入的钢板的数量越大，队列违反对下限值的约束越少。这是因为当可以插入更多钢板时，满足对下限值的位置约束变得很容易。

选择处理部分1440优选地选择使新钢板被插入以便生成具有更小指数值的钢板队列的位置，作为新钢板要被插入的位置。为了实现该选择，能够引入这样的估计函数(evaluation function)：该估计函数根据较小的指数值取较小的值，并根据由第一计算部分1410计算的较大期望值取较大的值。在这样的情况下，选择处理部分1440只需要选择最大化估计函数的值的位置。

第三计算部分1430计算指示用于由生成部分1405生成的每个钢板队列的加工钢板的效率的第一估计值。从插入新钢板时的加工效率的观点出发，最大化第一估计值的钢板队列是最期望的钢板队列。但是，当考虑重复进行插入操作时，最大化第一估计值的钢板队列并不总是最期望的钢板队列。由于此原因，选择处理部分1440根据通过组合第一估计值与由第一计算部分1410计算的期望值而获得的第二估计值来选择用于插入钢板的位置。例如，第二估计值是在第一估计值较大时取较大值并在由第一计算部分1410计算的期望值较大时取较大值的估计函数的值。

注意，第一估计值可以是通过使用例如整数计划问题的目标函数而计算的值。换句话说，可以通过估计将由一组工作滚轮110轧压的钢板的较长的总长度来确定第一估计值，作为较高的加工效率。替换地，可以通过估计将由一组工作滚轮110进行的较大数量的困难加工操作来确定第一估计值，作为较高的加工效率。相反，可以通过估计将由一组工作滚轮110进行的较大数量的困难加工操作来确定第一估计值，作为较高加工效率。另外，可以通过估计将由一组工作滚轮110进行的较小数量的恢复加工操作来确定第一估计值，作为较高的加工效率。替换地，可以通过估计较低频率来确定第一估计值作为较高的加工效率，其中以该较低频率，钢板的传送实际上将从每个被确定用于相应的钢板的传送期限延迟。

图15示出了用于通过将加工操作分类成集群来排列加工操作的处理的流程图。分类部分800将多个加工操作分类成多个集群(S1500)。在某个集群中的所有的多个加工操作具有第一属性的相同的属性值。在此假定：C表示分类的集群的集合；C^D表示包括困难加工操作在内的集群集合；C^R表示包括恢复加工操作在内的集群集合；C^SQ表示包括较高质量加工操作在内的集群集合；并且C^O表示在集合C中不同于三个集合C^D、C^R和C^SQ的集群集合。

粗略调度部分810将第一顺序约束和第三顺序约束看作多个集群之间的约束，并通过求解整数计划问题按最大化钢板加工的效率的顺序来排列多个加工操作(S1510)。该整数计划问题是用于找出将要将多个集群的每个分配给哪一轮中的哪个块的问题。在此，假定R表示集群要被分配到的轮的集合，并且S表示块的集合。

该整数计划问题的变量对每个块并对每个集群保存指示是否在块中进行被包括在集群中的加工操作的状态值。在此，x_i，j，k表示该变量。在将集群k∈C分配给一轮i∈R中的块j∈S的情况下，该变量取1，并且否则，该变量取零。

该整数计划问题包括被当作集群间的约束的第一顺序约束。例如，将第一顺序约束表达为用于第一属性的每个的线性不等式。这些线性不等式采用包括了包括具有相同第一属性值的加工操作、并且被分配给每个块的集群的数量的范围，作为变量。公式1示出不同制造厚板之间的约束，该约束是第一顺序约束中的一个。该约束指示给困难制造块(manufacturing block)(D1到D3)的每个分配将由困难加工操作组成的集群还是与其被分配的集群不同的集群。

[公式1]

$\underset{k\∈C^D\∪C^O}{\mathrm{\Σ}}{x}_{i,D1,k}=\underset{k\∈C^D\∪C^O}{\mathrm{\Σ}}{x}_{i,D2,k}=\underset{k\∈C^D\∪C^O}{\mathrm{\Σ}}{x}_{i,D3,k}=\underset{k\∈C^D\∪C^O}{\mathrm{\Σ}}{x}_{i,D4,k}=1$ 对每个i∈R

$\underset{k\∈C/(C^D\∪C^O)}{\mathrm{\Σ}}{x}_{i,D1,k}=\underset{k\∈C/(C^D\∪C^O)}{\mathrm{\Σ}}{x}_{i,D2,k}=\underset{k\∈C/(C^D\∪C^O)}{\mathrm{\Σ}}{x}_{i,D3,k}=\underset{k\∈C/(C^D\∪C^O)}{\mathrm{\Σ}}{x}_{i,D4,k}=0$ 对每个i∈R  ...公式1

另外，还可以将困难制造厚板之间的约束表达为公式2所示的不等式。该约束禁止将由第一组的困难加工操作(Gx)组成的集群分配给在由第二组的困难加工操作(Gy)组成的集群被分配给的块之前的块。加工操作的某些特性允许这种约束的添加。

[公式2]

$\underset{k\∈G_x}{\mathrm{\Σ}}{x}_{i,D1,k}+\underset{k\∈G_y}{\mathrm{\Σ}}{x}_{i,D2,k}\≤1$ 对每个i∈R

$\underset{k\∈G_x}{\mathrm{\Σ}}{x}_{i,D2,k}+\underset{k\∈G_y}{\mathrm{\Σ}}{x}_{i,D3,k}\≤1$ 对每个i∈R  ...公式2

$\underset{k\∈G_x}{\mathrm{\Σ}}{x}_{i,D3,k}+\underset{k\∈G_y}{\mathrm{\Σ}}{x}_{i,D4,k}\≤1$ 对每个i∈R

此外，可以将困难制造厚板之间的约束表达为公式3所示的不等式。该约束禁止将由第一组的困难加工操作(Gx)组成的集群分配给由第二组的困难加工操作(Gy)组成的集群的相同轮。加工操作的某些特性也允许这种约束的添加。

[公式3]

$\underset{j\∈S,k\∈G_x}{\mathrm{\Σ}}{x}_{i,j,k}\≤L\·z_1$

$\underset{j\∈S,k\∈G_y}{\mathrm{\Σ}}{x}_{i,j,k}\≤L\·z_2$ ...公式3

z₁+z₂≤1  对每个i∈R

注意，在公式3，L是足够大的正常数，z1和z2每个是取值0或1的二值变量(two-valued variable)。

此外，公式4示出对较高质量厚板的约束，该约束是第一顺序约束中的一个。该约束指示应该在块SQ中进行需要具有比预定标准质量较高的质量的钢片的较高质量加工操作。

[公式4]

$\underset{k\∈C^{\mathrm{SQ}}\∪C^O}{\mathrm{\Σ}}{x}_{i,\mathrm{SQ},k}=1$ 对每个i∈R

$\underset{k\∈C/(C^{\mathrm{SQ}}\∪C^O)}{\mathrm{\Σ}}{x}_{i,\mathrm{SQ},k}=0$ 对每个i∈R    ...公式4

此外，公式5和公式6示出对恢复厚板的约束，该约束是第一顺序约束中的一个。该约束指示必须在每个由困难加工操作组成的两个集群之间进行恢复加工操作。

[公式5]

$\underset{k\∈C^R\∪C^O}{\mathrm{\Σ}}{x}_{i,R1,k}=\underset{k\∈C^R\∪C^O}{\mathrm{\Σ}}{x}_{i,R2,k}=\underset{k\∈C^R\∪C^O}{\mathrm{\Σ}}{x}_{i,R3,k}=1$ 对每个i∈R

$\underset{k\∈C/(C^R\∪C^O)}{\mathrm{\Σ}}{x}_{i,R1,k}=\underset{k\∈C/(C^R\∪C^O)}{\mathrm{\Σ}}{x}_{i,R2,k}=\underset{k\∈C/(C^R\∪C^O)}{\mathrm{\Σ}}{x}_{i,R3,k}=0$ 对每个i∈R  ...公式5

[公式6]

$\underset{k\∈G_X}{\mathrm{\Σ}}{x}_{i,D1,k}+\underset{k\∈G_y}{\mathrm{\Σ}}{x}_{i,D2,k}\≤\underset{k\∈C^R}{\mathrm{\Σ}}{x}_{i,R1,k}+1$ 对每个i∈R

$\underset{k\∈G_X}{\mathrm{\Σ}}{x}_{i,D2,k}+\underset{k\∈G_y}{\mathrm{\Σ}}{x}_{i,D3,k}\≤\underset{k\∈C^R}{\mathrm{\Σ}}{x}_{i,R2,k}+1$ 对每个i∈R  ...公式6

$\underset{k\∈G_X}{\mathrm{\Σ}}{x}_{i,D3,k}+\underset{k\∈G_y}{\mathrm{\Σ}}{x}_{i,D4,k}\≤\underset{k\∈C^R}{\mathrm{\Σ}}{x}_{i,R3,k}+1$ 对每个i∈R

另外，该整数计划问题具有指示给每个块分配不多于一个的集群的约束。该约束可以表达为例如公式7。

[公式7]

$\underset{i\∈R_i,i\∈S}{\mathrm{\Σ}}{x}_{i,j,k}\≤1$ 对每个k∈C  ...公式7

该整数计划问题还包括被看作集群间的约束的第三顺序约束。例如，粗略调度部分810将该第三顺序约束看作这样的约束：该约束指示来自在较早排列的集群中的最后加工操作的轧压后钢片比来自在较后排列的集群中的第一加工操作的轧压后钢片宽。遵循该约束，粗略调度部分810排列多个集群。将被看作集群间的约束的第三顺序约束表达为以下所示的公式8。

[公式8]

$\underset{k\∈C}{\mathrm{\Σ}}\mathrm{WidthL}\left(k\right)\·x_{i,D1,k}-\underset{k\∈C}{\mathrm{\Σ}}\mathrm{WidthF}\left(k\right)\·x_{i,R1,k}\≥0$ 对每个i∈R...公式8

注意，WidthF(k)表示在被排列在集群k中的第一加工操作中所轧压的轧压后钢片的宽度，并且WidthL(k)表示在集群k中的最后加工操作中所轧压的轧压后钢片的宽度。

通过求解上述整数计划问题来排列多个集群。其后，判断部分820判断第一集群中的最后加工操作与第一集群之后排列的第二集群中的第一加工操作之间是否满足第二顺序约束(S1520)。在不满足第二顺序约束的情况下(S1520：否)，详细调度部分830搜索出每个与第一集群中的最后加工操作和第二集群中的第一加工操作之间满足第二顺序约束的其他加工操作的至少一个(S1530)。然后，详细调度部分830在第一集群之后并在第二集群之前排列所搜索出的加工操作。此外，详细调度部分830可以搜索没有由粗略调度部分810排列的集群，以便找出要排列在热身主体中的加工操作和图13所示的尾部部分。

在粗略调度部分810和/或详细调度部分830满足第二顺序约束的情况下，局部搜索部分840试图修改加工操作的顺序，以便进一步改进加工效率(S1540)。例如，关于具有在属性存储单元150中存储的属性并且不具有在加工顺序中已确定的位置的每个钢板，局部搜索部分840通过将该钢板插入由粗略调度部分810和详细调度部分830所排列的钢板队列中来判断目标函数的值的变化。例如，局部搜索部分840判断钢板的插入是否使得满足顺序约束，以及是否使得目标函数的值增加。在满足顺序约束并且目标函数的值增加的情况下，局部搜索部分840插入该钢板。

图16示出步骤S1500中的处理的细节。组生成部分900从属性存储单元150中依次读取第一属性的属性值，并将具有第一属性的相同的属性值的多个加工操作分类成一个组(S1600)。换句话说，例如仅将困难加工操作分类成某一组，并且不将其它类型的加工操作分类到该组。同时，可以将多个困难加工操作分类成多个组。

随后，集群生成部分910将每个组中所包括的加工操作分类成多个集群(S1610)。在每个集群中，加工顺序满足第二顺序约束和第三顺序约束。为了更精确，集群生成部分910首先从属性存储单元150读取被分类成某一组的多个加工操作的每个的各个第二和第三属性的属性值。然后，集群生成部分910按满足第二顺序约束和第三顺序约束的顺序来重新排列多个加工操作。换句话说，例如，集群生成部分910按轧压后钢片的宽度降低的顺序来重新排列多个钢板，并判断如此排列的多个加工操作的每个是否满足第三顺序约束。在不满足第三顺序约束的情况下，例如，在存在用于具有明显不同的厚度的钢板的加工操作的情况下，可以从重新排列的顺序中排除该加工操作。然后，集群生成部分910选择多个如此排列的加工操作的每个部分作为一个集群。不满足第三顺序约束并从而被排除的加工操作可以由其本身或与要产生具有类似厚度的钢片的另一加工操作一起形成另一集群。

图17示出步骤S1530中的处理的细节。初始搜索部分1000搜索出与第一集群中的最后加工操作和第一集群之后排列的第二集群中的第一加工操作中的任意一个(第一匹配加工操作)之间满足第二顺序约束的另一加工操作(S1700)。为了找出这种加工操作，例如，初始搜索部分1000可以在由用户指定的用于处理多个厚板200的多个加工操作中搜索被包括在不是由粗略调度部分830排列的集群中的加工操作。

满足判断部分1010判断如此搜索出的加工操作是否与第一集群中的最后加工操作和第二集群中的第一加工操作的另一个(第二匹配加工操作)之间满足第二顺序约束(S1710)。在不满足第二顺序约束的情况下(S1710：否)，递归搜索部分1020进一步搜索出与该搜索出的加工操作之间满足第二顺序约束的另一加工操作(S1720)，并使得处理回到步骤S1710。

一旦满足判断部分1010判断满足第二顺序约束，则详细调度部分830终止图17所示的处理。然后，详细调度部分830在第一集群之后并在第二集群之前排列由初始搜索部分1000和递归搜索部分1020依次搜索出的加工操作的至少一个。

图18示出步骤S1540中的处理的细节。局部搜索部分840对其属性被存储在属性存储单元150中的除了具有在加工顺序中的确定位置而被选择的钢板以外的剩余钢板的每个重复执行以下处理(S1800)。首先，生成部分1405通过在剩余钢板类型的上限值之前将剩余钢板的每个插入已经被确定作为加工顺序的每个钢板队列中的每个可插入的位置而生成多个钢板队列(S1810)。但是，队列是在即使当剩余钢板被插入其中时这些队列也满足其他顺序约束的情况下生成的。

生成部分1405判断钢板的至少一个队列是否是通过插入剩余钢板的至少一个而生成的(S1820)。换句话说，生成部分1405判断是否存在在满足顺序约束的同时可以将剩余钢板的一个插入到的至少一个位置。当队列生成失败时(S1820：否)，局部搜索部分840将处理移至步骤S1890，并对剩余钢板的下一个重复该处理。另一方面，当队列生成成功时(S1820：是)，第一计算部分1410对每个所生成的钢板队列计算期望值，并且该期望值用于在满足对上限值的位置约束的同时可以进一步插入其中的钢板的数量(S1830)。下文中，将通过参考图19和20详细描述计算处理。

图19示出基于多个约束确定的可插入的钢板的数量。各类钢板混合地存在于按已经确定的加工顺序排列的钢板队列中。例如，假定第一类和第二类钢板混合地存在，并被排列在第一类和第二类钢板的最后位置中的钢板被分别称为钢板1900和钢板1910。另外，将这些类型的钢板限制在由不同的位置约束限制的位置上。例如，在钢板1900前可插入的钢板的数量是钢板1900的位置与位置约束1的属性值1之间的差值m₁。另一方面，在钢板1910前可插入的钢板的数量是钢板1910的位置与位置约束2的属性值2之间的差值m₂。

由在钢板1900和钢板1910两者之前的区段中的两个约束来限制两类钢板。换句话说，在该区段中，由于两个约束的限制，仅较小数量的钢板m₁和m₂可以被新插入到队列中。以这种方式，在每个区段中确定可插入的钢板的数量，并且可以将在可插入的钢板的数量和区段之间的该关系表达为具有水平轴上的可插入的位置和垂直轴上的可插入的钢板的数量的图。在此由于钢板1900被排列在钢板1910之前，因此钢板1900之前的区段受两个约束限制，并且因此可插入的钢板的数量是m₁。相反，由于在钢板1900和1910之间的区段仅受对上限值2的约束2限制，因此可插入的钢板的数量是m₂。图20示出了指示在约束的数量增加到3个或更多的情况下可插入的钢板的数量的图。

图20示出了可插入的位置与可插入的钢板的数量之间的关系。在此，首先从已经按加工顺序排列的钢板队列中选择每类的最后钢板，并假定从最前侧开始由所选钢板分隔的区段是1到n。此外，假定l₁到l_n分别表示区段1到n中所包括的钢板的数量，并假定m₁到m_n分别表示可插入到区段1到n的钢板的数量。当在这些假设之下建立具有水平轴上的可插入的位置和垂直轴上的可插入的钢板的数量的图时，获得的是，随着可插入的钢板的数量逐渐增加，阶梯图形向右逐渐增加。这是因为当可插入的位置变得更接近于队列的末端时，有影响力的位置约束的类型变得更少。

参考该图，将提供对于如下方法的详细描述，第一计算部分1410使用该方法计算可插入的钢板的数量的期望值。首先，第一计算部分1410计算图中所指示的各类信息，以便计算期望值。更具体地，第一计算部分1410在每个区段中用作末尾侧的边界的最后钢板的位置与该最后的钢板的类型的上限值之间的每个差值，作为m₁到m_n。另外，第一计算部分1410计算已经被排列在各个区段中的钢板的数量l₁到l_n。然后，第一计算部分1410通过使用这些类型的信息来计算期望值。

在此，说明作为在不严格的约束下的期望值的宽松期望值的计算。下面的公式9的左侧示出了当将随机选择的钢板插入在某一区段k中随机选择的位置中时该随机选择的钢板不违反顺序约束的概率。

[公式9]

$(1-{(1-p)}^l)\frac{l_k}{l}\≈{\mathrm{pl}}_k$ ...公式9

在此，l表示按已经确定的加工顺序排列的钢板队列中所包括的钢板的数量。由于p是可以将随机选择的钢板插入随机选择的位置而不违反顺序约束的概率，因而可以将钢板插入至少一个位置而不违反顺序约束的概率是(l-(l-p)^l)。然后通过将该概率乘以l_k/l得到区段k包括可插入而不违反约束的位置的概率。

另外，当概率p比1小得多时，(l-p)^l可以近似为1-pl。结果，公式9的左侧被变换成其右侧。

在此，假定上限值的位置约束对于其后要插入的钢板是不严格的，并且l_k ⁿ表示第n个钢板要插入到的区段k的长度。然后，建立以下递推公式10.

[公式10]

$l_k^{n+1}=l_k^n+{\mathrm{pl}}_k^n=(1+p)l_k^n$ ...公式10

由该公式10，确定通项l_k ⁿ为公式11。

[公式11]

$l_k^n=l_k{(1+p)}^n$ ...公式11

当N表示以从具有被存储在属性存储单元150中的属性的钢板的基本数量中减去既不具有在加工顺序中的确定位置又不试图被插入的钢板的数量的这种方式而获得的值时，将可插入区段k中的钢板的数量的宽松期望值表达为数量N、概率p和区段k中的数量l_k的乘积(公式12)。

[公式12]

$l_k^N-l_k=l_k{(1+p)}^N-l_k\≈{\mathrm{Npl}}_k$ ...公式12

第一计算部分1410通过计算公式12来计算宽松期望值。但是，该期望值是在对上限值的不严格的约束下的宽松期望值。由于此原因，考虑对上限值的位置约束，应该将可插入区段k中的钢板的数量限制为m_k或更少。此外，数量m_k仅指示在将钢板仅插入区段k的情况下可插入的钢板的数量。由于此原因，如果在区段k之前的区段中插入一个或多个钢板，则可插入区段k的钢板的数量进一步减少。具体地，可插入的钢板的数量减少了插入区段k之前的区段中的钢板的数量。当s_k表示被插入区段k中的钢板的数量的期望值时，将期望值表达为以下的公式13。

[公式13]

$s_k=\min (m_k-\underset{l=1}{\overset{k-1}{\mathrm{\Σ}}}{s}_l,{\mathrm{Npl}}_k)$ ...公式13

通过随着k从1逐一增加而计算公式13来计算对于每个区段k的s_k。

[公式14]

$s=\underset{k}{\mathrm{\Σ}}{s}_k$ ...公式14

如公式13和14所示，对于从前端开始的每个区段k，第一计算部分1410选择以下之中较小的一个作为可插入的钢板的数量的期望值：通过从可插入到区段k中的钢板的数量m_k中减去与区段k之前的区段对应的期望值的总和而获得的值；和对于区段k计算的宽松期望值Npl_k。以这种方式，第一计算部分1410可以对所有区段计算可插入的钢板的数量的期望值。

在此，描述回到图18。随后，第二计算部分1420对所产生的钢板队列的每个计算指数值，该指数值指示钢板队列违反对下限值的约束的程度(S1840)。例如，在下列过程中实行该计算。第二计算部分1420选择每类钢板的第一个钢板，并对每个所选的第一钢板计算将被插入到第一钢板前的区段中的钢板的数量的期望值。由于在第一钢板前的区段应该的确满足对上限值的约束，因此要被插入到前面的钢板之前的区段中的钢板的数量等于宽松期望值。换句话说，第二计算部分1420通过将以下值相乘来计算期望值：通过从基本数量中减去队列中的钢板的数量而获得的数量N；满足概率p；以及在前面的钢板之前的区段中所包括的钢板的数量l_k。

然后，关于具有即使当将期望值添加到位置上时其位置也没有达到下限值的第一钢板的每类钢板，第二计算部分1420首先计算下限值与通过将期望值添加到第一钢板的位置而获得的值之间的差值，并然后通过计算这些差值的总和来计算指数值。该指数值指示这样的概率：即使当对所有基本数量的钢板重复执行插入操作时，在重复插入操作完成时也不满足对下限值的约束。

接下来，第三计算部分1430计算第一估计值，该第一估计值指示用于由生成部分1405生成的钢板队列的每个的钢板加工的效率(S1850)。其后，选择处理部分1440根据通过结合第一估计值、由第一计算部分1410所计算的期望值和由第二计算部分1420所计算的指数值而获得的第二估计值，来选择钢板要被插入到的位置(S1860)。例如，第二估计值是这样的估计函数的值：当第一估计值较大时该函数取较大值，当由第一计算部分1410计算的期望值较大时该函数取较大值，并且当由第二计算部分1420所计算的指数值较小时该函数取较大的值。

选择处理部分1440判断在由生成部分1405生成的钢板队列中的任意一个中的第二估计值是否增加(S1865)。如果第二估计值不增加(S1865：否)，则局部搜索部分840将处理移动到S1890，并对下一钢板重复该处理。如果第二估计值增加(S1865：是)，则选择处理部分1440选择将钢板插入其中以便生成具有最大的第二估计值的钢板队列的位置(S1870)。其后，插入单元1450将钢板插入到所选位置(S1890)。局部搜索部分840对其属性被存储在属性存储单元150中的所有钢板执行前述处理(S1890)。

为了通过相继将钢板插入加工顺序中来增加加工效率，在上文中通过参考图18到20所描述的局部搜索部分840根据在稍后阶段可进一步插入的钢板的数量的期望值来确定每个钢板要被插入到的位置。这使得能够增加被插入的钢板的数量，并从而能够使得如此生成的所得到的钢板队列产生甚至更高的加工效率。根据本发明人做出的试验，比较相互在局部搜索部分840的处理之前和之后的钢板队列的加工效率的结果示出，该加工后的加工效率等于或被改善了多于处理前的效率达90％的高概率或更多。

图21示出用作顺序确定系统140的信息处理装置20的硬件配置的例子。信息处理装置20包括CPU外围单元、输入/输出单元和遗赠(legacy)输入/输出单元。CPU外围单元包括CPU 2100、RAM 2120和图形控制器2175，其所有都通过主机控制器2182彼此连接。输入/输出单元包括通信接口2130、硬盘驱动2140和CD-ROM驱动2160，其所有通过输入/输出控制器2184与主机控制器2182连接。遗赠输入/输出单元包括ROM 2110、软盘驱动2150和输入/输出芯片2170，其所有都与输入/输出控制器2184连接。

主机控制器2182将RAM 2120与都以高传输速率访问RAM 2120的CPU2100和图形控制器2175连接。根据被存储在ROM 2110和RAM 2120中的程序操作CPU 2100，并且CPU 2100控制每个组件。图形控制器2175获取由被提供在RAM 2120中的帧缓冲器中的CPU 2100等生成的图像数据，并使得在显示器件2180上显示所获得的图像数据。替代地，图形控制器2175可以内在地包括存储由CPU 2100等生成的图像数据的帧缓冲器。

输入/输出控制器2184将主机控制器2182与通信接口2130、硬盘驱动2140和CD-ROM驱动2160连接，其所有都是较高速的输入/输出器件。通信接口2130通过网络与外部器件通信。硬盘驱动2140存储将由信息处理装置20使用的程序和数据。CD-ROM驱动2160从CD-ROM 2195读取程序或数据，并将所读出的程序或数据提供给RAM 2120或硬盘驱动2140。

此外，输入/输出控制器2184与ROM 2110和诸如软盘驱动2150和输入/输出芯片2170之类的较低速输入/输出器件连接。ROM 2110诸如在信息处理装置20的启动时由CPU2100执行的引导程序的程序和取决于信息处理装置20的硬件的程序。软盘驱动2150从软盘2190中读取程序或数据，并通过输入/输出芯片2170将所读出的程序或数据提供给RAM 2120或硬盘驱动2140。输入/输出芯片2170与软盘2190和具有例如并口、串口、键盘端口、鼠标端口等的各种输入/输出器件连接。

由用户使用被存储在诸如软盘2190、CD-ROM 2195和IC卡之类的记录介质中的程序来提供要被提供给信息处理装置20的程序。通过输入/输出芯片2170和/或输入/输出控制器2184从记录介质读取程序，并将该程序安装在信息处理装置20上。然后，执行该程序。由于程序致使信息处理装置20执行的操作与通过参考图1到20所描述的顺序确定系统140的操作一致，因而在此省略其描述。

可以将上述程序存储在外部存储介质中。除了软盘2190和CD-ROM 2195之外，使用的存储介质的例子是诸如DVD或PD的光记录介质、诸如MD的磁光记录介质、磁带介质和诸如IC卡的半导体存储器。可替换地，可以通过使用被提供在与私有通信网络或因特网连接的服务器系统中的诸如硬盘和RAM的存储器件作为记录介质，经由网络将程序提供给信息处理装置20。

图22示出提供用于提供采用顺序确定系统140的服务的方法的例子。顺序确定系统140使能提供用于改进钢板的加工效率的服务。例如，工程师在钢板中实行顺序确定系统140(S2200)。如上所述，顺序确定系统140包括分类部分800、粗略调度部分810、判断部分820、详细调度部分830、局部搜索部分840和输出部分850。然后，响应于钢板的管理者的请求，工程师改变用于确定加工操作的加工顺序的各种顺序约束或目标函数(S2210)。另外，响应于钢板的管理者的请求，工程师改变用于确定当按该加工顺序排列钢板时每个钢板被插入到的位置的位置约束(S2220)。可以通过改变被存储在问题存储单元160中的内容来实现这些改变。

通过以前述方式响应于钢板的管理的请求而调整顺序约束等，可以对于各种消费者的需要定制顺序确定系统140，从而改善加工效率。

在上文中，已经通过使用实施例描述了本发明。但是，本发明的技术范围不限于上述实施例。本领域技术人员显而易见的是，可以对本实施例做出各种修改和改进。例如，根据本实施例的顺序确定系统140不仅能够确定用于钢板的、而且能够确定用于其它类型产品的、以便提高加工效率的适当的加工顺序。从本发明的权利要求的范围显而易见的是，因此修改而改进的实施例包括在本发明的技术范围内。

Claims (11)

1.一种用于确定钢板的加工顺序的系统，包括：

约束存储单元，用于存储位置约束，所述位置约束限定了在按所述加工顺序排列所述钢板时应排列各个种类的钢板的位置的范围；

选择单元，用于优先选择即使插入新钢板仍然满足所述位置约束、并且对于插入所述新钢板之后的钢板队列在满足所述位置约束的情况下指示可以进一步插入的钢板数量的期望值变得更大的位置，作为在已经按加工顺序排列了的钢板队列中应插入该新钢板的位置；以及

插入单元，用于在所述选择单元选择的所述位置插入所述新钢板，并用于输出指示插入所述新钢板后的钢板队列的数据。

2.根据权利要求1所述的系统，其中

所述约束存储单元存储被确定用于每类钢板的并且限定了在排列所述每类钢板的加工顺序中的最后位置的上限值，作为所述位置约束；以及，

所述选择单元包括：

生成部分，用于通过将所述新钢板插入到在已经按所述加工顺序排列的钢板队列中的所述新钢板的类型的上限值之前的每个位置，来生成代表用于插入后的钢板队列的候选的多个钢板候选队列；

第一计算部分，其从每个钢板候选队列中选择在每类钢板的最后位置上排列的钢板，并且其然后基于在所选钢板的位置和所选钢板的类型的上限值之间的差值，来计算可插入到由所选钢板分隔的每个区段中的钢板的数量的期望值；以及

选择处理部分，用于选择插入所述新钢板的位置，作为所述新钢板要被插入到的位置。

3.根据权利要求2所述的系统，其中所述选择处理部分选择插入所述新钢板以便生成具有对每个区段所计算的期望值的较大总和的钢板候选队列的位置，作为所述新钢板要被插入到的位置。

4.根据权利要求2所述的系统，进一步包括候选存储单元，用于存储被预定为要被加工的候选的基本数量的钢板的每个的类型、轧压后的厚度和轧压后的宽度中的至少一个，其中

所述约束存储单元存储当新钢板被插入到从已经按加工顺序排列的钢板队列中随机选择的位置时、所述新钢板满足对钢板的轧压后的厚度和轧压后的宽度中的至少一个的顺序约束的满足概率，以及

关于由所述生成部分生成的钢板候选队列的每个，所述第一计算部分：

计算在用作每个所述区段中的末尾侧上的边界的钢板的位置和对应的上限值之间的差值；

按由所述满足概率乘以所述区段中所包括的钢板的数量再乘以通过从所述基本数量中减去既不具有在加工顺序中的确定位置又不试图被插入的钢板的数量而得到的值的方式，对每个所述区段计算宽松期望值，所述宽松期望值是当放松所述位置约束时可插入的钢板的数量的期望值；以及

选择在对于所述区段而计算的所述宽松期望值与通过从所述区段的所述差值中减去与所述区段之前的区段对应的所述期望值的总和而获得的值之间的较小值，作为可插入的钢板的数量的期望值。

5.根据权利要求2所述的系统，其中

所述约束存储单元进一步存储被确定用于每类钢板并限定在排列每类钢板的加工顺序中的第一位置的下限值，作为所述位置约束；以及

在按当放松对所述下限值的所述位置约束时所确定的加工顺序排列的钢板队列中，所述生成部分通过不论所述下限值是多少而将所述新钢板插入到在所述新钢板的类型的上限值之前的多个位置的每个，来生成所述代表用于插入后的钢板队列的候选的多个钢板候选队列，

所述选择单元进一步包括第二计算部分，其从所生成的钢板候选队列的每个中选择在每类钢板的第一位置上排列的钢板，并基于在每个所选钢板的位置和对应于所选钢板的下限值之间的差值，来计算指示每个所述钢板候选队列违反对所述下限值的位置约束的程度的指数值，以及

所述选择处理部分选择插入所述新钢板以便生成具有较小指数值的钢板候选队列的位置，作为所述新钢板要被插入到的位置。

6.根据权利要求5所述的系统，还包括候选存储单元，用于存储被预定为要被加工的候选的基本数量的钢板的每个的类型、轧压后的厚度和轧压后的宽度中的至少一个，其中

所述约束存储单元存储当新钢板被插入到从已经按加工顺序排列的钢板队列中随机选择的位置时、所述新钢板满足对所述新钢板的轧压后的厚度和轧压后的宽度中的至少一个的顺序约束的满足概率，以及

关于由所述生成部分生成的所述钢板候选队列的每个，所述第二计算部分：

选择在所述钢板候选队列中的每类钢板的第一位置上排列的钢板，

按由所述满足概率乘以在所述钢板候选队列中的所选钢板之前的钢板数量再乘以通过从所述基本数量中减去所述钢板候选队列中的钢板数量而得到的值的方式，计算要被插入到每个所选钢板之前的钢板的数量的期望值，以及

通过相加如下差值来计算指数值，所述差值是对于每个具有即使当加上所述期望值时其位置也达不到所述下限值的第一钢板的这类钢板而获得的，并且所述差值每个都是在通过将所述第一钢板的位置加到所述期望值上而获得的值和与这类所述钢板相对应的下限值之间的差值。

7.根据权利要求5所述的系统，还包括第三计算部分，用于计算指示钢板加工效率的第一估计值，其中

所述选择单元计算第二估计值，所述第二估计值在所述第一估计值较大时取较大值，在所述期望值较大时取较大值，在所述指数值较小时取较大的值，然后选择具有最大的所述第二估计值的位置。

8.根据权利要求1所述的系统，还包括候选存储单元，用于存储被预定为要被加工的候选的基本数量的钢板的每个的类型，其中

所述选择单元对在基本数量的钢板中每个都不具有在所述加工顺序中的确定位置的所有钢板来重复选择不具有在所述加工顺序中的确定位置的钢板要被插入到的位置的处理。

9.根据权利要求1所述的系统，还包括顺序确定系统，所述顺序确定系统包括分类部分、粗略调度部分、判断部分和详细调度部分，其中

在依次加工多个钢板的多个加工操作的每对之间限定基于每个加工操作的第一属性的第一顺序约束和基于每个加工操作的第二属性的第二顺序约束，

所述分类部分根据所述第一属性的属性值，来将所述多个加工操作分类成多个集群，并按满足所述第二顺序约束的顺序来排列所述集群的每个中所包括的加工操作，

所述粗略调度部分将所述第一顺序约束看作所述多个集群之间的顺序约束，并按最大化所述钢板加工效率的顺序来排列所述多个集群，

所述判断部分判断在第一集群的队列中的最后加工操作和在所述第一集群之后排列的第二集群的队列中的第一加工操作之间是否满足所述第二顺序约束，以及

在不满足所述第二顺序约束的条件下，所述详细调度部分搜索出与所述第一集群的队列中的最后加工操作和所述第二集群的队列中的第一加工操作之间满足所述第二顺序约束的另一加工操作，并在所述第一集群之后且在所述第二集群之前排列搜索出的加工操作，以及

所述选择单元选择所述新钢板要被插入到的、在指示由所述详细调度部分排列的加工顺序的钢板队列中的位置。

10.根据权利要求9所述的系统，其中

所述加工操作是通过一组工作滚轮轧压钢板的处理，

所述粗略调度部分通过求解整数计划问题来确定哪个集群要在多个块的每个中进行加工操作，这些块是通过划分从通过所述工作滚轮来开始轧压钢板时到在依次轧压多个钢板后用新工作滚轮更换所述工作滚轮时的时间段而获得的，以及

所述整数计划问题包括，

保存用于每个块和每个集群的状态值的变量，所述状态值指示是否进行每个所述集群中所包括的加工操作，

第一顺序约束，作为集群间的约束，所述第一顺序约束表达为用于第一属性的每个的线性不等式，所述线性不等式采用包括了包括具有相同第一属性值的加工操作、并且被分配给每个块的集群的数量的范围，作为变量，以及

目标函数，用于使用所述变量的值来计算指示钢板加工效率的指数值。

11.一种确定钢板的加工顺序的方法，包括步骤：

约束存储步骤，存储位置约束，所述位置约束限定了当按所述加工顺序排列所述钢板时每类钢板要被插入到的位置的范围；

选择步骤，优先选择在插入新钢板后可以进一步插入到钢板队列中的钢板数量的期望值更大且同时满足位置约束的位置，作为在已经按加工顺序排列了的钢板队列中插入该新钢板的位置；以及

插入步骤，将所述新钢板插入到所选位置，并输出指示插入后的钢板队列的数据。

Images