IBM Journal of Research and Development
IBM Skip to main content
  Home     Products & services     Support & downloads     My account  

  Select a country  
Journals Home  
  Systems Journal  
Journal of Research
and Development
    Current Issue  
    Recent Issues  
    Papers in Progress  
    Recent publications  
    Author's Guide  
  Contact Us  
  Related links:  
     IBM Research  

IBM Journal of Research and Development  
Volume 21, Number 3, Page 273 (1977)
Analysis of Positive Photoresists
  Full article: arrowPDF   arrowCopyright info


Improving the Computation of Lower Bounds for Optimal Schedules

by T. Lang, E. B. Fernandez
Ways of decreasing the number of operations needed to compute the lower bounds of optimal schedules, by reducing the number of time intervals that must be considered, are presented. The bounds apply to a system of identical processors executing a partially ordered set of tasks, with known execution times, using a non-preemptive scheduling strategy. In one approach we find that the required number of intervals depends on the graph. In our other approach, which subsumes the first, the number of intervals is decreased to at most min [D2/2, n2], where D is the deadline to complete the tasks and n is the number of tasks. The actual number of intervals for a particular graph can be considerably smaller than this worst case.
Related Subjects: Algorithms; Mathematics