考慮公平性與順序相依整備時間之工作分配

Abstract

工作分配與排程問題在許多領域中一直是很重要的課題。有效率的工作分配與排程有助於公司提高生產力以獲得更多利益。在製造工廠裡，為了達到公司訂定的生產目標，管理者將各式各樣的工作分配給不同的機器處理，每台機器適合處理的工作不盡相同，工作處理速度、生產出來的品質利潤也不同；此外，工作分配問題也發生在職場上主管對員工指派工作，一台機器相當於是一位員工，每位員工的實力與專長也不太一樣。同時，工作執行的前後可能會存在有整備時間，當一個工作完成後，需要整理機器或是拆裝配件才能處理下一個工作，因此工作執行順序也是一個必要的考量。每台機器及每位員工都有工作時間限制，假如超時工作，就會產生維修成本及員工的加班成本。 除此之外，公平性議題也相當重要，本研究考慮若干工作與若干員工，完成工作會帶來利益，希望每台機器或每位員工都能在有限資源下賺得最大利益。在考慮工作整備時間及工作量限制的同時，將工作公平地分配給每位員工，為管理者處理這一工作分配和排程問題帶來了新的挑戰。 因此，在本篇論文中，我們建立了一個數學模型清楚地描述該公平性工作分配問題，目標最大化機器產生的最小利益，以達到工作公平分配的目的。由於這是一個NP-hard問題，我們套用基因演算法並嘗試優化生成的初始解群、交配方法及突變方法。我們發現採用最小利益優先（LB）的交配方法能帶來較好的結果，而使用Outer 突變方法因帶來更多的遺傳多樣性也明顯有幫助。我們也設計一系列的數值實驗，證明演算法在不同情境之下仍能保有良好的效能。

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.