[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

837.0. "Greedy scheduling" by CLT::GILBERT (Builder) Thu Mar 03 1988 17:19

    Here is a scheduling problem.  Suppose we have a set of tasks, and a set
    of n processors.  We'd like to schedule these tasks on the processors
    such that the time to completion of all the tasks minimized.  We know
    the amount of time that each task will consume.

    For example, given five tasks with times 5,5,3,3,3, and two processors,
    the optimal schedule would have one processor run 5+5, and the other
    will run 3+3+3.  The time to completion is 10 = max(5+5,3+3+3).

    Rather than determine an optimal schedule, a 'greedy' algorithm is used.
    Whenever a processor is idle, it chooses to run the longest remaining
    task.  Using the above example, we have:

	[      5      ][   3   ][   3   ]
	[      5      ][   3   ]

    The time to completion is 11.  The ratio between the Greedy schedule
    and the optimal schedule is 11/10.

    Letting F(n) be defined as the largest possible ratio on n processors,
    it's fairly easy to show that 1 < F(n) < 2, and we know 11/10 <= F(2).
    The question is, how bad (large) can the ratio be between the Greedy
    and optimal schedules?  Upper and/or lower bounds would be nice.
T.RTitleUserPersonal
Name
DateLines
837.1Conclusions & hand waving...CHOVAX::YOUNGBack from the Shadows Again,Thu Mar 03 1988 22:4041
    Several conclusions that I can see right away:
    
    Let the set Gn be any collection of numbers whose 'Greedy' scheduling
    on n processors results in a maximal ratio with the Optimal scheduling,
    (ie. Gn is any set which demonstrates F(n) ).
    
    1)  If the largest Element of a set to be scheduled is >= 1/2 the
    total sum of the set, then 'Greedy' scheduling will be equivilant
    to the Optimal schedule.  Therefore either Gn for some n does NOT
    have any element >= 1/2 the sum of Gn, OR F(n) = 1 for that n.
    Furthermore we can extend this to say that in cases where F(n) > 1
    then ( Max(Gn) < 1/n ).
    
    2)  The largest 'error' that the Greedy algorithim can make on a
    set to be scheduled is <= the smallest member of the set.
    
    3)  It is apparent that if the order of a set to be scheduled is
    <= n, then the Greedy algorithim is equivilant to the Optimal solution.
    It is also true, however, that the Greedy solution remains equivilant
    to the Optimal solution so long as ( m <= 2n ) where m is the number
    of elements to be scheduled.
    
    4)  Pulling 1, 2, & 3 together with .0 we can now conclude:
    
    	1 < F(n) < (1 + 1/(2n+1) )
    
    Which is pretty good.  Indeed I believe that I know the worst case
    solution for n=2:
    
    		{ 3, 3, 2, 2, 2 }
    
    Optimal:	< 3  3  >	=	6
    		< 2 2 2 >
    
    Greedy:	< 3  2 >	=	7
    		< 3  2 2 >

    If correct this means that F(n) = 1+1/7.  Since 1 + 1/(2n+1) = 1+1/5
    Then : 1 < 1+1/7 < 1+1/5 does confirm the theory.

    --  Barry
837.2CLT::GILBERTBuilderFri Mar 04 1988 16:5825
    I'm not sure I agree.  Consider:

	[ 1 + (2n-2)/n   ][      1    ][     1     ]
	[ 1 + (2n-3)/n  ][   1 + 1/n  ]
		...
	[ 1 + (n)/n    ][ 1 + (n-2)/n ]
	[ 1 + (n-1)/n ][ 1 + (n-1)/n  ]

    Versus:
	[ 1 + (2n-2)/n   ][   1 + 1/n  ]
	[ 1 + (2n-3)/n  ][   1 + 2/n   ]
		...
	[ 1 + (n)/n    ][ 1 + (n-1)/n  ]
	[ 1 + (n-1)/n ][   1    ][  1  ]

    This gives a ratio of (5n-2)/(4n-1).

    For example, (scaling up to give integers)

	4, 2, 2		vs	4, 3		=>	8/7
	3, 3			3, 2, 2

	7, 3, 3		vs	7, 4		=>	13/11
	6, 4			6, 5
	5, 5			5, 3, 3
837.3CLT::GILBERTBuilderMon Mar 07 1988 13:4521
    I've improved the bound to F(n) >= (4n-1)/(3n).  The first few examples
    (from which the pattern should be apparent) follow.  I believe this gives
    the worst ratio, but am looking for a proof.

	3 2 2	vs	3 3
	3 2		2 2 2

	5 3 3	vs	5 4
	5 3		5 4
	4 4		3 3 3

	7 4 4	vs	7 5
	7 4		7 5
	6 5		6 6
	6 5		4 4 4

	9 5 5	vs	9 6
	9 5		9 6
	8 6		8 7
	8 6		8 7
	7 7		5 5 5
837.4Ooops, again...PLDVS2::YOUNGBack from the Shadows Again,Mon Mar 07 1988 15:5432
    re .2:
    
    I realized after I entered it that I had made a mistake in .1. 
    (4) is the only one that is wrong, I keep getting my 'm's and 'n's 
    mixed up in this thing.
    
    However, (1),(2), and (3) are still correct.
    
    
    Summarizing:
    
    1)	Max(Gn)/Sum(Gn) < 1/n
    
    2)	Optimal_time(Gn) - Greedy_time(Gn) <= Min(Gn)
    
    3)	Order(Gn) >= ( 2n + 1 )

    Prove:
    
    	F(n)  =  (4n - 1)/(3n)		( ?? )

    Where:
    
    n	-  Number of processors
    F(n)-  Maximum ratio of greedy scheduling time to optimal scheduling
    		time for n processors.
    Gn	-  A set that demonstrates F(n)
    
    
    --  Barry
    
    ps.  Does anyone know if this is a 'solved' problem?  
837.5CLT::GILBERTBuilderTue Mar 08 1988 14:1824
>   2)  The largest 'error' that the Greedy algorithim can make on a
>   set to be scheduled is <= the smallest member of the set.

    Suppose that the optimal schedule has a little bit of 'slack' in
    it -- that is, not all of the processors finish simultaneously.
    Then a tiny additional task can be added (to fill part of this
    slack) without affecting either the Greedy or Optimal schedule.
    But somehow the 'error' must be larger than this.

    You can show that there *exists* a Gn with this property that gives
    a maximal ratio -- just the Greedy schedule for a given Gn, and
    remove any tasks that were started after the start of the (longest)
    task that determines the overall time of that schedule.


    Let T be a collection of numbers with 'error' <= the smallest number in T.
    Calling the smallest number 'b', we have:

	Greedy(T) <= (Sum(T) + (n-1)b)/n, and
	Optimal(T) >= Sum(T)/n.

    So that:

	Greedy(T)/Optimal <= (Sum(T) + (n-1)b)/Sum(T) = 1 + b(n-1)/Sum(T)