運籌學指派問題

前言：想要寫出一篇令人眼前一亮的文章嗎？我們特意為您整理了5篇運籌學指派問題范文，相信會為您的寫作帶來幫助，發現更多的寫作思路和靈感。

運籌學指派問題范文第1篇

關鍵詞：運籌學；空中交通管理；應用

0. 引言

運籌學是一門應用性的實用科學，是用多種數學工具及邏輯判斷方法來對系統中的人、財、物的組織管理及籌劃調度等問題進行研究的一種管理學科，它能有效的對管理系統中的各種資源進行科學的規劃與安排，并為相關決策者提供有價值的參考依據，有力促進效益最佳化的實現[1]。對于空中交通管理而言，能夠運用到空中交通管理中的運籌學知識有很多，包括線性規劃、整數規劃、非線性規劃、動態規劃、排隊論、網絡分析以及對策論等等，而在這其中，運籌學內容中的線性規劃以及整數規劃中的等很多課程內容的設計都與空中交通實踐過程不謀而合，能有力的起到提升空中交通管理安全性及管理效率的作用，因而對其在在空中交通管理中的應用做出仔細探究則顯得尤為迫切與重要，現分析如下：

1. 在空中交通管理中線性規劃的應用

1.1機場空側容量評估優化中線性規劃的應用

完善的機場空側的容量評估體系能對機場航班的有效安排起到重要促進作用。一般情況下機場空側容量評估體系主要由滑行道系統、停機坪系統以及跑道體統等三部分內容構成，而對這三方面不同內容的評估目的也有所差異，即依次為改良滑行道的路徑、對停機位指派進行優化以及進港先服務、離港優先隔。將機場空側容量評估的模型轉化為多目標線性規劃后，其目標函數則為經濟成本函數與延誤時間函數，約束條件既通過進港以及離港定位點的設定，來轉化成節點的流量控制[2]。

1.2地面等待問題中線性規劃的應用

統籌學中線性規劃在地面等待問題的應用中一般情況下需要通過以下三個步驟才能進行有效解決。首先就是對影響地面等待的各個因素進行科學、仔細的分析，并確定出決策中的變量因素。其次就是將問題的解決的目的加以明確和定位，同時緊密結合決策變量來對目標函數進行確定。最后就是以機場的運行限制為重要依據，來決定約束的條件。通過以上三個步驟我們便可以將地面等待問題有效轉換成線性規劃問題，而在其中目標函數則是綜合飛機延誤時間的最小化，約束條件則包括機場在容量方面的約束、航班的到達約束、單位時間內機場的最大起駕次以及飛機起飛時間與次數方面連續性的約束。

2. 在空中交通管理中整數規劃的應用

2.1整數規劃在機位分配中的應用

整數規劃除了在限制方面不同于線性規劃外，其在原理、操作流程以及模型上都與線性規劃在空中交通管理中的應用大體相似。在整數模型建立之后，運用單純性的方法以及計算機的計算軟件來進行求解，以促進機位分配最優化的實現，同時，在建立機位分配模型時，所選取的目標函數即為旅客轉機路程最優、機位空閑時間均衡、航班等待延誤時間最小等，其中可以將機位空閑時間均衡與航班等待延誤時間進行整體的規劃，使得機位分配模型將旅客與地面服務人員異動距離的最小化作為目標。其中決策參數即為機位作業時間以及機位最小間隔時間[3]。

2.2整數規劃在機位分配中的流程設置

將實時調配的流程設計應用于機場機位的分配中，能夠有效的提升機位分配的有效性。同時，在進行停機位的指派時要將機位號、機型以及所屬公司等飛機的屬性匹配問題進行充分考慮。而其主要流程一般由以下七個步驟組成：第一步 ，對航班預期到達的時間進行仔細的確認；第二步，對航班所需要調整的時間段進行科學的設定；第三步，調整進港航班集合；第四步，將集合中的航班在機位預指派中進行取消；第五步，對和航班需要調整時間段有交集的極為空閑時間進行及時的更新；第六步，運用遺傳算法對集中航班的機位進行合理的調配；第七步，以機位調配方案為重要依據，對機位空閑時間進行更新，實現調整方案的輸出。另外，在對機位指派問題中的求解過程中可以采取以下幾種方法：貪心算法、禁忌搜索算法、模擬退火算法、圖著色算法、蟻群算法（ASP）、遺傳算法以及Memet-ic 算法，同時，還可以對其中若干個算法進行組合來進行求解[4]。

