» Download Article
On Scheduling Malleable Jobs to Minimise the Total Weighted Completion Time
Information Control Problems in Manufacturing, Volume # 13 | Part# 1
Authors
Sadykov, Ruslan
Digital Object Identifier (DOI)
10.3182/20090603-3-RU-2001.00250
Page Numbers:
1514-1516
Index Terms
Optimization and Control; Mathematical Approaches for Scheduling; Discrete Applied Mathematics
Abstract
This paper is about scheduling parallel jobs, i.e. which can be executed on more than one processor at the same time. Malleable jobs is a special class of parallel jobs. The number of processors a malleable job is executed on may change during the execution. In this work, we consider the NP-hard problem of scheduling malleable jobs to minimize the total weighted completion time or mean weighted flow time. For this problem, we introduce an important dominance rule which can be used to reduce the search space while searching for an optimal solution.
References
Blayo, E., Debreu, L., Mouni´e, G., and Trystram, D. (2000). Dynamic load balancing for adaptive mesh ocean circulation model. Engineering Simulations, 22, 8–24. Blazewicz, J., Kovalyov, M., Machowiak, M., Trystram, D., and Weglarz, J. (2006). Preemptable malleable task scheduling problem. IEEE Transactions on Computers, 55(4), 486–490. Drozdowski, M. (2004). Scheduling parallel tasks — algo- rithms and complexity. In J.T. Leung (ed.), Handbook of Scheduling: Algorithms, Models, and Performance Anal- ysis. Chapman Hall, CRC Press. Dutot, P.F., Mouni´e, G., and Trystram, D. (2004). Scheduling parallel tasks — approximation algorithms. In J.T. Leung (ed.), Handbook of Scheduling: Algo- rithms, Models, and Performance Analysis. Chapman Hall, CRC Press. Fishkin, A., Jansen, K., and Porkolab, L. (2001). On min- imizing average weighted completion time: A ptas for scheduling general multiprocessor tasks. In R. Freivalds (ed.), Proceedings of the 13th International Symposium on Fundamentals of Computation Theory, LNCS 2138, 495–507. Garey, M. and Johnson, D. (1979). Computers and In- tractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco. Hendel, Y. and Kubiak, W. (2008). Minimizing mean flow time for the two machines semi-malleable jobs scheduling problem. In F. Serifoglu and U. Bilge (eds.), Proceedings of the 11th International Workshop on Project Management and Scheduling, 136–140. Ludwig, W. (1995). Algorithms for Scheduling Mal leable and Nonmal leable Paral lel Tasks. Ph.D. thesis, Univer- sity of Wisconsin-Madison. Serafini, P. (1996). Scheduling jobs on several machines with the jobs splitting property. Operations Research, 44(4), 617–628. Tchernykh, A., Trystram, D., Brizuela, C., and Scherson, I. (2009). Idle regulation in non-clairvoyant scheduling of parallel jobs. Discrete Applied Mathematics, 157, 364– 376. Turek, J., Wolf, J., and Yu, P. (1992). Approximate algorithms for scheduling parallelizable tasks. In 4th Annual ACM Symposium on Paral lel Algorithms and Architectures, 323–332.