具工件釋放時間限制下最小化提早與延遲成本之單機排程問題; Single machine scheduling to minimize job-dependent weighted earliness and tardiness penalties with distinct release dates

NCU Institutional Repository > 管理學院 > 工業管理研究所 > 博碩士論文 > Item 987654321/11169

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/11169

題名:	具工件釋放時間限制下最小化提早與延遲成本之單機排程問題;Single machine scheduling to minimize job-dependent weighted earliness and tardiness penalties with distinct release dates
作者:	羅久哲;Jeou-jer Luo
貢獻者:	工業管理研究所
關鍵詞:	提早成本;優先法則;分枝定界法;延遲成本;branch-and-bound;dominance rule;tardiness;earliness
日期:	2005-06-30
上傳時間:	2009-09-22 14:15:28 (UTC+8)
出版者:	國立中央大學圖書館
摘要:	我們考慮在具有工件釋放時限制下最小化提早與延遲成本之單機排程問題。此問題為單一機台、n 的工件，此機台一次只能針對一個工件偍供服務，而工件在被服務的過程中，不因其他因素而中斷。在我們的問題中，每一個工件有不同的釋放時間，此釋放時間代表工件進入機台等待加工的時間點，只有在此時間點或此時間點之後，工件才可進行加工。所有的工作有一個相同的到期日，在到期日之前完工，會造成提早完工成本；在到期日之後完工，會造成延遲成本。目的是找到一個提早時間與延遲時間最小的最佳解。針對此問題，我們利用分枝定界法(Branch-and-Bound)來找尋最佳解，並提出適用於此問題的分枝法則與定界法則。在實驗的部份，主要針對我們所建構的分枝定界法進行正確性的驗證與效率性的評估。我們利用窮舉法與特例來驗證演算法的正確性。而效率評估的部分，窮舉法與我們所提出之演算法進行比較。根據實驗結果平均顯示，我們所提出演算法可有效地刪除超過99%的點。 We consider a single machine scheduling problem to minimize job-dependent weighted earliness and tardiness penalties with distinct release dates. Each of n jobs is to be processed without interruption on a single machine which can handle only one job at a time. In our problem, each job becomes available for processing at its release date. All jobs have common due date and each job has different weights for earliness and tardiness. The objective is to find an optimal schedule that minimizes the sum of job-dependent earliness and job-dependent tardiness. For this problem, a branch-and-Bound Algorithm is proposed to find an optimal schedule in this article, and some propositions are used to eliminate a large of infeasible solutions. Computational experiments are proposed to validate and evaluate our algorithm. In validation, a special case and enumeration are compared with our algorithm. In evaluation, we compare effectiveness between our algorithm and enumeration. In average, more than 99% of nodes are eliminated in test problems.
顯示於類別:	[工業管理研究所 ] 博碩士論文

文件中的檔案:

檔案	大小	格式	瀏覽次數

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....