3. 結語

總而言之，運籌學作為一門利用數學方法來解決生產、管理問題的重要學科，對于空中交通管理效率的提升而言，有著十分重要的戰略指導意義。為此，相關管理人員應當加大對運籌學的學習與研究力度，并將運籌學有效應用于空中交通管理中，唯有如此，才能進一步促進公眾交通管理在安全性與效益性方面的有效增長。

參考文獻

[1]石文先，朱新平. 智慧空中交通管理系統及其應用[J]. 南京航空航天大學學報（社會科學版），2013（03）

[2]萬健，李楠，李琦. 空中交通管理系統安全評價研究[J]. 北京航空航天大學學報（社會科學版），2013（01）

運籌學指派問題范文第2篇

【關鍵詞】運籌學；交通運輸管理；實際

隨著科技和社會的不斷發展，運籌學作為一門以解決實際問題為主的學科，已經滲入到了很多領域上，尤其是在農業、工業和社會生活中被人們廣泛的應用。在進行運籌學的教學中，雖然它屬于軟科學的中的一種，只是通過理論知識進行研究，但是由于它存在比較強的邏輯思維，在人們學習形成了很大的阻礙。運籌學是系統工程學和現代管理學中的一種基礎理論和不可缺少的方法和手段，目前運籌學已被應用到各個管理行業中，對我國現代化的社會建設有著十分重要的作用。

1.運籌學概論

運籌學又被稱之為作業研究，是指以應用數學和形式科學的跨領域研究，利用像是統計學、數學模型和算法等方法，去尋找復雜問題中的最佳或近似最佳的解答。它經常用于解答生活中的各種復雜的問題，幫助人們在生活中找到一個屬于自己的答案。對于運籌學知識的研究我們主要采用的實分析、矩陣論等方法進行研究，以便挖掘更多的知識。

我們在運用運籌學在處理各種不同的問題時，一般都是采用確定目標、制定方案、建立模型、制定解法這四個方面入手，運用科學的理論來分析問題的實質，這樣的處理方案，把復雜的問題瞬間簡單化，從而方便人們的解決。所以正是由于，在解決問題是有著系統、全面的分析方法，我們才在各個方面，廣泛的運用運籌學。而且在學習中，也有著許多專業和運籌學密不可分，例如應用數學、工業工程、計算機技術等都和運籌學有著密切的聯系。

在我國古代，運籌學就開始運用在人們的社會中，但是當時卻少一種比較系統全面的分析，人們只能把運籌學通過一種思想傳遞的方式，在社會中進行運用和傳播。當時人們對于運籌學的理解還比較片面，而且涉及范圍也比較狹窄，主要就是運用在戰爭中而對于運籌學的真正發展，那還是在20世紀40年代，那時候運籌學的思想主要是英國和美國提出并用于社會的發展當中，而真正引入我國的時候，是20世紀50年代末。對當時來說這些先進的思想是我國社會主義發展所需要的，因此在通過科學家們的努力下，現在已經建立了一個系統全面的運籌體系，對社會的發展和經濟的建設有著重要的意義。

2.運籌學的特點

對運籌學特點的分析，是運籌學發展、前進和開展新思想的唯一方法。目前我們歸納的特點有以下幾點：

2.1主要使用數學方法

運籌學在教學和與數學有著密切的聯系，在人們對運籌學進行學習時我們不僅要求人們要有比較強的邏輯思維，還要有著一定的數學基礎。在對運籌學進行定義的時候，我們就把數學方案作為協助運籌學發展的一件工具。而且這門應用科學在實際操作中也需要，許多數學提供的信息和技巧，才能使其發揮出最大的效率。

2.2以優化思想為核心

運籌學主要就是以最簡單的方法對實際科學，做出最優化的判斷，以最優化的方法，來解決人們生活中的問題，這樣往往會使得人們在社會中得到最大的收益。由于運籌學以這樣的思想為核心，因此這就讓運籌學形成了一門獨特而又嚴謹的科學。

2.3多學科交叉

