基因演算法在排休之應用

Application of Genetic Algorithm on the Leave Allocation Problem

錢玉兒(Yu-Er Chien)

指導教授 ： 謝俊宏

國立臺中科技大學/資訊學群/資訊科技與應用研究所/碩士(2009年)

https://doi.org/10.6826/NUTC.2009.00055

摘要

摘 要

提供員工適當的休假，是讓員工調節身心與體力、取得家庭與工作平衡、以及提高員工向心力與忠誠度的重要措施之一。為了使員工有適當的休假，組織應運用一個有效的方法來對員工休假的申請進行最好的規劃。
本研究的主要目的，即是運用一個有效的方法來分配組織的休假。休假分配問題類似於一般化的指派問題(Generalized Assignment Problem)，當員工人數及休假時段的數目變得很大時，休假分配問題變成一個複雜的問題。為解決此問題，本研究首先藉由員工休假志願表來瞭解員工休假的志願或偏好。在員工填好志願表後，將員工的休假意願或偏好進行彙整。其次，根據組織的目標，以及休假的限制進行求解。由於一般組織都希望在短時間內即能求得多種可行方案，鑑此，運用短時間內可求得近似最佳解的啟發式演算法(Heuristic Algorithm)比運用可求得精確解但耗時的精確演算法(Exact Algorithm)更加合適。從前人的文獻可以發現，基因演算法(Genetic Algorithm)在求解一般化的指派問題可以得到不錯的結果。因此，本研究運用基因演算法進行求解。
為驗證基因演算法的有效性，本研究運用幾個個案公司或組織的情境來進行分析。研究結果顯示：運用基因演算法在排休上可獲得不錯的結果；提高員工的權重可以提高員工被安排到更前志願的可能性。除此之外，本研究也對基因參數改變的影響進行探討，基因參數的確對結果有所影響。

關鍵字

排休 ； 休假分配 ； 休假排程 ； 基因演算法 ； 分配問題

並列摘要

ABSTRACT

Providing employees with fitting leave is an important task for many organizations to let employees live a healthy life, remain in physical strength, and maintain the work-life balance. In recognition of the importance of leave in maintaining the work-life balance for employees, and with the understanding that allocation of leave is often difficult during peak-periods in service delivery settings, some organizations have developed various guiding principles. These principles, however, may not ensure fair allocation of leave because the organizations arrange leave mostly by the experience of senior managers and fail to use an objective quantified indicator to ensure high employee satisfaction on leave allocation.
In this study we employ the genetic algorithm (GA) as an analytical tool to solve the leave allocation problem. The problem demonstrated deals with the allocation of leave to employees. Employees are first asked to point out their preferences, in an employee–leave time table, which takes the form of a scoring system where a one indicates a first choice, two a second and so on up until an allowed maximum number of preferences. Then GA is employed to allocate the leave of an organization.
Results from this study show that the proposed GA approach can obtain feasible solutions quickly and can help the organization make decisions effectively and efficiently. In addition, increasing the priority weight of an employee can lead to a higher probability of being assigned a better choice. The increase of the employee number, however, will increase the complexity of the allocation and take much computational time. Furthermore, in this study, the influences of genetic parameters are investigated and discussed.

並列關鍵字

Leave allocation ； genetic algorithm ； leave scheduling ； GA ； assignment problem

參考文獻

[2] P.R. Harper, V. de Senna, I.T. Vieira, and A.K. Shahani,“A genetic Algorithm for the Project Assignment Problem,” Computer and Operations Research, Vol. 32, pp. 1225-1265, 2005.

[4] R.C. Chen, T.T. Chen, and W.L. Fang, “Assignment of External Off-the-job Training Courses to Employees Using Genetic Algorithm,” Information Technology Journal, Vol. 8, No. 2, pp. 147-155, 2009.

[5] T Öncan, “ A survey of theGeneralized Assignment Problem and its Applications,” INFOR, Vol. 45, No. 3, pp. 123-141, 2007.

[6] P.C. Chu, and J.E. Beasley, “A Genetic Algorithm for the Generalized Assignment Problem,” Computers and Operations Research, Vol. 24, No. 1, pp. 17–23, 1997.

[7] J.M. Wilson, “A Genetic Algorithm for the Generalized Assignment Problem,” Journal of the Operational Research Society, Vol. 48, pp. 804-809, 1997.