單機多屬性工作排程研究

Abstract

不論在排程或人力資源規劃的問題中，如何讓多重屬性工作之排序能達到平均分散已逐漸成為重要的議題之一。當工作所具備屬性越多、其值範圍越小時，要避免屬性值相似的工作過度集中就會變得更加複雜。本論文乃探討在給定的排程限制下，如何利用有效且快速的方法，於單機作業中找出一組最佳近似解，可滿足同屬性工作在排序上均勻地分散。 在本篇論文研究中，在給定各工作所具備屬性個數、各屬性值範圍和排序限制規範後，以三階段演算法進行求解。階段一主要使用以獨立點集問題為基礎的演算法找出初始解；階段二則是使用兩種區域搜尋法進行改善；階段三則使用禁忌搜尋法，並搭配swap和2-opt兩種鄰域結構，進行前兩階段的再改善。根據實驗結果顯示，我們所提出的三階段求解方法可以在短時間內求得良好的最佳近似解，而對於相似性高的工作群，其分散度之改善率可達到八成以上。

How to make multi-attribute jobs dispersed evenly over a single horizon is one of the important issues in scheduling or human resource planning. The more number of attributes each job is associated with, or the narrower the value range of each attribute has, the harder the problem will be. Thence, this paper seeks to develop an effective and efficient approach for composing quality schedules in which similar jobs are evenly dispersed subject to the several realistic constraints. This thesis develops a three-phase algorithm to solve the studied problem. In phase one, we deploy a greedy algorithm, based upon independent set to obtain an initial solution, and in phase two, we design two local search algorithms to improve upon the initial solutions. In phase three, a tabu search algorithm equipped with swap and 2-opt neighborhood structures is developed to further improve the solutions obtained in phase two. The numerical statics of a computational study indicate that the tree-phase algorithm can produce quality solutions, reducing the number of violations to zero for most test instances. For instances with high similarities among the jobs, the improvement even could reach 80 percents.