臺灣博碩士論文加值系統

本研究旨在運用Python 設計基因算法程式，以模擬求解便利商店員工排班問題。求解便利商店的員工排班問題是指在可接受的時間內產出薪資支出較低的排班表，而設定之限制條件為滿足便利商店營運上對於員工能力的需求，以及員工對於出勤安排之偏好，且遵守勞動基準法對於工時、休假與加班費率之規定。

為了達成上述目標，本研究擬建構2 個模擬的便利商店。此2 間店聘雇了兼職和全職員工，且採用勞動基準法中兩周變形工時的制度。接著運用基因演算法之機制，逐代演化出不斷改良之排班表。而因應基因演算法在求解過程的隨機特性，本研究將整體程式執行100 次並將獲得的數據加以平均，以驗證其求解效果之良窳。

在3.5 GHz 四核心的電腦設備規格下，模擬結果指出，在滿足所有勞動法令與員工出勤偏好下，求得第1 代可行班表的平均時間為3.86 分鐘，最終代之最佳可行班表為14.51 分鐘。相較於實務界便利商店店長在排班時花費至少1 小時左右，兩者時間皆相當幅度地減少。而從最初代的可行解演化至最終代的最佳可
行解後，平均而言總薪資成本支出降低了1.96％，加班費用支出降低了75.18％；作為衡量滿足營運需求的指標，能力短缺情形，則改善了61.97％。由模擬結果可說明，即使店長成功排出已可行之班表，但仍有機會再進一步排出更佳之班表。因此，本研究若能作為一輔助工具以改良現有的便利商店人員排班式，則效益是可以期待的。

This study intends to simulate solving the staff scheduling problem for multiple convenience stores by genetic algorithm in Python. This denotes in an acceptable time obtaining a schedule that eliminates redundant payroll costs, while meeting operational requirement for employee abilities and employee preference for days off, as well as conforming to regulations of working hours, holiday and overtime pay rate specified in Labor Standards Act.

For this intention, this study constructs a simulation model of 2 convenience stores that are staffed by part-time and full-time employees. The two-week flextime policy is adopted. With the mechanism of genetic algorithm, a better schedule can be obtained through evolving. To tackle the stochastic characteristic of the solving procedure of genetic algorithm, the whole solving procedure is executed 100 times and the obtained data are averaged to verify the effectiveness of the proposed solving method.

In a 3.5 GHz quad-core environment, the simulation result shows that while meeting labor law regulations and employee preference, the averaged time to obtain the first feasible solution and the final best solution is 3.86 and 14.51 minutes, both showing great improvement compared to at least 1 hour by practical experts. And when the first feasible schedule evolves into the final best schedule, averagely total payroll costs have decreased by 1.96%, overtime pay expenses by 75.18%, and the shortage of ability by 61.97%. This denotes that even if store managers succeed in a feasible schedule, there is still a chance to propose a much better schedule. Therefore, the value of this study is expectable for being a good reference for store managers who are eager to strengthen the current scheduling tools for their own business.

摘要 I
ABSTRACT II
致謝 III
TABLE OF CONTENTS IV
LIST OF TABLES VI
LIST OF FIGURES VII
CHAPTER 1 INTRODUCTION 1
1.1 Research Background and Motivation 1
1.2 Research Purpose 2
1.3 Significance of This Research 4
1.4 Research Process 5
CHAPTER 2 LITERATURE REVIEW 8
2.1 Mathematical Programming 8
2.2 Metaheuristics 9
2.3 Scheduling Solving Methods for the Retail Industry 11
2.4 Brief Summary 12
CHAPTER 3 RESEARCH DESIGN AND METHODOLOGY 13
3.1 A Brief on Regulations for Scheduling in the Labor Standard Act 13
3.1.1 Working Hours and Holidays 14
3.1.2 Overtime Pay Rate 14
3.1.3 Flextime Policies 15
3.2 Simulation Model for 2 Convenience Stores 17
3.2.1 Category of Shifts 19
3.2.2 Number of Staffs 20
3.2.3 Legal Days off for All Employees 21
3.2.4 Operational Requirement 25
3.3 Formation of Mathematical Equations and Algorithms 28
3.4 Procedure of Genetic Algorithm 36
CHAPTER 4 RESULT ANALYSIS 43
4.1 An Example of a Schedule Output 43
4.2 Extension 46
CHAPTER 5 CONCLUSION AND FUTURE SUGGESTIONS 49
5.1 Research Conclusion 49
5.2 Future Suggestions 50
REFERENCE 53

