We use cookies to improve your experience with our site.
Yi-Wei Jiang, Yong He. Semi-Online Algorithms for Scheduling with Machine Cost[J]. Journal of Computer Science and Technology, 2006, 21(6): 984-988.
Citation: Yi-Wei Jiang, Yong He. Semi-Online Algorithms for Scheduling with Machine Cost[J]. Journal of Computer Science and Technology, 2006, 21(6): 984-988.

Semi-Online Algorithms for Scheduling with Machine Cost

  • In this paper, we consider the following semi-online List Model problemwith known total size. We are given a sequence of independent jobs withpositive sizes, which must be assigned to be processed on machines. Nomachines are initially provided, and when a job is revealed thealgorithm has the option to purchase new machines. By normalizing alljob sizes and machine cost, we assume that the cost of purchasing onemachine is 1. We further know the total size of all jobs in advance. Theobjective is to minimize the sum of the makespan and the number ofmachines to be purchased. Both non-preemptive and preemptive versions areconsidered. For the non-preemptive version, we present a new lower bound6/5 which improves the known lower bound 1.161. For the preemptiveversion, we present an optimal semi-online algorithm with a competitiveratio of 1 in the case that the total size is not greater than 4, and analgorithm with a competitive ratio of 5/4 otherwise, while a lowerbound 1.0957 is also presented for general case.
  • loading

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return