关于肉制品加工的车间调度问题研究

王海玲*，严司婷



关于肉制品加工的车间调度问题研究

王海玲*，严司婷

（厦门大学嘉庚学院，福建厦门，363105）

本文将针对肉制品厂产品的加工流程进行相关工件车间调度问题研究。根据实例建立工件之间的加工工序，得出基于图论的车间调度析取图模型，然后结合拓扑算法的进行逐步求解，最后求出整个产品在加工过程中的线序关系析取图。该研究结果表明拓扑算法在求解该问题上是具有高效性以及可行性的。

析取图；拓扑算法；相关工件；车间调度

引言

近年来，中国的食品行业发展迅速，同时市场上的竞争愈发严峻，对各个食品企业而言，想要获得较为有利的市场地位是较为困难的，因此，各个企业必须从自身加以改变，使自身的实力不断提高，从而更具有竞争力。面对市场需求和顾客需求的多样化以及生产规模的大型化和生产过程的连续化，车间调度已成为食品企业生产过程中的关键瓶颈之一。

一个高效且可执行性强的作业车间调度算法的研究，在于有效地优化肉制品企业生产设备配置，缩短肉制品加工时间，提高肉制品营销利润等方面有着重要的实际应用价值。本文结合作业车间调度的理论，对目前存在的问题借助建模的方法予以解决，再结合相关的肉制品企业的具体车间问题建立了析取图模型，利用拓扑算法对其进行研究，针对装配离散型产品的特点，提出将各工序之间存在的偏序关系转化为线序关系，也就是将相关工件车间调度问题转化为经典的作业车间调度问题，以提出提高肉制品厂生产率的方法和建议。

1 析取图模型的介绍

具体建模可分为以下3个步骤：

（1）暂不考虑工序之间的关系，根据车间调度问题中的信息建立经典析取图模型。

（2）考虑两两相接的工序之间的时间问题，根据实际情况，调整其顺序。

（3）对图中的合取弧加以检验，从而对其中的环进行确定，如果存在环，则工序间的冲突也会呈现出来[1]。

2 拓扑算法的基本思想

关于拓扑算法的描述，在每一个步骤中对于所有加工的肉制品，可以分为以下5个步骤[2]。

3 研究实例介绍

表1 肉制品礼盒的加工流程表

表2 肉制品礼盒的加工流程表

4 算法在实例上的应用

图1 肉制品礼盒不考虑工序相关性的析取图

图2 肉制品礼盒的析取图

根据图2的析取图模型可以重新调整礼盒1肉制品的加工流程，具体如下表3所示。

表3 肉制品礼盒工序调整后的加工流程表

图3 肉制品礼盒不考虑工序相关性的析取图

图4 肉制品礼盒的析取图

根据图4的析取图模型可以重新调整礼盒2肉制品的加工流程，具体如下表4所示。

表4 肉制品礼盒工序调整后的加工流程表

表5 和各工序的加工时间表

表6 和各工序所需的完成时间

表7 和各工序的最近直接前趋

表8 和各工序的完成率函数

图5 线序关系析取图

图6 线序关系析取图

5 结束语

本文针对目前企业存在的问题，提出了求解相关工件的车间调度算法——拓扑算法，使用析取图模型构造出了两种不同礼盒包装的肉制品在生产过程中的机器分配情况，使得产品的加工流程更加的简洁明了。根据拓扑算法，将原本两种礼盒中的肉片、肉条、原味肉松、海苔肉松等在加工过程中各工序彼此间存在的偏序关系，最终转化为了线序关系，转变相关的思路，将相关工件车间的调度问题加以转化，从而在求解的过程中借助经典的车间调度算法[4]进行计算。但在实际的生活中，偶尔会出现紧急加单的情况，这就属于动态事件发生后的重调度，如何调整产品在加工过程中的工序能够使总体的加工时间不受太大影响，又或者是订单取消的情况，对于正处在生产流水线上的产品，应该如何调整工序能使得企业的损失降到最小，也是一个需要研究的问题。对于此类问题，可以借助改进蚁群算法[5]，通过调控存在多目标的车间问题，用甘特图进行调整工序，最终计算出其所需的最长时间[6]。

[1] 熊禾根, 李建军. 考虑工序相关性的Job Shop调度问题及其析取图模型[J]. 中国制造业信息化, 2006, 35(5): 6-9.

[2] 张淑丽, 刘胜辉. 相关工件车间调度问题的拓扑算法[J]. 计算机工程与应用, 2013, 49(3): 251-254.

[3] 朱立华, 王汝传. AOV网中全拓扑排序算法的设计及应用[J]. 微机发展, 2004, 14(12): 124-126.

[4] 刘明周, 单晖, 蒋增强. 不确定条件下车间动态重调度优化方法[J].机械工程学报, 2009, 45(10: 143-148.

[5] 黎冰, 王静, 顾幸生. 基于改进蚁群算法的多目标Job-shop动态调度[J]. 华东理工大学学报(自然科学版), 2015, 41(4): 523-258.

[6] 李峥峰. 多时间因素作业车间调度问题的研究与工程应用[D]. 华中科技大学, 2010.

Research on Job Shop Scheduling Problem with Correlative Operations

WANG Hailing*, YAN Siting

(Xiamen University Tan Kah Kee Colledge, Fujian Xiamen, 363105, China)

The article will discuss the job shop scheduling problem with correlative operations of the working process in the meat product plant by analyzing the job shop scheduling problem. According to the working procedure between the work-piece according to the example, a workshop scheduling analysis model based on graph theory is obtained, and then we can solve it by using the topology algorithm.Finally, we find out the sequence relation of the whole product in the process of processing.

The research result indicates that the topology algorithm is of high efficiency and feasibility when solving this problem.

Disjunction graph; topology algorithm; correlative operations; job shop scheduling problem

10.19551/j.cnki.issn1672-9129.2018.01.014

O157.6

A

1672-9129(2018)01-0037-03

王海玲, 严司婷. 关于肉制品加工的车间调度问题研究[J]. 数码设计, 2018, 7(1): 37-39.

WANG Hailing, YAN Siting. Research on Job Shop Scheduling Problem with Correlative Operations[J]. Peak Data Science, 2018, 7(1): 37-39.

2017-12-05；

2018-01-10。

受校级孵化项目（201512L02）和省级教改项目（FBJG20170154）资助。

王海玲，女，硕士，副教授，研究方向：图论、方程。E-mail: 19099428@qq.com