An Arabic Slot Grammar parser
Michael C. McCord, Violetta Cavalli-Sforza
ACL 2007
Consider a system of independent tasks to be scheduled without preemption on a parallel computer. For each task the number of processors required, the execution time, and a weight are known. The problem is to find a schedule with minimum weighted average response time. We present an algorithm called SMART (which stands for scheduling to minimize average response time) for this problem that produces solutions that are within a factor of 8.53 of optimal. To our knowledge this is the first polynomial-time algorithm for the minimum weighted average response time problem that achieves a constant bound. In addition, for the unweighted case (that is, where all the weights are unity) we describe a variant of SMART that produces solutions that are within a factor of 8 of optimal, improving upon the best known bound of 32 for this special case.
Michael C. McCord, Violetta Cavalli-Sforza
ACL 2007
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021