Scheduling of re-entrant flow shops
Scheduling of re-entrant flow shops
复制标题
DOI：
10.1016/0272-6963(83)90004-9
复制
发表时间：
1983-08
影响因子：
7.8
通讯作者：
S. Graves;H. C. Meal;Dan Stefek;Abdel Hamid Zeghmi
中科院分区：
文献类型：
--
作者：
S. Graves;H. C. Meal;Dan Stefek;Abdel Hamid Zeghmi
我们提出并开发了一个调度系统的一个非常特殊类型的流水车间。这种流水作业处理从加工角度来看是相同的各种作业。所有作业在车间的设施上具有相同的路由，并且在每个设施处需要相同的处理时间。然而，个别工作可能不同，因为它们可能在特定设施中执行不同的任务。这样的车间的例子是灵活的加工系统和集成电路制造过程。在柔性加工系统中，所有作业可能在设施上具有相同的路由，但执行的实际任务可能不同;例如，钻孔操作可能在孔的位置或大小方面有所不同。类似地，对于集成电路制造，尽管所有作业可以遵循相同的路线，但是作业将在生产线操作处被区分。光刻工艺在硅晶片上建立图案，其中图案根据所使用的掩模而不同。我们所考虑的流水车间还有另一个重要的特征，即作业路由是这样的，即一个作业可以一次或多次返回到任何设施。我们说，当一个工件返回到一个设施，它重新进入该设施的流程，因此我们称该车间为可重入流程车间。在集成电路制造中，特定的集成电路将多次返回到光刻工艺，以便在晶片上放置若干层图案。类似地，在柔性加工系统中，工件可能必须多次返回到特定工位以进行额外的金属切削操作。这些可重入的流水车间通常被当作一般的作业车间来操作和调度，忽略了车间流的内在结构。将这些车间视为作业车间意味着使用短视的调度规则来对每个设施的作业进行排序，并且通常需要大量的在制品库存队列以保持高设施利用率，但以长吞吐时间为代价。在本文中，我们开发了一种循环调度方法，利用流程的特点。循环周期是所需生产率（每天的工作）的倒数。周期计划是基于这样的要求，即在每个周期中，车间应该完成完成一项工作所需的所有任务，尽管可能是不同的工作。换句话说，在一个周期内，我们要求每个设施只完成一次分配给它的每项任务。根据这一要求，循环计划只是每个设施在每个循环期间必须执行的所有任务的顺序和时间安排。每个循环周期内，每个设施都应重复该循环计划。最佳循环调度的确定是一个非常困难的组合优化问题，我们不能最优地解决实际操作。相反，我们提出了一个计算机化的启发式程序，似乎非常有效地产生良好的时间表。我们已经发现，这些时间表的吞吐量时间是远远低于近视排序规则中使用的工作车间实现。我们正试图在集成电路制造工厂实施调度系统。
We propose and develop a scheduling system for a very special type of flow shop. This flow shop processes a variety of jobs that are identical from a processing point of view. All jobs have the same routing over the facilities of the shop and require the same amount of processing time at each facility. Individual jobs, though, may differ since they may have different tasks performed upon them at a particular facility. Examples of such shops are flexible machining systems and integrated circuit fabrication processes. In a flexible machining system, all jobs may have the same routing over the facilities, but the actual tasks performed may differ; for instance, a drilling operation may vary in the placement or size of the holes. Similarly, for integrated circuit manufacturing, although all jobs may follow the same routing, the jobs will be differentiated at the photolithographic operations. The photolitho-graphic process establishes patterns upon the silicon wafers where the patterns differ according to the mask that is used. The flow shop that we consider has another important feature, namely the job routing is such that a job may return one or more times to any facility. We say that when a job returns to a facility it reenters the flow at that facility, and consequently we call the shop a re-entrant flow shop. In integrated circuit manufacturing, a particular integrated circuit will return several times to the photolithographic process in order to place several layers of patterns on the wafer. Similarly, in a flexible machining system, a job may have to return to a particular station several times for additional metal-cutting operations. These re-entrant flow shops are usually operated and scheduled as general job shops, ignoring the inherent structure of the shop flow. Viewing such shops as job shops means using myopic scheduling rules to sequence jobs at each facility and usually requires large queues of work-in-process inventory in order to maintain high facility utilization, but at the expense of long throughput times. In this paper we develop a cyclic scheduling method that takes advantage of the flow character of the process. The cycle period is the inverse of the desired production rate (jobs per day). The cyclic schedule is predicated upon the requirement that during each cycle the shop should perform all of the tasks required to complete a job, although possibly on different jobs. In other words, during a cycle period we require each facility to do each task assigned to it exactly once. With this requirement, a cyclic schedule is just the sequencing and timing on each facility of all of the tasks that that facility must perform during each cycle period. This cyclic schedule is to be repeated by each facility each cycle period. The determination of the best cyclic schedule is a very difficult combinatorial optimization problem that we cannot solve optimally for actual operations. Rather, we present a computerized heuristic procedure that seems very effective at producing good schedules. We have found that the throughput time of these schedules is much less than that achievable with myopic sequencing rules as used in a job shop. We are attempting to implement the scheduling system at an integrated circuit fabrication facility.