運籌學思想廣泛解決不同學科領域的問題。解決實際中提出的決策問題，為決策者選擇理想方案提供科學依據，同時它綜合運用心理學、經濟學、化學、物理學、計算機科學和工程技術等學科的理論及方法。既提供量化因素，也進行定性分析，最終能向決策者提供建設性意見，并收到實效。

2.4 應用性

我國在1956年曾用過“運用學”的名詞，到1957年正式定名為運籌學。不管是最初僅應用在軍事上，還是到最后應用到社會經濟等各個領域，運籌學都是扮演著“工具”的角色。運籌學既對各種經營進行創造性的科學研究，又涉及到組織的實際管理問題，它具有很強的實踐性。運籌學從來自于企業和生活的實際案例出發，了解事實，理清問題結構，對問題進行量化，建立數學模型，運用運籌學軟件求解，最終服務于實際生活。

2.5多分支性

運籌學經過半個多世紀的發展，已經成為具有堅實的理論基礎，完善的結構體系，嚴謹的科學方法的學科。并已有眾多分支學科，包括數學規劃、圖論與網絡、排隊論、存貯淪、決策論、對策論、設備維修更新理論、搜索論、可靠性理論等。而且每一個分支在實際生活中已經滲透多個領域，得到廣泛使用。

3.運籌學在交通運輸中的理論體現及應用

3.1教學規劃論

數學規劃論可以處理成千上萬個約束條件和變量的大規模線性規劃問題。研究內容與生產活動中有限資源的分配有關，在組織生產的經營管理活動中，具有極為重要的地位和作用。包括線性規劃、整數規劃、動態規劃、應用規劃、目標規劃等。從解決技術問題的最優化，到工業、農業、商業、交通運輸業以及決策分析部門都可以發揮作用。具有適應性強，應用面廣，計算技術比較簡便的特點。具體地講，線性規劃可解決交通運輸系統中物資調運、配送和人員分派等問題。我國曾經利用線性規劃理論進行水泥、糧食和鋼材的合理調運，取得了較好的經濟效益；動態規劃可用來解決諸如最優運輸路徑、資源分配、運輸凋度、庫存控制、設備更新等同題；應用規劃論典型的例子就是“運輸問題”，即將數量和單位運價都是給定的某種物資從供應站運送到消費站，在滿足供銷平衡的同時。定出流量與流向，達到總運輸成本最小。應用規劃論還可以解決運輸系統中合理選址、車輛調度、貨物配裝、物流資源（人員或設備）指派、投資分配等問題。

3.2圖論

圖論是一個古老的但又十分活躍的分支，在物流中的應用非常顯著。其中最明顯的應用體現在運輸問題，比如城市間的物資調運、車輛調度時運輸路線的選擇等。運用了圖論中的最小生成樹、最短路、最大流、最小費用等知識，可求得運輸所需時間最少、路線最短、費用最省的路線等一系列實際問題。另外，運用圖論的知識繪制鐵路運輸系統線路圖、公路網的設計和分析、市內公共汽車路線的選擇和行車時刻表的安排、出租汽車的詞度和停車場的設立等，可輔助決策者進行最優的安排。

3.3排隊論

排隊論主要研究各種系統的排隊隊長、等待時間和服務等參數，解決系統服務設施和服務水平之問的平衡問題。以較低的投入求得更好的服務?，F實生活中排隊現象普遍存在，如運輸站車輛進出站的排隊，商店顧客排隊付款、客服中心顧客電話排隊等待服務等。交通領域中也有多見。在高速公路收費站服務臺的設計與管理中運用排隊論進行定量分析，運用排隊論知識對其進行優化和設計，并建立速公路收費站服務臺與工作人員的配備模型，對避免盲目確定收費亭建設規模大小，提高收費站服務臺的服務和管理水平，降低運營成本等方面發揮重要作用。

3.4對策論

對策論是一種定量分析方法，可以幫助我們尋找最佳的競爭策略。以便戰勝對手或者減少損失。在市場經濟條件下，交通行業也充滿了競爭。例如在一個城市內有兩個配送中心經營相同的業務，為了爭奪市場份額，雙方都有多個策略可供選擇，可以運用對策論進行分析，尋求最佳策略。又如，某一地區，汽車運輸公司要與鐵路系統爭奪客源，有多種策略可供選擇，也可用對策論研究競爭方案，最終獲得利益的最大化。對策論可以在競爭性定價、新服務的推出、銷售計劃的制定、加強廣告與宣傳、新設備的引入等方面發揮作用。

