Author | Conference | Journal | Organization | Year | DOI
Look for results that meet for the following criteria:
Academic
Publications
Online hierarchical scheduling: An approach using mathematical programming

Online hierarchical scheduling: An approach using mathematical programming,10.1016/j.tcs.2009.08.014,Theoretical Computer Science,Zhiyi Tan,An Zhang

Edit
Online hierarchical scheduling: An approach using mathematical programming   (Citations: 2)
BibTex | RIS | RefWorks Download
This paper considers an online hierarchical scheduling problem on parallel identical machines. We are given a set of m machines and a sequence of jobs. Each machine has a different hierarchy, and each job also has a hierarchy associated with it. A job can be assigned to a machine only if its hierarchy is no less than that of the machine. The objective is to minimize the makespan, i.e., the maximum load of all machines. Two models are studied in the paper. For the fractional model, we present an improved algorithm and lower bounds. Both the algorithm and the lower bound are based on solutions of mathematical programming. For any given m, our algorithm is optimal by numerical calculation. For the integral model, we present both a general algorithm for any m, and an improved algorithm with better competitive ratios of 2.333 and 2.610 for m=4 and 5, respectively.
Journal: Theoretical Computer Science - TCS , vol. 412, no. 3, pp. 246-256, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
More »
    • ...Tan and Zhang (2010b) give a slight improvement of the algorithm of Bar-Noy et al. (2001)...
    • ...Tan and Zhang (2010b) give a more effective LP algorithm for the fractional model, withabettercompetitiveratiothanthealgorithmofBar-Noyetal.(2001)forallvalues of m .F orm = 4 and 5, they present improved algorithms with competitive ratios of 2.333 and 2.610, respectively...

    Kangbok Lee, et al. Makespan minimization in online scheduling with machine eligibility

Sort by:

Citations (2)

Share this on