考慮公平性、不同機臺產能與不同工作截止時間的工作分配問題

Abstract

工作分配在各領域中一直是一個重要議題。在製造業中，其中一個目標是希望能最大化最小利潤的機台。然而，在實際的工作分配中，我們不僅僅要考慮工作的利潤，還要考慮工作本身是否可以被完成。工作的截止時間和機器的產能限制都是安排工作時必須考慮的地方。這樣的特性，讓工作分配更為困難，乃至於我們需要一個專門的排序法來解決這個問題。我們希望能設計演算法，在考慮公平性、不同機臺產能與不同工作截止時間的工作分配問題，有效分配工作。 在本研究中，我們考慮若干工作及若干機台，完成工作會帶來利潤，但也會為機台帶來工作量，各機台能負荷的最大工作量是一樣但是有不同的情形，同時每個工作有自己的截止時間。為了使各機台的利潤盡量地一致，我們的目標是最大化得到最小利潤的機台上的利潤，根據前人的最長處理時間優先演算法（LPT rule），以及產能限制下的最大收益優先演算法（CHBF rule），我們提出了最差收益擠出法。 我們採用數值試驗的方式證明了最差收益擠出法的有效性。通過和整數規劃得出的最優解以及線性規劃得出的最優解的上界進行比較，我們可以顯示最差收益擠出法是一個優秀的算法。通過和基因（GA）算法的比較，我們證明了我們的算法在耗時比基因算法少的情況下有著與之相當甚至更為優秀的表現。我們認為這個算法在未來還有一些問題可以應用，本文所述的「擠出」概念以及具體的擠出方法可以為今後的研究者們提供一種解決問題的新思路。

Job scheduling is an important issue applied in many fields. In the manufacturing industry, one of the objectives is to assign jobs to machines in order to maximize the minimum profit among machines. Assigning jobs by considering their benefits is a good idea. However, we also have to consider whether the jobs can be assigned to those machines, because each machine cannot be assigned too many jobs due to limited capacity. Moreover, each job has its own due date. This characteristic introduces a new challenge to this allocation problem and calls for a specific algorithm to solve it. We propose an efficient algorithm to assign jobs by taking fairness, machine capacity, and job due dates into consideration. In this study, our objective is to assign jobs to bring benefits to all the machines as equally as possible while ensuring that machines cannot be overloaded and all assigned jobs can be completed before their due dates. The capacity of all machines are the same. We propose the least benefit out (LBO) algorithm based on the longest processing time (LPT) rule and the capacitated highest-benefit job first (CHBF) algorithm. We use numerical experiments to verify the efficiency of the LBO algorithm. By comparing with optimal solutions or their upper bounds obtained by integer/linear programing, we confirm that our algorithm can get a good enough result. Moreover, we choose Genetic Algorithm as a benchmark and find that LBO can use less time to get similar or better results in almost all cases in our experiment. We believe that this algorithm as well as the way to squeeze out worse works can be a new groundbreaking method that may be adopted for solving other problems.