用于将排程问题切分成子问题的方法和系统

摘要

计算系统接收用户输入的排程问题数据。排程问题数据涉及排程问题，且该排程问题数据包括一个或多个站以及待通过至少一个站执行的任务。计算系统使用排程问题数据建构图形问题。图形问题包括图形。计算系统使用切分算法将图形切分成子图形以产生满足一阈值的切分结果，且计算系统从切分结果中的子图形中识别一个或多个任务异常。一个或多个任务异常为可分配至多于一个子图形的任务。计算系统使用切分结果产生关于一个或多个任务异常的排程子问题。

说明书

技术领域

本发明的实施方式大致涉及排程(scheduling)，更具体地，涉及将排程 问题切分成子问题。

背景技术

解决制造排程问题的困难可与问题大小有关。典型的制造排程问题涉及大 量的站(stations)和待在这些站上执行的很多任务。例如，排程可取决于工具 数量、批次(lots)数量、操作的顺序、约束条件等等。传统的排程系统花费 大量的时间和计算资源来解决涉及许多变量和因素的排程问题。困难随着排程 问题大小的增大而非常快地增长。因此，大的排程问题不可能被直接解决。

数据数据数据数据算法计算机存储介质计算机存储介质数据数据数据数据算 法存储器存储器数据数据数据数据算法附图说明

本发明在附图中以举例而非限制的方式图示，其中，相同的参考标记指示 相同的元件。应注意，本文中对“一”或“一个”实施方式的不同引用不一定 指同一个实施方式，并且这些引用是指至少一个。

图1为图示利用排程问题切分器模块的排程系统的框图。

图2为排程问题切分器模块的一个实施方式的框图。

图3A至3D图示了表示排程问题的示例性图表。

图4图示了用于将排程问题切分成为排程子问题的方法的一个实施方式。

图5图示了示例性排程子问题和示例性任务异常(exception)。

图6图示了示例性计算机系统。

具体实施方式

本发明的实施方式涉及用于将排程问题切分成排程子问题的方法和系统。 计算系统接收用户输入的排程问题数据。排程问题数据识别站和待通过至少一 个站执行的任务。计算系统使用排程问题数据建构一个图形问题。该图形问题 可以包括图形，计算系统可使用切分算法将该图形分割成子图形，以产生满足 一阈值的切分结果。阈值的实例可包括(且不限于)：产生具有最少任务异常 的切分结果、产生具有最少数量的任务类型的切分结果、产生具有最少数量的 成为异常的任务配方(task recipes)的切分结果。计算系统从子图形中识别任 务异常。任务异常可以是被分配至多于一个子图形的任务。计算系统使用切分 结果产生排程子问题。各实施方式通过将大的排程问题自动切分成子问题并且 识别与这些子问题相关联的一个或更多个任务异常，极大减少了用以解决制造 排程问题的时间和资源的量。

图1为图示了制造系统100的框图，该制造系统100包括制造系统数据源 (例如，制造执行系统(manufacturing execution system；MES)101)、调度器 (dispatcher)103和排程系统105(例如通过网络120通信)。网络120可以 是局域网(local area network；LAN)、无线网络、移动通信网络、广域网(wide area  network；WAN)(诸如因特网)，或类似的通信系统。

