請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/74883
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 孔令傑(Ling-Chieh Kung) | |
dc.contributor.author | Yi-Hsuan Chen | en |
dc.contributor.author | 陳奕瑄 | zh_TW |
dc.date.accessioned | 2021-06-17T09:09:30Z | - |
dc.date.available | 2021-02-20 | |
dc.date.copyright | 2021-02-20 | |
dc.date.issued | 2021 | |
dc.date.submitted | 2021-02-02 | |
dc.identifier.citation | Avalos-Rosales, O., A. Alvarez, F. Angel-Bello. 2013. A reformulation for the problem of scheduling unrelated parallel machines with sequence and machine dependent setup times. Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling (ICAPS2013) 211 278–282. Bansal, N., M. Sviridenko. 2006. The santa claus problem. Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing 31–40. Bertsimas, D., V. F. Farias, N. Trichakis. 2011. The price of fairness. Operations Research 59(1) 17–31. Cota, L. P., V. N. Coelho, F. G. Guimaraes, M. J. F. Souza. 2018. Bi-criteria formulation for green scheduling with unrelated parallel machines with sequence-dependent setup times. International Transactions in Operational Research 1–22. Guinet, A. 1993. Scheduling sequence-dependent jobs on identical parallel machines to minimize completion time criteria. The International Journal of Production Research 31(7) 1579–1594. Helal, M., G. Rabadi, A. Al-Salem. 2006. A tabu search algorithm to minimize the makespan for the unrelated parallel machines scheduling problem with setup times. International Journal of Operations Research 3(3) 182–192. Kurz, M. E., R. G. Askin. 2001. Heuristic scheduling of parallel machines with sequence-dependent set-up times. International Journal of Production Research 39(16) 3747–3769. Li, T.-T. 2019. A fair multi-agent job assignment and scheduling algorithm considering release times. Master’s thesis, National Taiwan University, Taipei, Taiwan. Lin, Y. A. 2017. iSMART: An approximation algorithm for fair job allocation on unrelated machines. Master’s thesis, National Taiwan University, Taipei, Taiwan. Liu, C.-W. 2016. Job allocation with a consideration of fairness. Master’s thesis, National Taiwan University, Taipei, Taiwan. Rabadi, G., R. J. Moraga, A. Al-salem. 2006. Heuristics for the unrelated parallel machine scheduling problem with setup times. Journal of Intelligent Manufacturing 17(4) 85–97. Tran, T. T., A. Araujo, J. C. Beck. 2016. Decomposition methods for the parallel machine scheduling problem with setups. INFORMS Journal on Computing 28(1) 83–95. Tran, T. T., J. C. Beck. 2012. Logic-based Benders decomposition for alternative resource scheduling with sequence dependent setups. Proceedings of the 20th European Conference on Artificial Intelligence(ECAI) 774–779. Vallada, E., R. Ruiz. 2011. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research 211 612–622. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/74883 | - |
dc.description.abstract | 工作分配與排程問題在許多領域中一直是很重要的課題。有效率的工作分配與排程有助於公司提高生產力以獲得更多利益。在製造工廠裡,為了達到公司訂定的生產目標,管理者將各式各樣的工作分配給不同的機器處理,每台機器適合處理的工作不盡相同,工作處理速度、生產出來的品質利潤也不同;此外,工作分配問題也發生在職場上主管對員工指派工作,一台機器相當於是一位員工,每位員工的實力與專長也不太一樣。同時,工作執行的前後可能會存在有整備時間,當一個工作完成後,需要整理機器或是拆裝配件才能處理下一個工作,因此工作執行順序也是一個必要的考量。每台機器及每位員工都有工作時間限制,假如超時工作,就會產生維修成本及員工的加班成本。 除此之外,公平性議題也相當重要,本研究考慮若干工作與若干員工,完成工作會帶來利益,希望每台機器或每位員工都能在有限資源下賺得最大利益。在考慮工作整備時間及工作量限制的同時,將工作公平地分配給每位員工,為管理者處理這一工作分配和排程問題帶來了新的挑戰。 因此,在本篇論文中,我們建立了一個數學模型清楚地描述該公平性工作分配問題,目標最大化機器產生的最小利益,以達到工作公平分配的目的。由於這是一個NP-hard問題,我們套用基因演算法並嘗試優化生成的初始解群、交配方法及突變方法。我們發現採用最小利益優先(LB)的交配方法能帶來較好的結果,而使用Outer 突變方法因帶來更多的遺傳多樣性也明顯有幫助。我們也設計一系列的數值實驗,證明演算法在不同情境之下仍能保有良好的效能。 | zh_TW |
dc.description.abstract | Job allocation problem is an important issue in many fields over the past few years, and effective job allocation helps companies increase productivity and earn more benefits. Manager assign different jobs to different machines to achieve the production objective. The capability of machines, including the process speed, the process quality, and the benefit generated, are not the same. Moreover, job allocation and scheduling problem also occurs in the office that a manager assign jobs to employees. A machine is then thought of as an employee. The abilities of employees are also different. There may exist sequence-dependent setup times between jobs. Maintain cost or overtime pay may reduce the generated benefit of a machine or an employee when the machine or employee work over its capacity limit. The fairness issue also becomes more and more important. More precisely, each machine or employee wants to earn as much benefit as possible under limited resources. Allocating jobs fairly with considering sequence-dependent setup times and capacity limit introduces a new challenge for decision makers. Therefore, in this research, we build a mathematical model for the aforementioned job allocation problem. The objective is to maximize the minimum net benefit, which is the total benefit minus overtime penalty, among all machines for fairness purpose. Since the problem is NP-hard, we apply GA to this problem. Based on the procedure of GA, several improvements of each step are implemented. We find that assigning jobs to the least net benefit machine can do better crossover. Outer mutation performs better than inner mutation since outer mutation generates more diversity. We also conduct numerical experiments to examine the average performance of our algorithm. | en |
dc.description.provenance | Made available in DSpace on 2021-06-17T09:09:30Z (GMT). No. of bitstreams: 1 U0001-0102202100585600.pdf: 1750682 bytes, checksum: 1cbca0832cd26b8e442b748126b702d0 (MD5) Previous issue date: 2021 | en |
dc.description.tableofcontents | 1 Introduction 1 1.1 Background and motivation . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Research objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Research plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Literature Review 5 2.1 Sequence-dependent setup time on unrelated machines . . . . . . . . . . 6 2.2 Job allocation considering fairness . . . . . . . . . . . . . . . . . . . . . . 9 2.2.1 Jobs with a single attribute . . . . . . . . . . . . . . . . . . . . . 9 2.2.2 Jobs with multiple attributes . . . . . . . . . . . . . . . . . . . . 10 3 Problem Formulation 13 4 Algorithm 19 5 Numerical Study 27 5.1 Experiment Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Performance comparison among GA versions . . . . . . . . . . . . . . . . 29 5.3 Impact of factors on performance . . . . . . . . . . . . . . . . . . . . . . 31 5.4 Time efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6 Conclusions and Future Works 37 A Supplemental Results of the Numerical Studies 39 | |
dc.language.iso | en | |
dc.title | 考慮公平性與順序相依整備時間之工作分配 | zh_TW |
dc.title | Job allocation considering fairness and sequence-dependent setup times | en |
dc.type | Thesis | |
dc.date.schoolyear | 109-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 郭佳瑋(Chia-Wei Kuo),黃奎隆(Kwei-Long Huang) | |
dc.subject.keyword | 工作排程,公平性,順序相依整備時間,工作量限制,基因演算法, | zh_TW |
dc.subject.keyword | Job Scheduling,Fairness,Sequence-dependent setup time,Capacity limit,Genetic Algorithm, | en |
dc.relation.page | 45 | |
dc.identifier.doi | 10.6342/NTU202100307 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2021-02-03 | |
dc.contributor.author-college | 管理學院 | zh_TW |
dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-0102202100585600.pdf 目前未授權公開取用 | 1.71 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。