運籌學指派問題范文第3篇

關鍵字：運籌學；企業管理

運籌學問題和運籌思想可以追溯到古代，它和人類實踐活動的各種決策并存。現在普遍認為，運籌學是近代應用數學的一個分支，主要是將生產、管理等事件中出現的一些帶有普遍性的運籌問題加以提煉，然后利用數學方法進行解決。界定運籌學作為在科學界的一門獨立學科的出現，應當說是在1951年，即P.M.Morse和G.E.Kimball的專著“運籌學方法”出版的那一年。運籌學的思想貫穿了企業管理的始終，運籌學對各種決策方案進行科學評估，為管理決策服務，使得企業管理者更有效合理地利用有限資源。優勝劣汰，適者生存，這是自然界的生存法則，也是企業的生存法則。只有那些能夠成功地應付環境挑戰的企業，才是得以繼續生存和發展的企業。作為企業的管理者，把握并運用好運籌學的理念定會取得“運籌帷幄之中，決勝千里之外”之功效。

一、企業發展原則與戰略管理

企業戰略管理是企業在宏觀層次通過分析、預測、規劃、控制等手段，充分利用本企業的人、財、物等資源，以達到優化管理，提高經濟效益的目的。隨著我國經濟市場化的日益加深，市場競爭日趨激烈，我國企業面臨著更多的環境因素的影響與沖擊。企業要求得生存與發展，必須運籌帷幄，長遠謀劃，根據自身的資源來制定最優的經營戰略，以戰略統攬全局。企業戰略過程包括，明確企業戰略目標，制定戰略規劃，作出和執行戰略決策，并最后對戰略作出評價。企業戰略管理作為企業管理形態的一種創新，應是以市場為導向的管理、是有關企業發展方向的管理、是面向未來的管理、是尋求內資源與外資源相協調的管理、是尋找企業的長期發展為目的。也就是將企業看作一個系統，來尋求系統內外的資源合理分配與優化，這正體現了運籌學的思想。我國企業戰略管理的內容應根據自己的國情，制定對應的戰略。主要側重規定企業使命、分析戰略環境、制定戰略目標。中國現在絕大部分商品已由賣方市場轉為買方市場，知識經濟正向我們走來，全球經濟一體化的程度在加深，我國企業不僅直接參與國內市場，還將更直接面臨與世界跨國公司之間的角逐，企業間競爭的檔次和水平日益提高，因而企業將面臨更加復雜的競爭環境。只有確定了宏偉的奮斗目標，才能使企業凝集全部的力量，眾志成城，向一個共同方向努力，爭取實現有限資源的最有效的利用。顯然，運籌學理念的作用舉足輕重。

二、企業生產計劃與市場營銷

1、生產計劃。使用運籌學方法從總體上確定適應需求的生產、貯存和勞動力安排等計劃，以謀求最大的利潤或最小的成本，運籌學主要用線性規劃、整數規劃以及模擬方法來解決此類問題。線性規劃問題的數學模型是指求一組滿足一個線性方程組（或線性不等式組，或線性方程與線性不等式混合組）的非負變量，使這組變量的一個線性函數達到最大值或最小值的數學表達式.

建立數學模型的一般步驟：

（1）確定決策變量（有非負約束）；對于一個企業來說，一般是直生產某產品的計劃數量。

（2）寫出目標函數（求最大值或最小值）確定一個目標函數；

（3）寫出約束條件（由等式或不等式組成）.約束條件包括指標約束需求約束、資源約束等；

（4）最后根據目標函數為作出最合適的企業生產計劃決策。

2、市場營銷。一個市場研究專家試圖用數據證明消費者的洞察多么有意義，而一個戰略管理咨詢專家則強調成功營銷案例中隱藏的思路更有價值。我認為市場營銷管理的任務主要是探查決策環境，進行數據和信息的搜集、加工、分析，確定影響決策的因素或條件。因此，在確定目標階段實際上包含了問題識別和問題診斷兩個內容。在設計方案階段要理解問題，建立模型，進行模擬，并獲得結論，提供各種可供選擇的方案（方案主要通過對產品、價格、銷售渠道、促銷等基本環境的控制來影響消費需求的水平、時機和構成）。評價方案階段要根據確定的決策準則，從可行方案中選擇出最優或滿意的方案。這些都都可以使用運籌學的理念來為管理者提供輔助決策。三、企業庫存管理與運輸問題

