An integer linear‐programming model for machine scheduling
An integer linear‐programming model for machine scheduling
复制标题
DOI：
10.1002/nav.3800060205
复制
发表时间：
1959-06
期刊：
影响因子：
--
通讯作者：
H. M. Wagner
中科院分区：
文献类型：
--
作者：
H. M. Wagner
I.引言机器调度或排序问题：给定n个项目，每个项目将在一个或多个m机器上处理，一个项目的处理顺序是部分或全部指定的，找到机器上的项目的排序，最大限度地减少了总耗时，以完成所有项目的制造。它是假设一个项目的机器上的制造时间是指定的（即，非随机），并在过程中的库存是允许的。问题的特征。我们认为提出这个模型是有意义的，因为（1）它表明存在一个包含各种机器调度情况的单一模型，（2）线性格式建立了一个有限算法的存在，该算法单调地寻求这种排序问题的最优解，（3）尽管这个模型现在的计算兴趣非常有限，整数线性规划和有效处理”次级约束”的方法的未来发展可能使特定问题的数值解成为可能;（4）有迹象表明，有可能构造特殊算法来利用某些”经典”调度问题的结构。不用说，考虑这种方法的主要理由是Gomory [9]和其他人[5，6，11]最近发现了解决整数线性规划问题的有前途的方法;一个相关的理由是Dantzig，F 'ulkerson和约翰逊[8]在使用二次约束技术解决先验包含猛犸数量限制的问题方面取得了显著的成功。如下面将显而易见的，除了可能具有非常少的机器和有限数量的项目的情况之外，其当前形式的模型在计算上是笨拙的;在这种情况下，频繁重复的排序问题或涉及相当大的财务金额的问题可以通过本文的方法有利地解决。如上所述，我们更有希望的是，这一介绍可能会成为一个链接到一个更计算可行的公式。在第二节中，我们讨论了一个通用的模型，这是适应大量的调度情况。熟悉的排序问题[3，10，12] n个项目，其中每一个必须放置或所有m台机器，制造的顺序是机器1，机器2，...，机器m，在第三节中考虑。进一步的限制，只有三台机器，将在第四节中探讨。
I. INTRODUCTION machine-scheduling or sequencing problem: Given n items, each to be processed on one or more of m machines, the order of processing for an item being partially or entirely specified, find the sequencing of items on the machines which minimizes the total elapsed time to complete the manufacture of all items. It is assumed that the manufacturing time of an item on a machine is specified (ie, nonstochastic) and that in-process inventory is allowable. characterizing the problem. We feel it is of interest to present the model, because (1) it shows that there is a single model which encompasses a wide variety of machine-scheduling situations,(2) the linear format establishes the existence of a finite algorithm which monotonically seeks an optimum solution to such sequencing problems,(3) although the model is now of very limited computational interest, future developments in integer linear programming and methods for efficiently handling" secondary constraints" may make numerical solutions of particular problems possible, and (4) there is an indication of the possibility of constructing special algorithms' to exploit the structure of certain of the" classical" scheduling problems. Needless to say, the major justification for considering such an approach is that Gomory [9] and others [5, 6, 11] have recently discovered promising methods for solving integer linearprogramming problems; a related justification is that Dantzig, F'ulkerson, and Johnson [8] have achieved noteworthy success in using secondary constraint techniques for solving a problem which a priori contains a mammoth number of restrictions. As will be evident below, the model in its present form is computationally unwieldy except perhaps for situations with a very few machines and a limited number of items; in such cases, a frequently recurring sequencing problem ox one involving a considerable financial sum might profitably be solved by the method herein. We are more hopeful, as stated above, that this presentation might serve as a link to a more computationally feasible formulation. In Section II we discuss a general model which is adaptable to a large number of scheduling situations. The familiar problem [3, 10, 12] of sequencing n items, each of which must be placed OR all m machines, the order of manufacturing being machine 1, machine 2,..., machine m, is considered in Section III. The further restriction, to three machines only, is explored in Section IV.