Aickelin, U., & Dowsland, K. A. (2004). An indirect genetic algorithm for a nurse-scheduling problem. Computers & Operations Research, 31(5), 761-778.
Avramidis, A. N., Chan, W., Gendreau, M., L’Ecuyer, P., & Pisacane, O. (2010). Optimizing daily agent scheduling in a multiskill call center. European Journal of Operational Research, 200(3), 822-832.
Bailey, J. (1985). Integrated days off and shift personnel scheduling. Computer & Industrial Engineering, Vol. 9, No. 4, pp. 395-404.
Beasley, J.E. & Chu, P.C. (1996). A genetic algorithm for set covering problem. European Journal of Operational Research, Vol. 94, pp. 392-404.
Cai, X. & Li, K. (2000). A genetic algorithm for scheduling staff of mixed skills under multi-criteria. European Journal of Operational Research, 125 359–369.
Chapados, N., Joliveau, M., L’Ecuyer, P. & Rousseau, L. M. (2014). Retail store scheduling for profit. European Journal of Operational Research, 239,609–624.
Dean, J. S. (2008). Staff scheduling by a genetic algorithm with a two dimensional chromosome structure. In Proc of the 7th Conference on the Practice and Theory of Automated Timetabling, Montreal, Canada.
Diveev, A. I., & Bobr, O. V. (2017). Variational genetic algorithm for NP-hard scheduling problem solution. Procedia Computer Science, 103, 52-58.
Ernst, A. T., Jiang, H., Krishnamoorthy, M. & Sier, D. (2004). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153(1), 3-27.
Fukunaga, A., Hamilton, E., Fama, J., Andre, D., Matan, O. & Nourbakhsh, I. (2002). Staff scheduling for inbound call and customer contact centers. AI Magazine, 23(4), 30-40.
Henao, C. A., Muñoz, J. C. & Ferrer, J. C. (2015). The impact of multi-skilling on personnel scheduling in the service sector: A retail industry case. Journal of the Operational Research Society, 66(12), 1949–1959.
Jaumard, B., Semet, F. & Vovor, T. (1997). A generalized linear programming model for nurse scheduling. European Journal of Operational Research, pp. 1-18.
Kabak, Ö., Ülengin, F., Aktaş, E., Önsel, Ş., & Topcu, Y. I. (2008). Efficient shift scheduling in the retail sector through two-stage optimization. European Journal of Operational Research, 184(1), 76-90.
Konak, A., Coit, D. V. & Smith, A. E. (2006). Multi-objective optimization using genetic algorithm: A tutorial. Reliability Engineering and System Safety, 91, 992 - 1007.
Labor Insurance Act (勞工保險條例) (2015). https://law.moj.gov.tw/Eng/LawClass/LawContent.aspx?PCODE=N0050001
Labor Pension Act (勞工退休金條例) (2016). https://law.moj.gov.tw/Eng/LawClass/LawContent.aspx?PCODE=N0030020
Labor Standard Act (勞動基準法) (2018). https://law.moj.gov.tw/Eng/LawClass/LawAll.aspx?PCode=N0030001
Lee, W. & Kim, H. Y. (2005). Genetic algorithm implementation in Python. Fourth Annual ACIS International Conference on Computer and Information Science.
Musliu, N., Schaerf, A., & Slany, W. (2004). Local search for shift design. European Journal of Operational Research, 153(1), 51-64.
National Health Insurance Act (全民健康保險法) (2017). https://law.moj.gov.tw/LawClass/LawContent.aspx?PCODE=L0060001
Tang, H., Miller-Hooks, E. & Tomastik, R. (2007). Scheduling technicians for planned maintenance of geographically distributed equipment. Transportation Research Part E – Logistics and Transportation Review, 43 591–609.
Tanomaru, J. (1995). Staff scheduling by a genetic algorithm with heuristic operators. Proceedings of 1995 IEEE International Conference on Evolutionary Computation.
Thompson, G. M. & Goodale, J.C. (2006). Variable employee productivity in workforce scheduling. European Journal of Operational Research, 170 376–390.
Van den Bergh, J., Beliën, J., De Bruecker, P., Demeulemeester, E., & De Boeck, L. (2013). Personnel scheduling: A literature review. European Journal of Operational Research, 226(3), 367-385.
Virtanen, M., Ferrie, J.E., Singh-Manoux, A., Shipley, M. J., Vahtera, J., Marmot , M.G. & Kivimäki, M. (2010). Overtime work and incident coronary heart disease: the Whitehall II prospective cohort study. European Heart Journal, Volume 31, Issue 14, 1737-1744.
Xie, X. H. (2002). Applications of genetic algorithms for TRA’s driver scheduling and rostering problems. Master's Thesis, National Cheng Kung University.
Zolfaghari, S., Vinh, Q., El-Bouri, A. & Khashayardoust, M. (2010). Application of a genetic algorithm to staff scheduling in retail Sector. International Journal of Industrial and Systems Engineering, 5 20–47.