臺灣博碩士論文加值系統

本研究探討可拒絕之退化性工作(件)非等效平行機台生產排程問題，研究的目標是找出可拒絕與不可拒絕的工作和不可拒絕工作的最佳安排使得機台總負荷的權重、總處理時間的權重、總工作的絕對處理時間差的權重和總工作的拒絕成本最小化，研究結果顯示：在機台個數固定下，本問題可以在多項式時間下求得最佳解。

This paper aimed to investigate the unrelated parallel-machine scheduling with deteriorating jobs and rejection. The objective is to find the rejected jobs, the non-rejected jobs, and the optimal non-rejected job sequence so that the cost function that includes the weighted of total load, total completion time, and total absolute deviation of completion time plus the total penalty of the rejected jobs would be minimized. Results showed that the problem is polynomial time solvable when the number of machine is fixed.

目錄

中文摘要……………………………………………………………………i
英文摘要……………………………………………………………………ii
誌謝…………………………………………………………………………iii
目錄……………………………………………………………………………iv
圖目錄………………………………………………………………………vi
表目錄………………………………………………………………………ix
第一章 緒論…………………………………………………………………1
1-1 研究背景與動機………………………………………………………1
1-2 研究目的………………………………………………………………3
1-3 研究架構………………………………………………………………4
第二章 排程理論與文獻探討………………………………………………6
2-1 排程問題分類…………………………………………………………6
2-2 排程績效衡量準則……………………………………………………8
2-3 排程求解方法…………………………………………………………9
2-4 文獻探討………………………………………………………………11
第三章問題定義與解法……………………………………………………13
3-1 問題描述與符號定義………………………………………………13
3-2 問題求解……………………………………………………………14
第四章結論與建議………………………………………………………17
參考文獻……………………………………………………………………18

圖目錄

圖1-1 研究架構……………………………………………………………5
圖3-1 非標準線性指派示意圖……………………………………………16


表目錄

表1-1 生產績效衡量指標……………………………………………………9

[1]S. Browne and U. Yechiali. Dynamic priority rules for cyclic type queues. Advances in Applied Probability Vol. 10 (1989), p. 432-450.
[2]A.S. Kunnathur and S.K. Gupta. Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem. European Journal of Operational Research Vol. 47 (1990), p. 56-64.
[3]G. Mosheiov. V-shaped policies for scheduling deteriorating jobs. Operations Research Vol. 39 (1991), p. 979-991.
[4]C.-Y. Low, C.-J. Hsu and C.-T. Su. Minimizing the makespan with an availability constraint on a single machine under simple linear deterioration. Computers and Mathematics with Applications Vol. 56 (2008), p. 257-265.
[5]S. Brown and U. Yechiali. Scheduling deteriorating jobs on a single process. Operations Research Vol. 38 (1990), p. 495-498.
[6]C.-L. Zhao, Q. Zhang and H.-Y Tang. Scheduling problems under linear deterioration. Acta Automatica Sinica Vol. 29 (2003), p. 531-535.
[7]C.-C. Wu, W.-C. Lee and Y.-R. Shiau. Minimizing the total weighted completion time on a single-machine under linear deterioration. International Journal of Advanced Manufacturing Technology Vol. 33 (2007), p. 1237-1243.
[8]M. Ji and T.C.E. Cheng. Parallel-machine scheduling with simple linear deterioration to minimize total completion time. European Journal of Operational Research Vol. 188 (2008), p. 342-347.
[9]C.-C Wu and W.-C. Lee. Single-machine group-scheduling problems with deteriorating setup times and job-processing times. International Journal of Production Economics Vol. 115 (2008), p. 128-133.
[10]W.H. Kuo and D.L. Yang. Minimizing the makespan in a single-machine scheduling problem with the cyclic process of an aging effect. Journal of the Operational Research Society Vol. 59 (2008), p. 416-420.
[11]W.-C. Lee, C.-C. Wu and H.-C. Liu. A note on single-machine makespan problem with general deteriorating function. International Journal of Advanced Manufacturing Technology Vol. 40 (2009), p. 1053-1056.
[12]E. Gerstl and G. Mosheiov. Scheduling on parallel identical machines with job-rejection and position-dependent processing times. Information Processing Letters Vol. 112 (2012), p. 743-747.
[13]C.-L. Zhao and H.-Y. Tang. A note to due-window assignment and single machine schedulingwith deteriorating jobs and a rate-modifying activity. Computers & Operations Research Vol. 39 (2012), P. 1300-1303.
[14]B. Alidaee and N.K. Womer. Scheduling with time dependent processing times: review and extensions. Journal of the Operational Research Society Vol. 50 (1999), p. 711-720.
[15]T.C.E. Cheng, Q. Ding and B.M.T. Lin. A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research Vol. 152 (2004), p. 1-13.
[16]A. Janiak, T. Krysiak, R. Trela. Scheduling problems with learning and aging effects: a survey. Decision Making in Manufacturing and Services Vol. 5 2 (2011), p. 19-36.
[17]S. Gawiejnowicz, Time-dependent scheduling, Springer Berlin Heidelberg, 2008.
[18]J.K. Cochran, S.-M. Horng and J.W Fowler. A Multi-Population Genetic Algorithm to Solve Multi-Objective Scheduling Problems for Parallel Machines. Computers & Operations Research Vol. 30 (2003), p. 1087-1102.
[19]M. Pinedo. Scheduling: Theory, Algorithms, and Systems, Prentice Hall, New Jersey, (2008).
[20]T.P. Bagchi. Multiobjective scheduling by Genetic algorithm. Kluwer Academic Publishers (1999).
[21]R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics Vol. 5 (1979), p. 287-326.
[22]J.J. Kanet. Minimizing variation of flow time in single machine systems. Management Science Vol. 27 (1981), p. 1453-1459.
[23]P. Brucker. Scheduling Algorithm. Springer-Verlag, Berlin (2004).
[24]C.-J. Hsu, T.C.E. Cheng and D.-L. Yang. Unrelated parallel-machine scheduling with rate-modifying activities to minimize the total completion time. Information Sciences Vol. 181 (2011), p. 4799-4803.
[25]王培珍，1996，應用遺傳演算法與模擬在動態排程問題之探討，中原大學，碩士論文。
[26]江珮甄，2005，以派工法則求解彈性流程式生產排程問題，國立台灣大學，碩士論文。
[27]劉鎮瑋，具資源限制及非等效平行機台考量之流程型生產排程問題，國立雲林科技大學，碩士論文。
[28]許洲榮，葉玉玲，蔡碧芳，相依整備時間考量下具等效平行機台之多階段流程型排程問題啟發式求解模式建構，南開技術學院，技術學刊。