在一个实施方式中，排程系统105包括排程问题切分器模块107。在另一 实施方式中，排程系统105(例如通过网络120与外部排程问题切分器模块107 通信。MES101、调度器103、排程系统105和排程问题切分器模块107可分 别由任何类型的计算装置主存(hosted)，这些计算装置包括服务器计算机、 网间连接计算机(gateway computer)、桌上型计算机、膝上型计算机、平板 计算机、笔记本计算机、个人数字助理(personal digital assistant；PDA)、移动通 信装置、蜂窝式电话、智能电话、手持式计算机，或类似的计算装置。可选地， MES101、调度器103、排程系统105和排程问题切分器模块107的任何组合 可被主存于单个计算装置上，该计算装置包括服务器计算机、网间连接计算机、 桌上型计算机、膝上型计算机、移动通信装置、蜂窝式电话、智能电话、手持 式计算机，或类似计算装置。

排程系统105可从排程问题切分器模块107接收与排程问题相关的输入以 产生关于一个或更多个任务可何时执行以及在哪些站(工具)上执行的排程。 排程可以是各站处理的任务列表。排程可包括任务开始时间。站可被认证以执 行某些任务。任务可以是用于制造半导体的任务，且可存在不同类型的任务。 任务的实例可包括(且不限于)制造产品的任务、使用主光罩(reticle)制造 工具的任务、检查主光罩制造工具的任务、处理大量晶片的任务等等。

排程问题切分器模块107可识别排程问题并且将排程问题自动地切分成 更小的排程子问题。排程问题可涉及一组任务T和一组(例如，组S)站，站 也称为工具。例如，排程问题可涉及四十个至五十个站和多于两千个任务。每 一任务可在一个或更多个站上处理。若存在不相交的任务子集，诸如任务子集 T1和任务子集T2，以使得T为任务子集T1和任务子集T2的并集，并且存在 类似的不相交的站子集，诸如站子集S1及站子集S2，以使得组S为站子集 S1和站子集S2的并集，则排程问题切分器模块107可将排程问题切分，并且 其中任务子集T1中的任务仅可在站子集S1中的站上处理，且任务子集T2中 的任务仅可在站子集S2中的站上处理。

排程问题切分器模块107可自动地将制造排程问题转换成图形理论问题， 并且可将切分算法应用于图形理论问题以解决该问题。排程问题切分器模块 107可将该解决方案从图形理论问题格式(format)转换回用于排程问题的格 式，其中排程问题可由更小的子问题以及与这些子问题相关联的一个或更多个 任务异常来表示。排程问题切分器模块107可将反映更小排程子问题的数据提 供至排程系统105，排程系统105可使用该数据为待执行的各种任务临时地排 定时间。在一个实施方式中，排程系统105被耦接至工厂系统数据源(例如， MES101、ERP)以接收批次数据和设备状态数据，并且排程系统105使用排 程子问题数据、批次数据和设备状态数据以临时地排程待执行的任务。在一个 实施方式中，排程系统105可以包括图形用户界面(graphical user interface；GUI) 产生器111以产生用户界面109(例如，GUI)且向用户(例如，工业工程师) 提供用户界面109(例如，GUI)。用户界面109可使用户(例如，工业工程 师)能够将临时排程模型化。在一个实施方式中，排程系统105向调度器103 提供全部排程。调度器103可通过MES101集成以相应地调度(例如)晶片 批次。

图2为排程问题切分器模块200的一个实施方式的框图。在一个实施方式 中，排程问题切分器模块200可与图1的排程问题切分器模块107相同。排程 问题切分器模块200可包括图形产生器子模块205、图形切分器子模块210、 问题翻译器子模块215和用户界面(UI)产生器子模块225。

用户界面产生器子模块225可产生用户界面202，该用户界面202可接收 一组排程问题数据251作为排程问题的用户输入。排程问题切分器模块200 也可从制造系统中的另一系统接收一组排程问题数据251或该排程问题数据 251的一部分。排程问题数据251可定义待执行的任务(例如，一组任务T) 和用于执行该任务的一组(例如，组S)站或工具。排程问题数据251也可描 述是否可在一个或更多个站上处理任务，且排程问题数据251可识别用于执行 该任务的一个或更多个站。排程问题数据251可存储于数据存储库250中，该 数据存储库250被耦接至排程问题切分器模块200。对于存储在数据存储库250 中的多个排程问题，可能存在多组排程问题数据251。数据存储库250可为永 久性存储单元。永久性存储单元可为本地存储单元或远程存储单元。永久性存 储单元可为磁性存储单元、光学存储单元、固态存储单元、电子存储单元(主 存储器)或类似的存储单元。永久性存储单元可为单片(monolithic)装置或 分布式的一组装置。如本文中所使用的“组”代表任何正整数个项目。

图形产生器子模块205可使用特定排程问题的排程问题数据251以将排程 问题格式转换为图形问题格式。图形产生器子模块205可建构图形问题以表示 排程问题。图形产生器子模块205可产生图形问题的图形253。图形253可存 储在数据存储库250中。在数据存储库250中可存储用于各种排程问题的图形 253。图形253可以是用以将来自某一集合(collection)的对象(objects)之 间的成对关系模型化的数学结构。图形253可代表顶点或节点的集合以及连接 顶点(节点)对的边的集合。边在下文中也被称为线。图形253可包括图形特 性，例如(但不限于)用于排程问题的S组站中的各站(例如，s1、s2……sn) 可为图形中的节点，并且在图形253中可存在连接对应于一对站的节点的边 (线)，以指示存在可在该对站上执行的至少一个任务。

排程问题数据251可包括(例如)由用户输入所定义的、一个或更多个权 重类型和/或权重值。图形产生器子模块205可基于诸如与站有关的约束条件 (constraints)而分配权重至图形253中的各对被连接的站，以指示(例如) 被连接的站的重要性。图形产生器子模块205可基于排程问题数据251而将权 重分配至图形253中的线。可计算的权重类型的实例可包括(且不限于)：可 在被连接的两个站上执行的任务的百分比，其中基于任务的重要性(例如，基 于用户输入的任务优先级)对该百分比加权；可在被连接的两个站上处理的操 作或路线步骤的百分比；可在被连接的两个站上处理的操作或路线步骤的百分 比，利用该操作的期望批次的百分比进行加权；以及指示一个任务相对于另一 任务的重要性的百分比(例如，任务1之后应是任务2)。各实施方式同时应 用于工作现场(job shop)排程和流程现场(flow shop)排程，其中在工作现 场排程中，各任务是独立的，而在流程现场排程中，任务表示用于单个制造批 次的多个操作并且应以特定顺序处理用于一个批次的任务。被分配至线的权重 值可反映流程现场排程，以指示相邻操作的重要性(也称为先验约束(precedent  constraint))。图形产生器子模块205可进一步基于其他参数调整权重，其他 参数诸如但不限于：站之间的物理距离、站之间的物理相似性、品牌(brand) 或站类型。

图3A为排程问题的示例性图形300。排程问题的排程问题数据可包括站 s1、s2、s3、s4和任务t1至t11。图形300可包括每个站的节点(例如，节点 301A至301D)。图形300可包括连接节点对的线(例如，线303A至303F)， 这些线指示存在可在对应于被连接节点的两个站上执行的一些任务。可基于排 程问题数据分配线303A至303F。例如，排程问题数据可以指定任务t1可在 站s1上处理；任务t2、t3和t4可在站s1和s2上处理；任务t5和t6可在站 s2上处理；任务t7可在站s3上处理；任务t8和t9可在站s3和s4上处理； 任务t10可在站s4上处理；任务t11可在站s2和s3上处理。基于此数据，例 如在图形300中可存在将表示站s1的节点301A连接至表示站s2的节点30B 的线303A，以指示存在可在两个站s1和s2上执行的至少一个任务(例如，t2、 t3、t4)。线303A至303F也可以被分配权重(例如，305A至305F)。在一 个实施方式中，线权重指示可在对应于被该线连接的节点的两个站上处理的任 务数量。图3B为具有基于可在两个站上处理的任务数量而分配的权重的示例 性图形350。例如，值“3”可作为权重307分配至线303A，以指示站两个s1 和s2可处理由排程问题数据定义的三个任务(例如，t2、t3和t4)。在另一 实施方式中，线权重指示反映相邻操作的重要性的流程现场排程。

回到图2，图形切分器子模块210可将图形253分割成为子图形，以将排 程问题切分成排程子问题来产生满足阈值的切分结果255。阈值的实例可包括 (且不限于)：产生具有最少任务异常的切分结果255、产生具有最少数量的 任务类型的切分结果255、产生具有最少数量的成为异常的任务配方的切分结 果255。任务异常可以是可在多于一个子图形中的站上执行的任务。例如，任 务异常可以是可由站子集S1中的站和站子集S2中的站执行的任务。图形切分 器子模块210可通过应用切分算法切分图形253的线以产生切分结果255。切 分结果255可表示已分割的图形253的子图形。切分结果255可存储在数据存 储库250中。切分可以是将图形253的顶点(节点)分割成为两个不相交的子 集。切分C＝(S,T)的大小可为切分集(cut-set)中的线的数量。若对线加权， 则切分的值可以是权重的和。在一个实施方式中，图形切分器子模块210将最 小切分算法应用于图形253，该最小切分算法为进行最小切分以将图形253切 分成两个子图形(例如，G1和G2)的算法。可使用将图形切分成任一数量的 子图形的各种切分算法。若用于切分的切分集具有最小的部分(elements)数 量，则切分可为最小切分。例如，横跨三条线的切分可产生六个部分(例如， 每条被切分的线为两个部分)，横跨两条线的切分可产生四个部分。横跨两条 线的切分可为最小切分。图形切分器子模块210可基于总权重切分线。图3C 为根据各种实施方式的、基于线的总权重切分线的排程问题的示例性图形 370。图形370可具有基于可在由线连接的两个站上处理的任务数量的线权重 (例如，权重371A至371F)。基于总权重切分线的切分结果可(例如)为两 个子图形G1和G2。图形切分器子模块可切分具有最小总权重的线。例如， 可切分线303B、303D、303E和303F。图3D为在切分具有最小总权重的线(例 如，连接s1和s4的线、连接s2和s3的线、连接s1和s3的线、连接s4和s2 的线)之后，可切分成子图形G1391A和子图形G2391B的排程问题的示例 性图形390。

对于每一子图形(子图形G1391A和子图形G2391B)，图形切分器子模 块210可识别站集(例如，S)的子集(例如，S1、S2)，其中每个站子集有 相应子集的任务(任务子集)。例如，在图3D中，图形切分器子模块210可 识别站子集S1对应于子图形G1391A。站子集S1可包括站s1和站s2。图形 切分器子模块210还可识别站子集S2对应于子图形G2391B。站子集S2可包 括站s3和站s4。图形切分器子模块210可识别站子集S1具有相应的任务子集 T1，以及站子集S2具有相应的任务子集T2。任务子集T1可包括任务t1至t6。 任务子集T2可包括任务t7至t10。

图形切分器子模块210也可使用切分结果255中的子图形以识别一个或更 多个任务异常。该一个或更多个任务异常可被分组以形成另一任务子集(例如， T3)。例如，图形切分器子模块210可确定如果将图形390切分成子图形G1 391A及子图形G2391B，那么可能仅存在一个任务异常。该任务异常可由权 重值“1”373表示，该权重值可表示可以在s2(站2)和s3(站3)上处理的 任务11(t11)。例如，因为任务t11可在处于不同子图形中的站上处理，所 以t11为任务异常。

问题翻译器子模块215可使用子图形、每个子图形的站子集和每个子图形 的任务子集来识别排程问题的子问题。问题翻译器子模块215可(例如)使用 存储于数据存储库250中的模板257和/或配置数据259以将子图形转换成子 问题的格式。问题翻译器子模块215可将站子集和对应于站子集的任务子集分 组为子问题。例如，站子集S1和任务子集T1可被分组以形成子问题1，站子 集S2和任务子集T2可被分组以形成子问题2。问题翻译器子模块215也可识 别与排程问题的子问题相关联的任务异常。例如，问题翻译器子模块215可将 任务t11识别为与子问题1和子问题2相关联的任务异常。问题翻译器子模块 215可产生另一组任务(例如，T3)以表示一个或更多个任务异常。最小数量 的任务异常可以是最佳子图形的指示。例如，子图形G1391A和子图形G2 391B可产生一个任务异常。在此实例中，子图形G1和子图形G2可指示图形 的最佳切分。

图4为用于将排程问题切分成排程子问题的方法400的一个实施方式的流 程图。方法400可由处理逻辑执行，处理逻辑可包括硬件(例如，电路、专用 逻辑、可编程逻辑、微码(microcode)，等等)、软件(例如，在处理装置上执 行的指令)，或硬件与软件的组合。在一个实施方式中，方法400由排程问题 切分器模块107执行，该排程问题切分器模块107由图1的计算装置主存。

在方框401处，处理逻辑接收用户输入的排程问题数据。排程问题数据可 包括从制造系统中的另一系统接收的数据。排程问题数据的用户输入可包括 (例如)且不限于：站的序号、描述特定站的站数据(例如，状态)、待执行 的任务(例如，一组任务T)、用于执行任务的一组(例如，组S)站或工具、 权重类型和权重值。权重类型和权重值可为用于站和/或任务的。排程问题数 据也可描述是否可在一个或更多个站上处理任务，并且可识别哪些站可执行任 务。

在方框403处，处理逻辑使用排程问题数据建构图形问题。处理逻辑可应 用来自用户输入的权重(若存在)以建构加权图形问题。在方框405处，处理 逻辑通过应用切分算法将图形切分成子图形，以产生满足阈值的切分结果。阈 值的实例可包括(且不限于)：产生具有最少任务异常的切分结果、产生具有 最少数量任务类型的切分结果、产生具有最少数量的成为异常的任务配方的切 分结果。处理逻辑选择满足阈值的子图形的最佳切分。阈值可以是用户定义的 阈值。当建构图形时，处理逻辑可应用不同的边(线)权重。不同权重可使得 不同类型的异常最少化。在方框407处，处理逻辑识别来自切分结果中的子图 形的一个或更多个任务异常。在方框409处，处理逻辑使用切分结果产生关于 一个或更多个任务异常的排程子问题。随后，处理逻辑可向排程系统提供子问 题和任务异常。排程系统可使用试探法(heuristic)以将任务异常自动分配至 子问题。例如，试探法可基于子问题的带宽(bandwidth)。在另一实例中， 可(例如)通过排程系统通知用户(例如，处理工程师)一个或更多个任务异 常，且该用户可将任务异常分配至子问题。图5图示了通过图3A至3D中的 图形所描述的排程问题的示例性排程子问题及示例性任务异常。例如，处理工 程师可确定子问题1不具有足够的工作，并且可将任务异常任务11分配至子 问题1。

回到图4，方法400的部分可为迭代法。迭代次数可基于可配置和/或用户 定义的值。例如，处理逻辑可执行多次迭代，直至(例如)识别了最小数量的 的任务异常。例如，在方框405处，处理逻辑可初始地切分图形(例如，图 3B中的图形350)，其中子图形1可包括站s1和站s4，并且子图形2可包括 站s2和站s3。利用这种切分，处理逻辑可识别(例如)五个任务异常。例如， 任务t2、t3和t4可在站s1和s2上执行，并且任务t8和t9可在站s4和s1上 执行。随后，在方框405处，处理逻辑可切分图形并且识别(例如)一个任务 异常(例如，任务t11可在站s2和s3上执行)，其中子图形1可包括站s1和 s2，子图形2可包括站s4和s3。在方框405处，处理逻辑可比较来自各种切 分的任务异常的数量，并且可选择产生最少数量任务异常的切分。例如，处理 逻辑可选择该切分，其中子图形1可包括站s1和s2，且子图形2可包括站s4 和s3，因为该特定的切分产生一个任务异常。

图6为图示示例性计算装置600的框图。在一个实施方式中，该计算装置 对应于主存图1的排程问题切分器模块107的计算装置。计算装置600包括一 组指令，该指令用于使该机器执行本文所述任何一个或更多个方法。在可选的 实施方式中，该机器可连接(例如，网络连接)至LAN、内联网、外联网， 或因特网中的其他机器。该机器可在客户端-服务器网络环境中的服务器机器 的容量(capacity)中操作。该机器可为个人计算机(personal computer；PC)、 机顶盒(set-top box；STB)、服务器、网络路由器、交换机或桥接器，或任何能 够运行一组指令622(顺序或以其他方式)的机器，该组指令622规定了待由 该机器完成的动作。进一步地，虽然仅图示了单个机器，但是术语“机器”也 应当理解为包括任何个别地或联合地运行一组(或多组)指令622以执行本文 所述之任何一个或更多个方法的机器的集合。

示例性计算机装置600包括通过总线630互相通信的处理系统(处理装置) 602、主存储器604(例如，只读存储器(ROM)、闪存、诸如同步DRAM(SDRAM) 的动态随机存取存储器(DRAM)等等)、静态存储器606(例如，闪存、静态 随机存取存储器(SRAM)等等)和数据存储装置618。

处理装置602表示一个或更多个通用处理装置，诸如微处理器、中央处理 单元等等。更特别地，处理装置602可为复杂指令集计算(complex instruction set  computing；CISC)微处理器、精简指令集计算(reduced instruction set computing； RISC)微处理器、超长指令字(very long instruction word；VLIW)微处理器，或实 施其他指令集的处理器或实施指令集组合的处理器。处理装置602也可为一个 或更多个专用处理装置，诸如特定应用集成电路(application specific integrated  circuit；ASIC)、现场可编程门阵列(field programmable gate array；FPGA)、数字 信号处理器(digital signal processor；DSP)、网络处理器，等等。处理装置602 被配置以运行用于执行本文所述操作及步骤的排程问题切分器模块670。

计算装置600可进一步包括网络界面装置608。计算装置600还可包括视 频显示单元610(例如，液晶显示器(liquid crystal display；LCD)或阴极射线管 (cathode ray tube；CRT))、字母数字输入装置612(例如，键盘)、光标控制 装置614(例如，鼠标)和信号产生装置616(例如，扬声器)。

数据存储库装置618可包括计算机可读存储介质628，在该计算机可读存 储介质628上存储实施本文所述方法或功能中的任何一个或多个的一组或多 组指令(例如，排程问题切分器模块670的指令)。排程问题切分器模块670 也可在其被计算装置600执行期间完全地或至少部分地常驻于主存储器604 内和/或处理装置602内，主存储器604和处理装置602也构成计算机可读介 质。排程问题切分器模块670可进一步经由网络接口装置608在网络620上传 输或接收。

虽然计算机可读存储介质628在示例性实施方式中图示为单个介质，但是 术语“计算机可读存储介质”应当包括存储一组或多组指令622的单个介质或 多个介质(例如，集中式或分布式数据库，和/或相关联的高速缓存(caches) 和服务器)。术语“计算机可读存储介质”也应当包括能够存储、编码或携带 一组指令622的任何介质，该指令用于由机器运行且使得机器执行本发明的任 何一个或更多个方法。术语“计算机可读存储介质”相应地应当包括(但不限 于)：固态存储器、光学介质和磁性介质。

在上述描述中阐述了许多细节。然而，对于了解本发明之益处的一般技术 人员显而易见的是，本发明的实施方式可在不需要这些特定细节的情况下实 现。在某些情况下，将公知的结构及装置以方框框图形式而非详细地图示，以 避免模糊本描述。

通过对计算机存储器内的数据位操作的算法和符号表示而呈现详细描述 的某些部分。这些算法描述和表示是数据处理技术领域的技术人员用以最有效 地将他们的成果之主旨传达给所属领域其他技术人员的手段。此处，算法通常 被设想为带来预期结果的一系列自洽性的步骤。该步骤为需要对物理量进行物 理操作的那些步骤。通常而非必须地，这些量采取能够存储、传送、组合、比 较以及其他可控的电信号或磁信号的形式。已证明，主要由于常见的用途，有 时将这些讯号称为位、值、元素、符号、字符、术语、数字等等是便利的。

然而，应注意到，所有这些和类似术语皆与适当的物理量相关联且仅为应 用于这些量的便利标记。除非特别叙述，否则如自上文中显而易见的，应理解 在本描述的全文中，利用诸如“接收”、“建构”、“切分”、“识别”、“产 生”、“分配”、“发送”等术语的论述代表计算装置或类似电子计算装置的 动作或处理，该计算装置或类似电子计算装置对在计算机系统寄存器和存储器 中表示为物理(例如，电子)量的数据进行操作并将其转换为在计算机系统存 储器或寄存器或其他这种信息存储装置中类似表示为物理量的其他数据。

本发明的实施方式还涉及用于执行本文操作的设备。该设备可为了所需目 的而特别地建构，或该设备可包含通用计算机，该通用计算机由存储在计算机 中的计算机程序而有选择地启动或重新配置。该计算机程序可存储于计算机可 读存储介质中，诸如但不限于包括光盘、只读光盘(Compact Disk-Read Only  Memory；CD-ROMs)及磁性光盘的任何类型光碟；只读存储器(ROMs)；随机 存取存储器(random access memories；RAMs)；EPROM、EEPROM；磁卡或光 学卡，或适合于存储电子指令的任何类型的介质。

应理解，上述描述意欲为说明性而非限制性的。在阅读且理解上述描述之 后，许多其他实施方式将对本领域技术人员是显而易见的。因此，本发明的范 围应参照所附权利要求以及该权利要求所被授予的等价物的全部范围来决定。