關于肉制品加工的車間調度問題研究

王海玲*，嚴司婷

?

關于肉制品加工的車間調度問題研究

王海玲*，嚴司婷

（廈門大學嘉庚學院，福建廈門，363105）

本文將針對肉制品廠產品的加工流程進行相關工件車間調度問題研究。根據實例建立工件之間的加工工序，得出基于圖論的車間調度析取圖模型，然后結合拓撲算法的進行逐步求解，最后求出整個產品在加工過程中的線序關系析取圖。該研究結果表明拓撲算法在求解該問題上是具有高效性以及可行性的。

析取圖；拓撲算法；相關工件；車間調度

引言

近年來，中國的食品行業發展迅速，同時市場上的競爭愈發嚴峻，對各個食品企業而言，想要獲得較為有利的市場地位是較為困難的，因此，各個企業必須從自身加以改變，使自身的實力不斷提高，從而更具有競爭力。面對市場需求和顧客需求的多樣化以及生產規模的大型化和生產過程的連續化，車間調度已成為食品企業生產過程中的關鍵瓶頸之一。

一個高效且可執行性強的作業車間調度算法的研究，在于有效地優化肉制品企業生產設備配置，縮短肉制品加工時間，提高肉制品營銷利潤等方面有著重要的實際應用價值。本文結合作業車間調度的理論，對目前存在的問題借助建模的方法予以解決，再結合相關的肉制品企業的具體車間問題建立了析取圖模型，利用拓撲算法對其進行研究，針對裝配離散型產品的特點，提出將各工序之間存在的偏序關系轉化為線序關系，也就是將相關工件車間調度問題轉化為經典的作業車間調度問題，以提出提高肉制品廠生產率的方法和建議。

1 析取圖模型的介紹

具體建?？煞譃橐韵?個步驟：

（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