具工件釋放時間限制下最小化提早與延遲成本之單機排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：61

、訪客IP：3.133.159.125

姓名

羅久哲(Jeou-jer Luo) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

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

相關論文

★ 以類神經網路探討晶圓測試良率預測與重測指標值之建立	★ 六標準突破性策略—企業管理議題
★ 限制驅導式在製罐產業生產管理之應用研究	★ 應用倒傳遞類神經網路於TFT-LCD G4.5代Cell廠不良問題與解決方法之研究
★ 限制驅導式生產排程在PCBA製程的運用	★ 平衡計分卡規劃與設計之研究-以海軍後勤支援指揮部修護工廠為例
★ 木製框式車身銷售數量之組合預測研究	★ 導入符合綠色產品RoHS之供應商管理-以光通訊產業L公司為例
★ 不同產品及供應商屬性對採購要求之相關性探討－以平面式觸控面板產業為例	★ 中長期產銷規劃之個案探討 -以抽絲產業為例
★ 消耗性部品存貨管理改善研究-以某邏輯測試公司之Socket Pin為例	★ 封裝廠之機台當機修復順序即時判別機制探討
★ 客戶危害限用物質規範研究-以TFT-LCD產業個案公司為例	★ PCB壓合代工業導入ISO/TS16949品質管理系統之研究-以K公司為例
★ 報價流程與價格議價之研究–以機殼產業為例	★ 產品量產前工程變更的分類機制與其可控制性探討-以某一手機產品家族為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

我們考慮在具有工件釋放時限制下最小化提早與延遲成本之單機排程問
題。此問題為單一機台、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.

關鍵字(中)

★ 提早成本
★ 優先法則
★ 分枝定界法
★ 延遲成本

關鍵字(英)

★ branch-and-bound
★ dominance rule
★ tardiness
★ earliness

論文目次

Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Background and Motivation . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Research Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Research Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.1 Research Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.2 Research Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Chapter 2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1 Earliness and Tardiness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Different Release Dates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Chapter 3 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Basic Propositions of E/T Model . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Branch-and-Bound Scheme . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3.1 Propositions used in Branching Tree . . . . . . . . . . . . . . . . . 18
3.3.2 Branch-and-Bound Algorithm . . . . . . . . . . . . . . . . . . . . . . 31
Chapter 4 Computational analysis . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1 Validation of Branch-and-bound Algorithm . . . . . . . . . . . . . 37
4.2 Evaluation of Branch-and-Bound Algorithm . . . . . . . . . . . . . 39
4.2.1 Comparing the Enumeration . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2.2 The Suitability of Algorithm Experiment . . . . . . . . . . . . . . . 41
Chapter 5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
APPENDIX A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
APPENDIX B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
APPENDIX C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

參考文獻

[1] Abdul-Razaq, T.S. and C.N. Potts (1988), “Dynamic Programming State-Space
Relaxation for single-machine scheduling,” Journal of Operational Research
Society 39, 141-152.
[2] Akturk, M.S. and D. Ozdemir (2000), “An exact approach to minimizing total
weighted tardiness with release dates,” IIE Transactions 32, 1091-1101.
[3] Asano, M. and H. Ohta (1999), “Single machine scheduling using dominance
relation to minimize earliness subject to ready and due times,” Int. J. Production
Economics 44, 35-43.
[4] Baker K.R. and G.D. Scudder (1990), “Sequencing with Earliness and Tardiness
Penalties: A Review,” Operations Research 38, 22-36.
[5] Bank, J. and F. Werner (2001), “Heuristic Algorithms for Unrelated Parallel
Machine Scheduling with a Common Due Date, Release Dates, and Linear
Earliness and Tardiness Penalties,” Mathematical and Computer Modelling 33,
363-383.
[6] Bapatiste, P., N. Carlier, and A. Jouglet (2004), “A Branch-and Bound procedure to
minimize total tardiness on one machine with arbitrary release dates,” European
Journal of operational research 158, 595-608.
[7] Belouadah, H., M.E. Ponser, and C.N. Potts (1992), “Scheduling with release dates
on single mahine to minimize total weighted completion time,” Mathematic 36,
213-231.
[8]Biskup, D. and M. Feldmann (2001), “Benchmarks for scheduling on a single
machine against restrictive and unrestrictive common due dates,” Computers &
Operations Research 28, 787-801.
[9] Cai, X., V.Y.S. Lum, and J.M.T. Chan (1997), “Scheduling about a common due date
with job-dependent asymmetric earliness and tardiness penalties,” European
Journal of Operational Research 98, 154-168.
[10] Cheng, T.C.E., Z.L. Chen (2002), and Shakhlevich, N.V., “Common due date
assignment and scheduling with ready times,” Computers & Operations
Research 29, 957–1967.
[11] Feldmann, M. and D. Biskup (2003), “Single-machine scheduling for minimizing
earliness and tardiness penalties by meta-heuristic approaches,” Computers &
Industrial Engineering 44, 307–323.
[12] Hall, N. and M. Posner (1991), “Earliness-Tardiness Scheduling Problems,Ⅰ：
Weighted deviation of completion times about a common due date,” Operations
Research 39, 836-846.
[13] Hall, N., W. Kubiak, and S.P. Sethi (1991), “Earliness-tardiness scheduling
problems,Ⅱ: Deviation of completion times about a restrictive common due
date,” Operation Research 39, 847-856.
[14] Hino, C.M., D.P. Ronconi, and A. B. Mendes (2005), “Minimizing earliness and
tardiness penalties in a single-machine problem with a common due date,”
European Journal of Operational Research 160, 190-201.
[15] Li, G. (1997), “The theory and Methodology, Single machine earliness and
tardiness scheduling,” European Journal of Operational Research 96, 546-558.
[16] Liaw, C.F. (1999), “A branch and bound algorithm for the single machine earliness
and tardiness scheduling problem,” Computer & Operations Research 26,
679-693.
[17] Mazzini R. and V. A. Armentano (2001), “A heuristic for single machine scheduling with early and tardy costs,” European Journal of Operational Research 128, 129-146
[18] Ow P. and T. Morton (1989), “The Single Machine Early-Tardy Problem,” Management Science 35, 177-191.
[19] Sheen, G.J. and W.Y. Chen (2003), “Single-Machine Scheduling to Minimize Job Dependent Earliness and Tardiness Penalties with a Given Common Due Date,” Working paper, Notional Central University, Taiwan.
[20] Valente, J.M.S. and R.A.F.S. Alves (2005), “An exact approach to early/tardy scheduling with release dates,” Computers & Operations Research 32,
2905–2917.
[21] Valente, J.M.S. and R.A.F.S. Alves (2003), “Heuristics for the early/tardy Scheduling Problem with release dates,” Working paper 130, Faculdade de Economia do Porto, Portugal.

指導教授

沈國基(Gwo-ji Sheen)

審核日期

2005-7-8

推文