楊田芳　李孟凱　王叢

摘 要：動車組運用所是負(fù)責(zé)對動車進(jìn)行檢修、養(yǎng)護(hù)等工作的場所，全國已有超過50個動車運用所。動車組的檢修根據(jù)行駛情況被劃分成不同檢修等級，不同等級對應(yīng)不同的工序。在這里我們引用計算機進(jìn)程中的PV操作，通過Python來實現(xiàn)，S在本題目中即為可提供檢修服務(wù)的車間資源數(shù)量。來解決并發(fā)進(jìn)程間互斥和同步關(guān)系，調(diào)配資源之間的合理利用。當(dāng)同一種維修資源被耗盡時，需要這種資源的工序不得不進(jìn)入阻塞階段，此時，表示有些進(jìn)程正在等待該資源，因此要喚醒一個阻塞狀態(tài)的進(jìn)程，即直到有其他競爭對手釋放足夠的資源，此時工序才可以從阻塞中恢復(fù)，進(jìn)入就緒階段。

關(guān)鍵詞：動車組檢修;PV操作;資源配置;Python

1 問題描述

如表1所示，不同類型的動車組每個工序需要花費的時間是不一樣的。請根據(jù)附件中附表一到達(dá)動車運用所的動車信息，計算維修完這些動車的總時間。

2 問題分析

車輛檢修資源有限，動車與動車之間構(gòu)成了對于維修車間的競爭互斥關(guān)系，每輛動車，都擁有自己的檢修狀態(tài)，以及車輛型號，所以在檢修方案規(guī)劃時，情況復(fù)雜，常規(guī)方法難以解決。此時我們從問題中抽象出單個動車的自動狀態(tài)機，將每個動車狀態(tài)劃分為，就緒，維修（運行），與阻塞狀態(tài)，但是問題假設(shè)中，不考慮車輛交換時間，所以問題可以進(jìn)一步轉(zhuǎn)化為，維修（運行）與阻塞兩個狀態(tài)。

此時提出信號量處理的PV操作方法，1962年，迪克斯特拉數(shù)學(xué)教授，設(shè)計與實現(xiàn)了一種具有多道程序運行能力的操作系統(tǒng)——THE。

在PV操作中，P代表資源占用，當(dāng)有動車進(jìn)入S維修工序之前，嘗試對S資源進(jìn)行占用操作，因為本題中，車輛對于維修車間的占用關(guān)系比較簡單，任意車輛在某一時刻只會占用一個資源，所以當(dāng)S≥1時，P操作占用資源成功，當(dāng)S=0時，P操作失敗，該動車維修陷入阻塞狀態(tài)。此時在其他的動車維修進(jìn)程中，某一個車輛完成了車輛的S檢修程序，對S資源進(jìn)行V釋放操作，S資源加1，并解除等待隊列中的一個阻塞狀態(tài)。

PV操作與常規(guī)方法相比較有限在于，在一個特定系統(tǒng)中，如果同時運行的進(jìn)程之間存在著相互制約的同步運行狀態(tài)，（例如相同時刻，不只有一個動車需要檢修），為了避免多個進(jìn)程在同一時刻在一個臨界區(qū)域中同時請求不可分割的獨立資源時，（同一車間不能同時維修兩個車輛），此時根據(jù)迪克斯特拉提出的PV同步可以化解，進(jìn)程與進(jìn)程之間的復(fù)雜關(guān)系，從而轉(zhuǎn)化為進(jìn)程與資源之間的相對簡單的占用釋放關(guān)系。

所以在此基礎(chǔ)上，我們只需要考慮，不同車輛對于某一個維修工序的排斥關(guān)系，在推廣至所有的維修工序，問題迎刃而解，當(dāng)所有動車順序完成了所有的檢修工作，問題就得到了解決。我們只需要在每個資源中記錄下這個資源維修過的車輛，便可以還原出維修方案，同時在每個動車對象中，記錄最后一次維修的結(jié)束時間，就可以得到動車完成維修的時間，與動車到達(dá)時間做差，得到維修總時長。

3 條件假設(shè)

（1）假設(shè)第一輛動車組抵達(dá)動車運用所時，所有檢修車間都是空閑的，且車間之間的轉(zhuǎn)換時間忽略不計。

（2）假設(shè)執(zhí)行PV操作時，沒有時間延誤;

（3）假設(shè)進(jìn)程實現(xiàn)的是先到先服務(wù)的系統(tǒng)操作。

4 模型建立與求解

問題2提出不同類型的動車組每個工序需要花費的時間是不一樣的。請根據(jù)附件中附表一到達(dá)動車運用所的動車信息，計算維修完這些動車的總時間。此時我們將每個動車組的維修進(jìn)程進(jìn)行綁定，通過PV操作進(jìn)行不同工序的開展工作，得到從第一輛動車組到達(dá)時間（0：16）到最后一輛動車組離開（9：17）所需要的總時間為541分鐘（9個小時零1分鐘），如表2所示：

5 結(jié)語

巧妙地利用計算機進(jìn)程中的PV操作，擺脫了傳統(tǒng)排隊模型的影響，從問題中抽象出單個動車的自動狀態(tài)機，問題可以進(jìn)一步轉(zhuǎn)化為，維修（運行）與阻塞兩個狀態(tài)這樣，我們只需要考慮，不同車輛對于某一個維修工序的排斥關(guān)系，在推廣至所有的維修工序，問題迎刃而解，當(dāng)所有動車順序完成了所有的檢修工作，問題就得到了解決。資源中記錄下這個資源維修過的車輛，同時在每個動車對象中，記錄最后一次維修的結(jié)束時間，就可以得到動車完成維修的時間。

參考文獻(xiàn)：

[1]《計算方法》科學(xué)出版社-教材[M] .2011年7月

[2]清華大學(xué)《操作系統(tǒng)》學(xué)習(xí)筆記[M].

[3]《PV操作經(jīng)典問題》簡書[Z].