以粒子群演算法求解具學習效應的流水式雙機排程問題

Using Particle Swarm Optimization to Solve Two-Machine Flowshop Scheduling Problem with a Learning Effect

霜睿哲(Jui-Che Shuang)

指導教授 ： 郭文宏

國立虎尾科技大學/管理學院/資訊管理研究所/碩士(2011年)

摘要

在本論文中，我們探討的是具學習效應的流水式雙機排程問題。與時間相依的學習效應的工作被假定在工作計劃的總正常處理時間之前的一個函數。典型的流水式排程問題具有n個工作和m個機台的案例中，除了Johnson’s雙機總完工時間(makespan)的情況下，很多流水式排程問題都是已知的NP-hard問題，因此，我們將注意力轉向求解效能近似的最佳解。我們提出WSPT啟發式演算法和粒子群演算法求解具學習效應的流水式排程問題，以總加權完工時間最小化(Minimize Total Weighted Completion Time)為目標。結果分為三個部分進行，首先在工作件數7、8與9，利用窮舉法獲得此問題之最佳解，來與WSPT啟發式演算法和粒子群演算法做比較；其次在10到100之工作件數下，使用粒子群演算法(Particle Swarm Optimization，PSO)求其近似解，並與WSPT啟發式演算法做比較；第二部分結果發現，粒子群演算法經過數次迭代計算後就會陷入局部最佳解，因此，我們進一步提出將粒子群演算法的初始解改為WSPT規則與SPT規則的解，證明粒子群演算法在具學習效應的流水式雙機排程問題上會比WSPT規則與SPT規則好。

關鍵字

學習效應 ； 粒子群演算法 ； 流水式排程 ； 總加權完工時間

並列摘要

In this paper, we consider a time-dependent learning effect into a two-machine flowshop scheduling problem. The time-dependent learning effect of a job is assumed to be a function of total normal processing time of jobs scheduled before it. The classical flowshop scheduling problem with n jobs and m machines, it is well known that except for Johnson’s two-machine makespan case, most of the flowshop scheduling problems are known to be NP-hard, hence, we turn our attention to obtain schedules in which the performance approximates those of optimal schedules. We propose WSPT heuristic algorithms and particle swarm optimization to solve two-machine flowshop scheduling problem with a learning effect, the objective function is the total weighted completion times minimize. The results of three parts, first, the job number form 7 to 9, the use of exhaustive method to obtain the optimal solution to this problem, and WSPT heuristic algorithms and particle swarm algorithm to compare；second, the job number form 10、20、30、50、100, Using the particle swarm Optimization algorithm solving the approximate solution, and heuristic algorithms to compare with WSPT；the second part results show PSO algorithm after several iterations will be convergence after a local optimal solution, therefore, we further proposed PSO algorithm the initial solution into WSPT rules and the SPT rule solution, that prove particle swarm algorithm than WSPT rules and SPT rules good for the learning effect of the flowshop two-machine scheduling problems.

並列關鍵字

learning effect ； particle swarm Optimizationflowshop ； total weighted completion times

參考文獻

1. Bean, J.C., 1994, “Genetic algorithm and random keys for sequencing and optimization”, ORSA Journal on Computing, 6(2), pp. 154-160.

2. Biskup, D., 1999, “Single-machine scheduling with learning considerations”, European Journal of Operational Research, 115, pp.173–178.

3. Compbell, H. G. , Dudek, R. A. and Smith, M. L., 1970, “A heuristic algorithm for the ‘N’ job ‘M’ machine sequence problem”, Management Science, 16, 630-637.

5. Chen, P. , Wu, C. C. and Lee, W. C., 2006, “A bi-criteria two-machine flowshop scheduling problem with a learning effect”, Journal of the Operational Research Society, 57, pp. 1113–1125.

6. Eren, T. and Guner, E., 2007, “ Minimizing total tardiness in a scheduling problem with a learning effect”, Applied Mathematical Modelling, 31, pp. 1351–1361.