本論文提出一種基於A*搜尋演算法和線性規劃的迭代演算法來解決具優先次序限制條件下可展延任務的排程問題。對於排程問題的描述如下，給定m個處理器及n項任務並且已知每一項任務指派各種數量處理器所會耗費的處理時間，此外，任務與任務之間還須考慮優先次序限制。對於此問題，排程演算法的目的則是要得到較短的總完工時間。目前最好的多項式時間近似演算法(polynomial-time approximation algorithm)是由Jansen et al. [1]所提出，其近似比率(approximation ratio)約為4.73。我們所提出的方法則可以保證近似比率低於3.78。然而，為了保證近似比率而利用的A*搜尋耗費了大部分的運行時間且其時間複雜度可能為指數複雜度，所以我們更進一步嘗試修改迭代演算法省略A*搜尋的步驟。修改過後的演算法雖無法保證最差的近似比率，但在我們設計的實驗中與Jansen et al所提出之演算法相比，我們所提出修改後的演算法在平均的總完工排程時間以及演算法運行速度皆有明顯的改善。

This paper presents an iterative approach based on the A* search algorithm and linear programming to solve the scheduling problem of malleable tasks with general precedence constraints. The scheduling problem is described as follows. We are given m processors and n tasks and known the processing time of each task with an arbitrary number of processors. In addition, the precedence constraints among these tasks must be considered. For this problem, the goal of a scheduling algorithm is to minimize the makespan. The best previous polynomial-time approximation algorithm proposed by Jansen et al. [1] has an approximation ratio about 4.73. Our algorithm can guarantee the approximation ratio better than 3.78. However, since the A* search of this approach costs most of running time to guarantee the approximation ratio and its time complexity may be exponential, we further try to modify the iterative approach by skipping the A* search. Therefore, the modified algorithm cannot guarantee the worst approximation ratio, but in our experiments compared with the algorithm proposed by Jansen et al., our modified algorithm achieves a significant improvement on average makespan and running time.

[1]K. Jansen and H. Zhang, “An approximation algorithm for scheduling malleable tasks under general precedence constraints,” ACM Trans. Algorithms, vol. 2, no. 3, pp. 416-434, Jul. 2006.
[2]R. Lepre, G. Mouni and D. Trystram, “An approximation algorithm for schedul-ing trees of malleable tasks,” European J. of Operational Research, vol. 142, no. 2, pp. 242-249, Jul. 2001.
[3]R. Lepre, D. Trystram, and G. J. Woeginger, “Approximation algorithms for scheduling malleable tasks under precedence constraints,” Int. J. Found. Computer Science, vol. 13, no. 4, pp. 613 -627, 2002.
[4]M. Cosnard and D. Trystram, “Parallel Algorithms and Architectures,” International Thomson Publishing, 1995.
[5]P. E. Hart, N. J. Nilsson and B. Raphael, “A formal basis for the heuristic determi-nation of minimum cost Paths,” IEEE Trans. Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, Jul. 1968.
[6]M. Skutella, “Approximation algorithms for the discrete time-cost Tradeoff prob-lem,” Mathematics of Operations Research, vol. 23, no. 4, pp. 909-929, Nov. 1998.
[7]R. Dechter and J. Pearl, “Generalized best-first search strategies and the optimality of A*,” Journal of the ACM, vol. 32, no. 3, pp. 505-536, Jul. 1985.
[8]D. Trystram, “Scheduling parallel applications using malleable tasks on clusters,” In Proc. 15th International Conference on Parallel and Distributed Processing Symposium, pp. 2128-2135, Apr. 2001.
[9]J. Du and J. Y.-T. Leung, “Complexity of scheduling parallel task systems,” SIAM J. Discrete Math., vol. 2, no. 4, pp. 473-487, Nov. 1989.
[10]J. Turek, J. L. Wolf and P. S. Yu, “Approximate algorithms scheduling parallelizable tasks,” In Proc. 4th Annual ACM Symposium on Parallel Algorithms and Ar-chitectures, pp. 323-332, Jun. 1992.
[11]E. Blayo, L. Debreu, G. Mouni and D. Trystram, “Dynamic load balancing for ocean circulation model with adaptive meshing,” In Proc. of the 5th European Conference on Parallel Computing (Euro-Par 1999), vol. 1685, pp. 303-312, 1999.
[12]B. Coppin, “Artificial intelligence illuminated,” Jones and Bartlett Publishing, 2004.
[13]E. K. Burke, M. Dror and J. B. Orlin, “Scheduling malleable tasks with interde-pendent processing rates: Comments and observations,” Discrete Applied Mathe-matics, vol. 156, no. 5, pp. 620-626, Mar. 2008.
[14]U. M. Schwarz, “Tightness results for malleable task scheduling algorithms,” In Proc. the 7th International Conference on Parallel Processing and Applied Mathe-matics (PPAM 2007), vol. 4967, pp. 1059-1067, 2008.
[15]G. Mouni, C. Rapine and D. Trystram, “Efficient approximation algorithms for scheduling malleable tasks,” In Proc. 11th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 12-32, 1999.
[16]K. Jansen and L. Porkolab, “Linear-time approximation schemes for scheduling malleable parallel tasks,” In Proc. the 10th annual ACM-SIAM symposium on Dis-crete algorithms, pp. 490-498, Jan. 1999.
[17]R. L. Graham, “Bounds for certain multiprocessing anomalies,” Bell Syst. Tech. J. vol. 45, no. 9, pp. 1563-1581, 1966.
[18]lp_solve reference guide, http://lpsolve.sourceforge.net/5.5/