Minimum Weighted Completion Time
- PDF / 226,966 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 96 Downloads / 211 Views
M
Minimum Weighted Completion Time
18. Tarjan, R.E.: Data structures and network algorithms. In: CBMSNSF Reg. Conf. Ser. Appl. Math., vol. 44. SIAM, Philadelphia (1983) 19. Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J. ACM 46(3), 362–394 (1999)
Minimum Weighted Completion Time 1999; Afrati et al. V.S. ANIL KUMAR1 , MADHAV V. MARATHE2 , SRINIVASAN PARTHASARATHY3 , ARAVIND SRINIVASAN4 1 Network Dynamics and Simulation Science Laboratory, Bioinformatics Institute, Virginia Tech, Blacksburg, VA, USA 2 Department of Computer Science and Virginia Bioinformatics Institute, Virginia Tech, Blacksburg, VA, USA 3 IBM T.J. Watson Research Center, Hawthorne, NY, USA 4 Department of Computer Science, University of Maryland, College Park, MD, USA Keywords and Synonyms Average weighted completion time Problem Definition The minimum weighted completion time problem involves (i) a set J of n jobs, a positive weight wj for each job j 2 J, and a release date rj before which it cannot be scheduled; (ii) a set of m machines, each of which can process at most one job at any time; and (iii) an arbitrary set of positive values fp i; j g, where pi, j denotes the time to process job j on machine i. A schedule involves assigning jobs to machines and choosing an order in which they are processed. Let Cj denote the completion time of job j for a given schedule. The weighted completion time of a schedule is deP fined as j2J w j C j , and the goal is to compute a schedule that has the minimum weighted completion time. In the scheduling notation introduced by Graham et al. [7], a scheduling problem is denoted by a 3-tuple ˛jˇj, where ˛ denotes the machine environment, ˇ denotes the additional constraints on jobs, and denotes the objective function. In this article, we will be concerned with the ˛-values 1, P, R, and Rm, which respectively denote one machine, identical parallel machines (i. e., for a fixed job j and for each machine i, pi, j equals a value pj that is independent of i), unrelated machines (the pi, j ’s are dependent
on both job i and machine j), and a fixed number m (not part of the input) of unrelated machines. The field ˇ takes on the values rj , which indicates that the jobs have release dates, and the value pmtn, which indicates that preemption of jobs is permitted. Further, the value prec in the field ˇ indicates that the problem may involve precedence constraints between jobs, which poses further restrictions on P P the schedule. The field is either w j C j or C j , which denote total weighted and total (unweighted) completion times, respectively. Some of the simpler classes of the weighted completion time scheduling problems admit optimal polynomialP time solutions. They include the problem Pjj C j , for which the shortest-job-first strategy is optimal, the probP lem 1jj w j C j , for which Smith’s rule [13] (scheduling jobs in their nondecreasing order of p j /w j values) is opP timal, and the problem Rjj C j , which can be solved via matching techniques [2,9]. With th
Data Loading...
