物流運籌實務課程設計

題目：置換流水車間調度問題的MATLAB求解

置換流水車間調度問題的MATLAB求解

目錄

前言……………………………………………………………………… 5

問題描述………………………………………………………………… 6

算法設計………………………………………………………………… 7

實驗結果……………………………………………………………… 15

摘要

自從Johnson 1954年發表第一篇關于流水車間調度問題的文章以來．流水車間調度問題引起了許多學者的關注。安排合理有效的生產調度是生產活動能井然有序開展，生產資源得到最佳配置，運作過程簡明流暢的有力保證。流水車間調度問題是許多實際流水線生產調度問題的簡化模型。它無論是在離散制造工業還是在流程工業中都具有廣泛的應用。因此，對進行研究具有重要的理論意義和工程價值。流水線調度問題中一個非常典型的問題，而置換流水線調度問題作為FSP問題的子問題，是一個著名的組合優化問題。該問題是一個典型的NP難問題，也是生產管理的核心內容。隨著生產規模的擴大，流水線調度問題的優化對提高資源利用率的作用越來越大，因此對其研究具有重要的理論和現實意義。

關鍵字：流水車間，單件小批量生產，jsp模型，Matlab

前言

企業資源的合理配置和優化利用很大程度上體現在車間一層的生產活動中,所以加強車間層的生產計劃與控制一直在企業生產經營活動中占有十分重要的地位。車間 生產計劃與控制的核心理論是調度理論。車間調度問題是一類重要的組合優化問題。為適應訂貨式、多品種、小批量生產的需要,引進了概念。在,可以避免或大大減少、提高生產效率。因此,研究成組技術下車間調度問題是很有必要的。個工件要在臺機器上加工，每個工件有道工序，每道工序都要在不同的機器上加工，所有工件的加工順序都相同，問題的目標是確定每臺機器上工件的加工順序及開工時間，使得。，遠遠小于流水車間調度問題的規模。

本次課程實驗主要研究PFSP中的最小化最大完工時間)求解Carlier (1978)提出的8個算例、以及Reeves (1995)提出的21個算。由于三臺機器以上的調度問題被證明是NP難問題，對于大規模的調度，至今仍未出現求解最優的方法，常常采用啟發式算法來求解近優解。本案例主要采用instance car2進行求解。

案例：某產品，需要經過4道工序對13個工件進行加工，這13個工件的生產流程是一樣的。加工時間表見下：

表4-3 某產品加工時間表

12345678910111213tj178963021457321865821420778569653212457tj293021425789653214254786532112412345678tj321475320124752147532145763214257854123tj4320142753214528653514527536214528888999計算步驟如下：首先確定n/m/F/Cmax的最大完工時間為：

k=2,...,m

i=2,...,n

則 Cmax=

二、算法設計

(一)

假設工件在機器上的加工順序是相同的，同時假定各工件準備就緒，機器一開動就投入生產，開工時間為0，則最大完工時間等于最大流程時間。同時3臺機器以上的流水車間調度是NP難問題，所以本文只考慮了2臺、3臺機器的情況，解決3臺機器以上的問題方法也可運用人工智能算法，解的質量更高，但因該類算法需良好的軟件編程能力，故本文不加探究。n個工件在m臺機器上的加工順序相同。工件在機器上的加工時間是給定的。問題的目標是求n個工件在每合機器上的最大完工時間等于最大流程時間。這種流水線調度問題要在滿足以下兩個約束條件的前提下，使得加工完所有

的工件所花的時間盡可能地少：

1、工件約束

每個工件在每臺機器上恰好加工一次，每個工件在各機器上加工順序相同。不失一般性，假設各工件按機

器1至m的順序進行加工。各工件在各機器上的加工時間已知。

2、機器約束

每臺機器在任何時刻至多加工一個工件，每臺機器加工的各工件的順序相同。

置換流水線調度問題實質是如何調整加工工件的序列，提高機器的利用率的問題，即在同一時刻正在加工的機攫數越多，機器利用率越大口根據該原則，我們