CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about |Store| Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Scheduling Algorithm"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange College math Topic #458
Reading Topic #458
jmitchem
Member since Jun-14-04
Jun-14-04, 02:00 PM (EST)
Click to EMail jmitchem Click to send private message to jmitchem Click to view user profileClick to add this user to your buddy list  
"Scheduling Algorithm"
 
   As seen on:
https://www.cut-the-knot.org/Curriculum/Combinatorics/CriticalPath.shtml

There is an applet which determines an optimal schedule for a list of tasks based on a list of task priorities.

There is no information on the algorithm to do this, and I am interested in learning how that is done. Building the network diagram is a highly documented topic, but finding any information on converting the tasks to a schedule with finite resources to perform the task has been difficult.

I would like to be pointed either to the actual algorithm, code or any other papers that address this issue.

My guess is that for each item in the priority list, every item in the critical path to that task is added to the queue for the active resource. The active resource is selected by comparing the lengths of scheduled tasks and choosing the shortest.

Any help is appreciated.

Jonathan Mitchem
Coop Engineer
Carrier Networks
ADTRAN


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1287 posts
Jun-14-04, 08:49 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
1. "RE: Scheduling Algorithm"
In response to message #0
 
   >As seen on:
>https://www.cut-the-knot.org/Curriculum/Combinatorics/CriticalPath.shtml
>
>There is an applet which determines an optimal schedule for
>a list of tasks based on a list of task priorities.

The result is not necessarily an optimal schedule.

>
>There is no information on the algorithm to do this, and I
>am interested in learning how that is done. Building the
>network diagram is a highly documented topic, but finding
>any information on converting the tasks to a schedule with
>finite resources to perform the task has been difficult.

The applet has been written for

P. Tannenbaum, Excursions in Modern Mathematics, Prentice-Hall, 2004 (5th edition)

The algorithm is also described in

For All Practical Purposes by COMAP, 2001 (5th edition)

>I would like to be pointed either to the actual algorithm,
>code or any other papers that address this issue.
>
>My guess is that for each item in the priority list, every
>item in the critical path to that task is added to the queue
>for the active resource. The active resource is selected by
>comparing the lengths of scheduled tasks and choosing the
>shortest.

It is simpler. The tasks could be in one of four states: ineligible, ready, in execution, completed. Whenever a processor becomes available, the algorithm selects the first of the ready tasks and puts it in execution on that processor. For a given graph, the resulting schedule may (and probably will) depend on the priority list.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
jmitchem
Member since Jun-14-04
Jun-16-04, 09:58 AM (EST)
Click to EMail jmitchem Click to send private message to jmitchem Click to view user profileClick to add this user to your buddy list  
2. "RE: Scheduling Algorithm"
In response to message #1
 
   Thank you.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

66388638