資源限制下排程之研究：考量資源回收再製作業

Abstract

本計畫之研究主題為探討資源限制下之排程問題，考慮一項未歸類為過去文獻中 相關之資源限制分類，因此是新的一項作業特性。在此特性下，每個工作必須自公共資 源區獲取一定數量之資源以啟動其作業，完成後則在產出資源返還予公共資源區；返還 之資源量可大於、小於或等於其所獲取之數量。另外，過去之研究均假設，任何工 作於完成實立即釋出其佔用之資源予後續尚未開始之工作。本計劃將資源回收再製作 業時間列入考慮，亦即必須再經由一道作業程序與作業時間之後始能釋出可再利 用之資源。規畫中，我們將探討單一機組、平行機器、平行指定機器與流線性等四種 作業環境，求取四項標準目標函數完工時間、總完工時間、延遲工作數、最大延遲之最 佳化。 本計畫之期程為三年。第一年將進行深度之文獻瀏覽與相關實務應用探討。繼之， 研究之步驟由確立問題複雜度開始，對於可在多項式時間解答之問題提出有效率之演算 法；對於無法以有效率演算法處理之潛在性較複雜問題則完成NP-hardness 證明。預期 成果包含：建構問題模式、多項式時間之問題演算法、NP-hardness 證明以及完整之複 雜度lattice 架構。第二年將發掘最佳解之性質以設計精確解演算法，包含分支與界定法 以及動態規劃法。優勢策略、刪除策略與下限值函數等之開發與設計亦是研究重點，以 做為加速分支與界定法之解題過程。最後年度之研究目標為近似解演算法，包含經驗法 則演算法、(fully) polynomial approximation schemes 以及次經驗法則演算法。如所探討 之問題存在有(F)PTAS，我們將以第二年所設計之動態規劃演算法為模本進行設計，並 分析其誤差與執行時間之關係函數。另外，對於經驗法則演算法部分，我們亦將以解析 方法探討其理論性誤差。次經驗法則之效能與效率則藉由模擬實驗進行驗證。

This project aims to extend the current cooperation of Russia and Taiwan parties to help the share and cultivate knowledge and to achieve frontier results in scheduling theory. The theme of the project is to investigate resource-constrained scheduling with separated recycling times. The main features differentiating the proposed research direction from the traditional ones include (1) a generalized resource constraint, and (2) resource recycling operations separated from normal job processing times. The second feature is especially highlighted from the environmental concerns about the reduction of e-waste and the re-use of the re-manufactured parts. This research will shed light on the recycling issues from the operations scheduling perspect. This project proposes to study scheduling problems subject to a generalized resource constraint, under which each job acquires and consumes a certain amount of resource from the common resource pool, and then reproduces and returns, at its completion, to the common pool another amount of resource which could be different from that the job already consumed. In the existing literature of resource-constrained scheduling, the resource occupied by a job under execution is to be immediately released when the processing of this job is complete. The proposed model of this project introduces separated recycling operations that are required for the system remanufacture/refurbish the used resource for the remaining unprocessed jobs. We shall investigate four configurations (or manufacturing environments): single machine, identical parallel machines, parallel dedicated machines and flow shops. Classical scheduling objective functions, including makespan, total (weighted) completion time, (weighted) number of late jobs, and maximum lateness, will be investigated. This proposal projects a three-year study horizon. Year one focuses on the literature survey and the concise formulation of the studied problems incorporating real applications. Establishing the complexity status, which indicates the subsequent research approaches to follow, is the second theme. We shall provide efficient solution algorithms for the polynomially solvable cases and give NP-hardness proofs for potentially hard problems. The results will include efficient algorithms and a concise formulation and complexity hierarchy of the studied problems. The second year is devoted to exploring optimality properties for the development of exact algorithms, including dynamic programming algorithms and branch-and-bound algorithms. Dominance and elimination rules and lower/upper bounds will be proposed to enhance the problem-solving capability of branch-and-bound algorithms. The third year will focus on approximate solutions. We shall develop heuristic, (fully) polynomial approximation schemes ((F)PTAS), and meta-heuristic algorithms. If the cases allow the existence of polynomial time approximation schemes (PTAS), we shall develop, based upon dynamic programming algorithms, approximation scheme and conduct analytical studies on their performance ratios. Error ratios associated with the proposed heuristics will be mathematically analyzed, too. Meta-heuristics will be assessed through a series of computational experiments.