1、庫存管理。如果說生產計劃是從信息流的角度指揮、控制生產系統的運行，那么庫存的管理則是從物質流的角度來指揮和控制。庫存管理的目標是如何最有效的利用企業的物質資源的問題。

由于庫存的物質屬性，因此對生產系統的日常運行具有更直接的作用，庫存是指處于存儲狀態的物品或商品。庫存具有整合需求和供給，維持各項活動順暢進行的功能。而庫存的存在又意味著占用資金、面積、資源，這種矛盾的處境導致了庫存管理的必要性與難度?，F在流行的庫存管理系統的庫存管理軟件，一般含貨品進貨、出貨管理系統，倉庫管理系統，報表系統等子模塊等，運用的原理還是運籌學模型。

2、運輸問題。在企業管理中經常出現運輸范疇內的問題，例如，工廠的原材料從倉庫運往各個生產車間，各個生產車間的產成品又分別運到成品倉庫。這種運輸活動一般都有若干個發貨地點（產地）、又有若干個收貨地點（銷地）；各產地有一定的可供貨量（產量）；各銷地各有一定的需求量（銷量）；運輸問題的實質就是如何組織調運，才能滿足各地地需求，又使總的運輸費用（公里數、時間等）達到最小。運輸模型是線性規劃的一種特殊模型。這模型不僅實用于實際物料的運輸問題，還實用于其它方面：新建廠址的選擇、短缺資源的分配問題、生產調度問題等。

四、企業人事管理與財務管理

1、人事管理。隨著知識經濟的到來，現代企業的競爭已經變成人才的競爭。知識經濟條件下，經濟發展中的知識含量高，對過去一直貫穿和滲透于農業和工業經濟中的知識的作用就凸顯得日益突出，知識經濟時代的到來，是知識成為社會的主要財富，知識和信息逐步成為與人力、資金并列的企業第三大“戰略資源”。因此，人力資源的競爭已成為企業間競爭的焦點。所以企業應根據自身的特點和發展狀況，應該建立戰略導向型的人力資源管理，根據客戶總部與下屬公司不同的架構，建立對應的人力資源管理模式，最大程度地通過戰略紐帶將“分割”的人力資源管理職能整合起來，帶動企業文化、企業管理等的全面提升，以內部管理的完善獲取市場競爭中的優勢。這顯然蘊涵的是運籌學的理念。還可以用指派問題對人員合理分配；用層次分析方法可以確定一個人才評價體系等。

2、財務管理。運籌學的理念在財務與會計中顯得更為突出也就是說它解決企業如何最有效的利用資金資源的問題。其涉及到投資決策分析、成本核算分析、證券管理等。在投資決策分析中，企業如何利用剩余資金，如何投資往往有多種方案。而運籌學的作用就是要要對這些不同的投資方案進行決策，以確定最優的方案，使得企業的收益最大。通常是利用線性規劃模型、決策論來進行判斷。

參考文獻：

[1]曹敬東，“管理科學之運籌學在企業中的應用初探”，科技資訊，2007（2).

運籌學指派問題范文第4篇

【關鍵詞】整數規劃 選課模型 最優解

1．整數規劃原理。在整數規劃中，為了滿足整數的要求，初看起來似乎只要把已得的非整數解舍入化整就可以了。實際上化整后的數不見得是可行解和最優解，所以應該有特殊的方法來求解整數規劃。在整數規劃中，如果所有變量都限制為整數，則稱為純整數規劃；如果僅一部分變量限制為整數，則稱為混合整數規劃。整數規劃的一種特殊情形是0－1規劃，它的變數僅限于0或1。0－1規劃在整數規劃中占有重要地位，可以解決許多實際問題，例如指派問題、選地問題、送貨問題等等。

0－1整數規劃的一般模型是：

2．課程優選模型的建立。

