用于手动操作机器的产品线电池中操作工分配和排序的启发式方法

Sekar Vembu 和G.Srinivasan

摘要

本文解决了生产不同品种产品的产品线中操作工分配和排序问题。 线被分成单元体，使得单元体内存在单一的运动，单元体之间的批量生产。 假设运营商是多单元，并在单元中的所有机器上处理零件，将它们从一台机器运送到另一台机器。 分配给单元的操作员数量可以小于机器数量，生产批次的时间取决于操作员分配。 开发用于操作员分配和排序作业的算法以最小化制造的算法

1.简介

制造系统是组织工厂资源以有效地将原材料转化成成品的方式。 制造系统可分为连续或大规模生产，间歇或批量生产和加工生产。 蜂窝制造系统（CMS）结合了批量生产在批量生产中的优势。 在这里，机器组以这样的方式形成，每个组理想地处理一系列零件或组件[1]。

即时（JIT）是在所需时间内以正确数量制造零件的理念。 JIT的目标之一是将任何生产阶段的库存降至零[2]。 这里，零件是分批生产的。 如果从一个零件品种到另一个品种的时间变化较小，则JIT可以非常有效地应用。 通过形成产品线单元体[2]，其中材料在单元体之间分批移动，并在单元体内单个片段中实现即时制备单元体的方法之一。

在产品线单元中调度各种作业是流程车间调度问题，为此已经开发了几个优化程序。 这些不适合于在合理的计算时间内解决大型问题，从而需要启发式的发展。

Johnson [3]最佳地解决了两台机器流程车间问题，以最大限度地减少制造成本。 Campbell等人提出了一种基于约翰逊算法解决一般问题的启发式方法。 （CDS算法）[4]。 Stinson和Smith [5]提出了一种解决排序问题作为旅行推销员问题（TSP）的方法。 Nawaz等人 [6]提出了一种通过可用部分序列中的作业插入来开发调度的算法（NEH算法）。 Osman和Potts [7]提出了一种模拟退火算法，Reeves [8]开发了一种遗传算法（GA）来解决排列流车间排序问题。 吉田和瞳[9]和Sirkar和Ghosh [10]已经解决了具有序列依赖建立时间的流程车间调度问题。

单元体调度问题已经由Hitomi和Ham [11]解决。 Vakharia和Chang [12]修改了流动商店启发式，即用于调度流水线制造单元中部件系列的CDS和NEH算法。 Park和Steudel [13]在单个流水线工作单元中为作业排序提出了启发式方法，处理类似的部分，其中建立时间与处理时间分开。 它们假设机器之间有限的缓冲区和单元件中的单件材料运动。

大多数调度模型假设可用的运算符数量等于产品线中的机器数量。 但实际上有些操作员比机器少的情况。 Chen [14]解决了操作员处理多台机器的问题。 他提出了将单元中运算符执行的操作排序为混合整数程序（MIP）的问题，以找到对应于最小制作时间的循环运算符行走模式。

Schonberger I15]表示，通过在低频率下放置更多的小尺寸订单可以实现更多的订单，从而可以实现更大规模的订单。 在批量生产环境中，转移批次尺寸尽可能小，以便工件在制程中是最小的。 当操作员进行多功能化并在单元格中从一台机器到另一台机器工作时，实现批量大小[2]。

本文介绍了操作员分配和排序工序在手动操作机器产品线中的组合问题，并结合了JIT生产原理。 由于分配给单元格的运算符数量是一个变量，所以批次的顺序取决于运算符分配。

2.问题环境

问题假设如下。 有K个单元体（在产品线）和M个作业（品种的产品）。 所有的工作以相同的顺序访问所有的单元格。 每个电池都有两台或更多台机器。 在一个单元格中，一个作业可以跳过一个机器，但是具有单向流。 从一个作业（品种）到另一个作业（品种），随时间推移有显着的序列依赖性变化 操作员在单元中的所有机器上工作，并将零件从一台机器运送到另一台机器。 机器之间的行走时间包括在处理时间内。 每个工作种类的需求和可用的运营商总数（N）是已知的。

在JIT系统中，每个品种都以小批量生产。 理想的情况是批量大小为1，但由于转换时间较长，通常情况下不可行。 在本文中，我们模拟了所有品种的多个小批量生产以实现库存减少的好处的情况。

3.操作员分配问题

考虑一个4台机器处理一批零件的电池。在四台机器上分别处理3,3和4分钟。使用一个操作员，电池可以每12分钟一次。如果有两个操作员，第一个操作员可以在第一个操作员在第一台机器上完成操作后立即开始处理。前四个部分完成的时间分别为12,16,24和28分钟。如果我们有三个运营商，那么前五个部分的完成时间分别是12,16,20,24和28分钟。如果单元中有四个操作符，则前五个部分完成的时间是12,16,20,24和28分钟。我们观察到，即使员工人数从3人增加到4人，产出率并没有增加。这是因为我们已经达到了三名工人的最高生产率（这是瓶颈机的时间）。这个数字是所有机器上的处理时间之和与瓶颈机处理时间的比值。这也标识了单元格中获得最大输出所需的最小工作人员数。这个数字对于同一单元格中的不同工作品种而言是不同的。

3.1表达了为批生产一批工作所花费的时间

符号：

i = 1 - M: 各种工作

j = 1-K：单元体

固定参数

Di: 需求多样i

t,/: 在单元格j（在所有机器上）处理一个单位品种i的总时间

bij:在瓶颈机上的一个单位的品种i在单元格j上的时间

w0：在单元格j = hj / bo中获得品种i的最大输出所需的最小工作人数

si，j：单元体j中品种i和品种k之间的转换时间

B：批量大小

