調度理論是指關於“調度、調用、管理、控制”等的理論。
基本介紹
- 中文名：調度理論
- 外文名：Scheduling theory
- 類型：計算機科學
- 學科：跨學科
- 性質：理論
- 概念：關於“調度、調用、管理”的理論
發展史,調度理論,
發展史
在過去的幾十年中,人們對調度問題進行了大量的研究工作。從上個世紀50年代起,調度問題的研究就受到套用數學、運籌學、工程技術等領域科學家的重視,科學家們利用運籌學中的線性規劃、整數規劃、目標規劃、動態規劃及決策分析方法,研究並解決了一系列有代表意義的調度和最佳化問題。但是，人們普遍把Conway、Maxwell和Miller三人有關調度的研究工作作為調度理論研究的正式開始,他們3人也被人們稱為調度理論的奠基人。
從20世紀80年代初開始，人們就一直在嘗試並致力於解決實際調度問題，調度研究由理論研究轉向套用研究階段。在這樣的歷史背景下,套用人工智慧、計算智慧型和實時智慧型研究成果，解決實際調度問題的智慧型調度方法就走上了歷史的舞台。
調度理論
根據加工系統的複雜度,生產調度可以分為單機調度、Job-shop調度、Flow-shop調度、Open-shop調度、多機器並行加工(K-machineinparallel)調度等幾個基本類型。
單機調度是指所有的操作任務都在一台機器上完成，需要對任務進行最佳化排隊；Job-shop調度是最一般的調度類型，它是指由m個不同的機器加工n個有特定加工路線(順序)的工件，不同工件的工序間沒有順序約束,工序加工不能中斷；Flow-shop調度假設所有工件都在同樣的設備上加工，並有一致的加工操作和加工順序；多機器並行加工調度是指多台機器並行加工工件,而且並行加工的機器和工件都是類似的-實際的調度問題通常是上述幾種調度類型的組合。
根據最佳化準則,可以分為基於代價和性能的調度兩大類。代價包括為了實現調度方案所消耗的各種費用和所造成的損失,如運行費用、運輸費用、存儲費用和延期交貨損失等。性能主要包括設備利用率、最大完成時間、拖延加工任務的百分比等。雖然在理論分析上,大部分只注意調度的性能,但在實際生產中,通常要綜合考慮代價和性能兩方面因素。
根據生產環境的特點,可將調度分為確定性調度和隨機性調度。前者是指加工時間和其他參數是已知的、確定的量;而後者的加工時間和有關參數是隨機的變數。
根據加工任務或被加工工件的特徵,可將調度分為靜態調度和動態調度。靜態調度是指所有待安排加工的工件均處於待加工狀態,因而進行一次調度後,各作業的加工被確定,在以後的加工過程中就不再改變;動態調度是指作業依次進入待加工狀態,各種作業不斷進入系統接受加工,同時完成加工的作業又不斷離開,還要考慮作業環境中不斷出現的不可預測的動態擾動。
