Abstract
此篇論文在探討靜態、確定性的相異性平行機臺排程問題；而totallateness及total tardiness為所選定的績效指標(performance 本研究旨在設計啟發式演算法，期能作為實務上排程決策之參考。此研究中，total lateness及total tardiness問題皆被建構為數學模式；問題之最佳解可透過此模式而獲得。total lateness 問題的最佳解可很快地獲得，因此各演算法將與最佳解作比較；而total tardiness問題由於最佳解求解時間過長，啟發式演算法之好壞則藉由比較各演算法績效。我們所設計之啟發式演算法分兩個部份： 資源分配及工件加工順序之決定。第一個部份分兩個步驟進行：建立起始工件加工順序及分配工件。分配工件時，除了依據起始工件加工順序，我們建議以兩種指標作不同的考量：一為平衡機臺之工作負荷；或者以工件本身之績效指標為依據。在資源分配之後，所設計之啟發式演算法即進入第二個部份。對於 total lateness 問題，我們採用 SPT 法來決定最後的加工順序；而對於 total tardiness問題，則採用 TPI 法來決定最後的加工順序。 由實驗結果發現，在資源分配部份中，以工件本身之績效指標為依據來分派工件可得到較佳之排程結果。In this paper, we propose several heuristics to scheduleindependent jobs in unrelated parallel machine systems. Welimit our scope to the static and deterministic problem. Thesystem we investigate consists of several different types ofmachines, and machines of different types are unrelated andmachines of the same type are identical. Both the totallateness and total tardiness problem in this thesis areformulated into mathematical programming models. Nevertheless,an optimal solution may not be available; and in practice, allthat is required may be just a near-optimal solution. Theproposed heuristics contain two phases: The first phase is toallocate jobs onto machines or subsystems. The second phase isto sequence the jobs on each machine or in each subsystem. Thefirst phase consists of two stages: the constructing stage andthe allocating stage. The constructing stage is to construct aninitial job list which is used as reference to allocate jobs.The allocating stage is to allocate jobs onto machines orsubsystems by balancing machine workload or by the criteriontaking performacne measure directly into account. The secondstage is composed of the sequencing stage which determine thefinal processing order of jobs on each machine. For the totallateness problem, the SPT rule is adopted to determine thefinal job sequence; for the total tardiness problem, the TPIrule is adopted in this stage.