2．1 問題的提出?，F在，多數高校采取的都是學分制，大學課程是按學分值進行設置的，大學生學費主要依據按學分多少收取。學生可以根據自己的興趣愛好選擇自己所喜歡的課程，但是不合理的選課將造成學校資源的浪費，同時也將增加學生的選課費用。因此，合理選擇所學課程是大學生學習過程中的一個重要組成部分。能否合理優選自己的課程，不但是我們順利完成學業的關鍵，還可以為我們自己節約大筆費用，節約學校的教學資源，達到經濟合理學好知識的目的。

目前，高校所學課程類型主要有三種：必修課程、限選課程和選修課程。必修課程是必選學科，而限選課程和任選課程則可以根據個人的愛好自己決定。學生可以根據自己的實際情況和學校關于學分選擇的規定，采用適合的方法，合理優選出自己的選課計劃。我們可以借助0－1整數規劃原理建立課程優選模型來解決此問題。下面結合某高校學生的選課實例對課程優選模型予以闡述。

2．2 模型的建立。

某高校學生要求經濟合理地選擇大三下學期課程。該學期可選課程中包括必修課程共7門，總共17個學分（此7門必修課程未在文中列出）；限選課程共有14門，任選課程有15門。限選課程和任選課程的學分設置情況以及部分課程之間的關系見表1。另外，學校關于選課的相關規定如下：

①所選課程的總學分不能少于26學分；

②任選課的至少選1門；

③限選課的至少選2門；

④必選課的學分為120元/學分，限選課程為108元/學分，任選課程為98元/學分。

我們針對上述情況建立0－1整數規劃模型。具體如下：

①選取所選學分總費用最小值作為本問題的目標函數z；

②用xi表示是否選擇課程，其中，xi=1表示該課程被選擇，xi=0表示該課程未選擇；

③若選課程i時必須同時選課程j，則可以用xi-xj=0表示；

④若選課程i前先選課程j，則用 ， 表示；

⑤若兩門課程不能同時選，則用 表示。

于是，建立如下的數學規劃模型：

2．3 求解模型。用VB編程來求解上述問題，運行結果為：x3=x4=x23=x25=1，其他xi=0。即選修4門課程，課程標號分別是3，4，23，25；本學期的最低學費為2962元。

一般來說，得到一個整數規劃問題的最優解是很困難的，所以該整數規劃模型的解也不唯一。我們通過對變量的約束進行隱式枚舉的方法給出其他一些選課方案，見表2。

由于必修，限選和任選課程學分的費用不一樣。所以由表2可以得出，要使費用最低，則在滿足模型的情況下，盡量選擇費用最低的任選課程，并所選的學分不超過總選修的9個學分。在本文中所給出的所有最優的選課方案中，學費最低的為選修4個學分的限選，5個學分的任選，其總的最低學費為2962元。

3．結束語。本文利用0－1整數規劃原理建立模型解決了高校學生課程優選問題。實際上，整數規劃原理已廣泛應用于我們的生產生活當中，它不僅在工業和工程設計和科學研究方面有許多應用，而且在計算機設計、系統可靠性、編碼和經濟分析等方面也有新的應用。

參考文獻

1 焦永蘭主編.《管理運籌學》[M].北京:中國鐵道出版社, 2007

2 郭耀煌主編.《運籌學原理與方法》[M].成都:西南交通大學出版社,1994

運籌學指派問題范文第5篇

關鍵詞：不同類型機排序 與位置相關 拒絕 排序

中圖分類號：O2 文獻標識碼：A 文章編號：1674-098X（2015）07（b）-0214-02

排序問題也稱調度問題或時間表理論，是運籌學的一個分支，有特別廣闊的實際背景和應用前景。鐵路上的火車調度，公共服務問題，宇宙飛船的飛行計劃，學校課程表的制定等等，都要用到排序理論。在工業生產過程中，工件的加工時間往往依賴于工件的實際加工位置。Mosheiov[1]提出工件的實際加工時間是與工件原有加工時間和位置相關的函數，其中，給出了總時間表長，總完工時間的多項式時間算法。Gordon[2]提出工件的實際加工時間是與工件原有加工時間和位置指數相關的函數，其中，并給出了總時間表長，總完工時間的多項式時間算法。Wang等[3]研究了加工時間與開始加工時間相關的，三臺機器同順序流水作業的排序問題，目標函數為最大完工時間。Gerstl等[4]研究了工件的加工時間與位置相關的、帶有拒絕的平行機排序問題，目標函數為總完工時間。研究表明當機器的數量固定時，此問題可以轉化成指派問題。Wang等[5]研究了帶有指數學習效應和一般函數退化效應的單機排序問題，其中工件的加工時間是由工件的開始加工時間和工件的位置決定的，目標函數分別為最大完工時間和總完工時間，證明了它們是多項式時間可解的。Kuo等[6]證明了問題是多項式時間可解的，算法復雜性為。Kuo等[7]證明了在給定每臺機器加工的工件數前提下，問題是多項式時間可解的。