r，k〜：表示在单元格j中从一批品种i到品种k的转换的影响的数量

N：可用运营商的数量

变量

ni：分配给单元格j的运算符数

T〜j：在单元格j中产生一批品种i的时间（取决于nj）

mj：运算符初始分配给单元格j

Tij的表达式在等式（1）中给出。

该处理时间与切换时间一起用于获得批次作业的最佳顺序。

4.序列问题

本文中考虑的排序问题中的一个假设是对每个产品的需求是批量大小的倍数。 另外，第批次不得制造，直到生产了其他所有品种的n批为止。 两批同样的品种不应立即生产。 考虑到三个品种A，B和C，序列ABCBCACBC是可以接受的，而ABCABCBCC序列应避免，因为两批C一起制造。 本文提出的排序问题是找出满足上述条件的几批作业的最佳顺序，并最大限度地减少制作时间。

5.神经网络算法

上面考虑的排序问题是唯一的，因为现有的启发式方法不能直接应用，因为上一节中列出的约束。另外，单元格中批处理的时间取决于分配给单元的操作员的数量。

在本文中，运营商分配问题通过三种方法 - 启发式（H），遗传算法（G）和枚举（E）来解决。 在第一种方法（H）中，尝试对运营商分配进行四种不同的启发式（H1，H2，H3，H4），并将应用排序算法后的最佳制作时间作为启发式解（H）。

运营商分配（H1，H2，H3）的前三个启发式是基于每个小区中每个品种的瓶颈工作者的加权平均数。 第四个启发式（H4）逐渐将运算符分配给最大加载单元。

遗传算法是基于进化和自然遗传学机制的搜索方法。 遗传算法的想法首先由荷兰提出[16]，用于解决组合优化问题。 它已经成功应用于单元体形成[17]和调度[18]等各种问题。

在为运营商分配（G）开发的遗传算法中，随机生成包含初始群体的一组字符串。 然后使用适应度函数来评估每个字符串，该适应度函数以适合度值的形式给出每个解决方案串的潜力。 选择表现更好的字符串用于交配池。 遗传算子在不同的字符串之间进行遗传物质转移的过程，并产生后代。 具有可接受适应度值的后代构成新一代。 该算法持续到满足终止条件。 遗传算法通过仔细和广泛的搜索通常给出良好的接近最优解。

完整的枚举算法（E）列举了运算符分配的所有排列，将排序算法应用于每个排序算法，并选择最佳（给出最小制作时间的那个）作为解。

通过将需求除以批量大小获得每种品种的批次数。 我们考虑一个有4个品种（A，B，C和D）的情况，分别有3批A，2个B，1个C和4个D.我们定义4个“套”作业，每组包含不同的品种。 第一套将有一批品种。 待生产的剩余批次数为A，B为2，D为3，D为3。第二组A，B，D为一批。第三组A，D为一批，第四组为 只有一批D.每个集合逐步解决排序和调度问题。

由于我们假设随时间的变化是依赖于序列的，所以标准流程车间算法被修改并用于排序。 使用两种用于对批次进行排序的算法。 第一种算法（称为C）使用两种方法，最近邻域搜索来解决旅行推销员问题（TSP）和CDS方法[4]，而第二种算法（称为S）使用Stinson和Smith [5]的修改版本， 结合切换时间的算法。

第一种测序算法如下：

所有单元体的所有品种的切换时间矩阵使用最近邻域搜索作为旅行推销员问题来解决。我们获得K个序列，每个单元体一个。考虑单独的处理时间，并直接应用CDS方法来获得K-1序列。使用第一组的切换和处理时间以及选择使最小化的序列来评估如此生成的每个2K-1序列。当将算法应用于第二组时，第二组的2K-1序列中的每一个都附加到从第一组获得的最佳解，并且选择使最小化的序列。重复这个过程，直到包含所有的集合，并找到具有最小制作时间的序列。

由于制造商取决于切换时间和处理时间，所以两种算法相结合，从而可以获得两者的优点。此外，由于处理时间取决于分配的操作员的数量，所以设置与处理时间的比率成为变量。如果切换时间很长，那么TSP方法会更好一些，如果处理时间很长，则CDS方法会更好。

在第二个调度算法中，Stinson和Smith算法[5]被修改为包括切换时间。 该算法评估六个序列，并且将使得最小化的序列选择为最佳解决方案。 这对于所有的集合是如先前的算法所完成的，并且找到最佳的制作时间。

运算符分配（H，G和E）和两个排序算法（C和S）的三种方法被组合以给出用于运营商分配的总体问题的六种算法（称为HC，HS，GC，GS，EC，ES） 和测序。

5.1.算法H-C

阶段1：（次启发式H1）

步骤1.计算

步骤2.计算

步骤3. 将nj舍入到下一个最高的整数。

步骤4.如果转到步骤8

步骤5.如果转到步骤7

步骤6.识别单元格j，其中（nj-mj）是最大值，并减少nj由1.转到步骤4

步骤7.识别单元格j，其中（mj-nj）是最大值，并增加nj由1.转到步骤4

步骤8. 执行启发式C并存储makepan。 （启发式C的算法在阶段6中给出）

阶段2：（次启发式H2）

步骤1.计算

步骤2.执行子启发式HI的步骤2-8。

第3阶段:(子启发式/ - / 3）

步骤1.计算

步骤2.执行子启发式HI的步骤2-8。

第4阶段：（次启发式/ - / 4）

步骤1.使所有j的nj = 1。

步骤2.使用公式（1）计算t〜j。

步骤3.计算包含所有i的

步骤4.查找j，使得totj = max {totsj = 1 to K}。

步骤5.使nj，

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[140913]，资料为PDF文档或Word文档，PDF文档可免费转换为Word