一個工作排程問題

Abstract

本論文所探討的是有關工程排程(Task Scheduling )的問題。工程排程問題在日常生 活中經常碰到，諸如：工廠的作業流程規劃、多處理機系統(Multiprocessor system )處理機分配……等等。此類問題的著眼點主要是在於工作執行所需時間的長短或投 入經費的多寡，期望能藉著良好的規劃，使此二方面都能儘量減縮到最小程度。 我們這□將探討工作排程問題的一類特例，即（１）處理機個數為無限多（２）每件 工件所需處理時間是可因投資多寡而變動的（３）各件工作時間的執行先後之限制條 件構成一個多入單出樹狀圖(intree)。此論文的目的就是要針對此類問題，找出在限 定花費範圍內，使得工作完成時間能減至最小的方法(algorithm )，其計算時間(com plexity)與工作件數的平方成正比(ie.O(N ))。 未來展望：希望能將研究的範圍推廣至執行先後限制圖為一般部分列圖(grneral par tial order graph )的情況上，有俾能更有效解決較多較的此類問題。