1 問題描述

假設有個工件，需要在臺變速處理機上被加工。在工件存在拒絕的情況下，即工件可能不被加工，但由此可能產生已定的代價。其中接受工件的個數為，拒接工件個數為，。接受工件在臺變速處理機上加工，每臺處理機的容量是一定的，分別為，且。如果工件被拒絕，則有一個懲罰費用。

工件的實際加工時間與工件的基本加工時間和其在處理機上的位置相關，即。工件的總完工時間為。該文研究帶有拒絕情況下，加工時間與位置相關的不同類型機排序問題，運用三參數表示法，表示為：

2 主要性質

假設1.在工件的加工過程中，機器無空閑。即工件在第臺處理機第個位置加工，第位置不能為空，若為空，工件必須放置在第個位置。

引理1.工件在每臺工件上的完工時間分別為：

定理1.問題存在時間復雜性為的最優算法。

證明：工件的總完工時間為：

則帶有拒絕的目標函數可化簡為：

（1）

由上式可知，這個問題可以轉化成指派問題。矩陣的行表示被加工工件，矩陣的列表示工件可能被加工的位置。矩陣包含兩塊（接受矩陣和拒絕矩陣），分別表示有個加工工件和個拒絕工件。對于一個給定向量，機器有列個位置分配。由于不知道工件被拒絕的數量，第二塊包含列，第二塊的維數為。因此，指派矩陣的總維數為。

下面，先定義矩陣的費用值。第一塊包含工件的加工時間與它們在相應機器上位置權的乘積。通過等式（1），在機器上位置的位置權：

第二塊對角線上的值為，其余均為無窮。為了方便起見，定義第二塊（也就是拒絕工件）作為第臺機器。這臺機器包含個可能排列的位置，這意味著這塊包含列，位置從到。定義的值：

它表示把工件指派在機器上位置的費用。另外，令為變量，如果工件排在機器上位置時，；否則。因此，上面討論的排序問題可以歸結為下面的指派問題：

對于一個給定的向量，當時，可能取值為。如果已知前臺機器的工件數且，那么最后一臺機器加工的工件數也唯一確定。得出分配向量的數量上界為。該過程需要重復執行所有可能的次，（）。因此，該問題要運行的總次數為。已知指派問題的算法復雜性為，因此問題存在時間復雜性為的多項式時間算法。

3 結論

該文研究帶有拒絕的不同類型機排序問題，工件的實際加工時間是與工件位置的一般函數，目標函數是極小化接受工件的排序指標與拒絕工件總懲罰之和。通過將問題轉化為指派問題，證明了問題是多項式可解的。對于其他目標函數，如最大完工時間，總誤工工件數和最大延誤時間等，也可進行研究，我們將繼續努力。

參考文獻

[1]Mosheiov G. A note on scheduling deteriorating jobs[J].Mathematical and ComputeModelling，2005， 41（8）：883-886.

[2]Gordon V S， Potts C N， Strusevich V A， et al. Single machine scheduling models with deterioration and learning： handling precedence constraints via priority generation[J].Journal of Scheduling，2008， 11（5）：357-370.

[3]WANG Jibo， WANG Mingzheng. Minimizing makespan in three-machine flow shops with deteriorating jobs[J].Comput Oper Res，2013， 40（2）：547-557.

[4]Gerstl E， Mosheiov G. Scheduling on parallel identical machines with job-rejection and position-dependent processing times[J].Inf Process Lett， 2012，112（19）：743-747.

[5]WANG Jibo， Hsu C J， Yang D L. Single-machine scheduling with effects of exponential learning and general deterioration[J].Appl Math Modell，2013，37（4）：2293-2299.