Scheduling activities
What is meant by scheduling (activities)?
-
Scheduling activities is the process of assigning workers (resources) to activities within a project
-
The two types of problem that arise involve
-
finding the minimum number of workers such that a project can be completed in its minimum project duration
-
The minimum project duration is also called the critical time of the project
-
-
finding the (new) minimum project duration given that their are constraints (restrictions) on the maximum number of workers available at any given time
-
-
In harder problems, certain workers may only be capable of carrying out particular activities
What assumptions are made in scheduling?
-
In scheduling activities the following assumptions are made
-
each activity requires only one worker
-
or one team of workers, i.e. one resource
-
-
an activity is assigned the first available worker
-
if there is a choice of activities to assign a worker to choose the activity with the lower late end time
-
i.e. the lower late event time at the activity end node
-
-
a worker can only work on one activity at a time
-
once a worker has started an activity, that activity needs to be completed
-
How do I schedule activities for a project that requires the minimum number of workers?
-
For this type of problem, the critical time of the project cannot change
-
the critical activities cannot be delayed
-
one worker (resource) will complete all the critical activities
-
-
Using a Gantt chart and considering the non-critical activities
-
non-critical activities can be delayed, but only within their (total) float times
-
i.e. early start times can be delayed but late end times cannot
-
-
visualise each activity as its bar being able to ‘slide’ (back and forth) within its box (solid and dotted)
-
aim for as few overlaps between activities as possible
-
-
activities can then be combined into as few rows as possible
-
by placing them ‘back-to-back’
-
i.e. where possible activities should start immediately after others end
-
-
each row on the (reduced) Gantt chart will then be completed by one worker
-
i.e. the number of rows is the number of workers
-
-
-
Remember that the precedence of activities needs to be maintained
-
e.g. Activity H, say, cannot move so it starts after activity I, as activity I depends on H being completed first
-
i.e. H is an immediate predecessor of I
-
-
What is the lower bound for the (minimum) number of workers?
-
The lower bound for the number of workers needed such that a project is completed in its minimum project duration is the smallest integer that satisfies
format('truetype')%3Bfont-weight%3Anormal%3Bfont-style%3Anormal%3B%7D%3C%2Fstyle%3E%3C%2Fdefs%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%2223.5%22%20y%3D%2230%22%3ELower%3C%2Ftext%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%2273.5%22%20y%3D%2230%22%3Ebound%3C%2Ftext%3E%3Ctext%20font-family%3D%22math1070c425fd005e11aec1a90706d%22%20font-size%3D%2216%22%20text-anchor%3D%22middle%22%20x%3D%22108.5%22%20y%3D%2230%22%3E%26%23x2265%3B%3C%2Ftext%3E%3Cline%20stroke%3D%22%23000%22%20stroke-linecap%3D%22square%22%20stroke-width%3D%221%22%20x1%3D%22122.5%22%20x2%3D%22315.5%22%20y1%3D%2223.5%22%20y2%3D%2223.5%22%2F%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%22146.5%22%20y%3D%2216%22%3ETotal%3C%2Ftext%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%22185.5%22%20y%3D%2216%22%3Etime%3C%2Ftext%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%22212.5%22%20y%3D%2216%22%3Eof%3C%2Ftext%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%22233.5%22%20y%3D%2216%22%3Eall%3C%2Ftext%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%22278.5%22%20y%3D%2216%22%3Eactivities%3C%2Ftext%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%22160.5%22%20y%3D%2241%22%3EMinimum%3C%2Ftext%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%22225.5%22%20y%3D%2241%22%3Eproject%3C%2Ftext%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%22284.5%22%20y%3D%2241%22%3Eduration%3C%2Ftext%3E%3C%2Fsvg%3E){kind=small}
-
It is not always possible to schedule activities such that the lower bound can be met
How do I schedule activities for a project that has a maximum number of workers?
-
For this type of problem, there will be a maximum number of workers available at any point in time
-
this cannot be exceeded, even if it requires activities to be delayed and the project’s critical time increased
-
-
Using a Gantt chart
-
find the minimum number of workers required to complete the project in its critical time
-
the Gantt chart would have already been largely reduced
-
do this using the process above
-
-
now consider how any activity (critical or non-critical) can be delayed such that
-
at any time the Gantt chart uses no more rows than the (maximum) number of workers available
-
-
-
As in the first type of problem, the precedence of activities needs to be maintained
-
e.g. Activity H, say, cannot move so it starts after activity I, as activity I depends on H being completed first
-
i.e. H is an immediate predecessor of I
-
-
Examiner Tips and Tricks
-
Practice scheduling questions as exam preparation
-
there is not an algorithm as such and experience is the best way to become familiar with what to look for
-
Worked Example
A precedence table and Gantt chart for a project are shown below. Each activity requires one worker and times are given in days.
|
Activity |
Immediately preceding activities |
|
A |
– |
|
B |
– |
|
C |
A |
|
D |
B |
|
E |
A, D |
|
F |
B |
|
G |
C |
|
H |
C |
|
I |
G, H |
|
J |
E, F |
a) Find the lower bound for the minimum number of workers required to complete the project within its critical time.
<img alt=”table row cell fraction numerator Total space time space of space all space activities over denominator Minimum space project space duration end fraction end cell equals cell fraction numerator 23 plus 4 plus 3 plus 7 plus 6 plus 4 plus 4 over denominator 23 end fraction end cell row blank equals cell 51 over 23 end cell row blank equals cell 2.217 space… end cell end table” data-mathml='<math ><semantics><mtable columnspacing=”0px” columnalign=”right center left”><mtr><mtd><mfrac><mrow><mi>Total</mi><mo> </mo><mi>time</mi><mo> </mo><mi>of</mi><mo> </mo><mi>all</mi><mo> </mo><mi>activities</mi></mrow><mrow><mi>Minimum</mi><mo> </mo><mi>project</mi><mo> </mo><mi>duration</mi></mrow></mfrac></mtd><mtd><mo>=</mo></mtd><mtd><mfrac><mrow><mn>23</mn><mo>+</mo><mn>4</mn><mo>+</mo><mn>3</mn><mo>+</mo><mn>7</mn><mo>+</mo><mn>6</mn><mo>+</mo><mn>4</mn><mo>+</mo><mn>4</mn></mrow><mn>23</mn></mfrac></mtd></mtr><mtr><mtd/><mtd><mo>=</mo></mtd><mtd><mfrac><mn>51</mn><mn>23</mn></mfrac></mtd></mtr><mtr><mtd/><mtd><mo>=</mo></mtd><mtd><mn>2</mn><mo>.</mo><mn>217</mn><mo> </mo><mo>.</mo><mo>.</mo><mo>.</mo></mtd></mtr></mtable><annotation encoding=”application/vnd.wiris.mtweb-params+json”>{“language”:”en”,”fontFamily”:”Times New Roman”,”fontSize”:”18″,”autoformat”:true}</annotation></semantics></math>’ data-type=”working” height=”124″ role=”math” src=”data:image/svg+xml;charset=utf8,%3Csvg%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F2000%2Fsvg%22%20xmlns%3Awrs%3D%22http%3A%2F%2Fwww.wiris.com%2Fxml%2Fmathml-extension%22%20height%3D%22124%22%20width%3D%22398%22%20wrs%3Abaseline%3D%2261%22%3E%3C!–MathML%3A%20%3Cmath%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F1998%2FMath%2FMathML%22%3E%3Cmtable%20columnalign%3D%22right%20center%20left%22%20columnspacing%3D%220px%22%3E%3Cmtr%3E%3Cmtd%3E%3Cmfrac%20mathcolor%3D%22%23000%22%3E%3Cmrow%3E%3Cmi%3ETotal%3C%2Fmi%3E%3Cmo%3E%26%23xA0%3B%3C%2Fmo%3E%3Cmi%3Etime%3C%2Fmi%3E%3Cmo%3E%26%23xA0%3B%3C%2Fmo%3E%3Cmi%3Eof%3C%2Fmi%3E%3Cmo%3E%26%23xA0%3B%3C%2Fmo%3E%3Cmi%3Eall%3C%2Fmi%3E%3Cmo%3E%26%23xA0%3B%3C%2Fmo%3E%3Cmi%3Eactivities%3C%2Fmi%3E%3C%2Fmrow%3E%3Cmrow%3E%3Cmi%3EMinimum%3C%2Fmi%3E%3Cmo%3E%26%23xA0%3B%3C%2Fmo%3E%3Cmi%3Eproject%3C%2Fmi%3E%3Cmo%3E%26%23xA0%3B%3C%2Fmo%3E%3Cmi%3Eduration%3C%2Fmi%3E%3C%2Fmrow%3E%3C%2Fmfrac%3E%3C%2Fmtd%3E%3Cmtd%3E%3Cmo%20mathcolor%3D%22%23000%22%3E%3D%3C%2Fmo%3E%3C%2Fmtd%3E%3Cmtd%3E%3Cmfrac%20mathcolor%3D%22%23000%22%3E%3Cmrow%3E%3Cmn%3E23%3C%2Fmn%3E%3Cmo%3E%2B%3C%2Fmo%3E%3Cmn%3E4%3C%2Fmn%3E%3Cmo%3E%2B%3C%2Fmo%3E%3Cmn%3E3%3C%2Fmn%3E%3Cmo%3E%2B%3C%2Fmo%3E%3Cmn%3E7%3C%2Fmn%3E%3Cmo%3E%2B%3C%2Fmo%3E%3Cmn%3E6%3C%2Fmn%3E%3Cmo%3E%2B%3C%2Fmo%3E%3Cmn%3E4%3C%2Fmn%3E%3Cmo%3E%2B%3C%2Fmo%3E%3Cmn%3E4%3C%2Fmn%3E%3C%2Fmrow%3E%3Cmn%3E23%3C%2Fmn%3E%3C%2Fmfrac%3E%3C%2Fmtd%3E%3C%2Fmtr%3E%3Cmtr%3E%3Cmtd%2F%3E%3Cmtd%3E%3Cmo%20mathcolor%3D%22%23000%22%3E%3D%3C%2Fmo%3E%3C%2Fmtd%3E%3Cmtd%3E%3Cmfrac%20mathcolor%3D%22%23000%22%3E%3Cmn%3E51%3C%2Fmn%3E%3Cmn%3E23%3C%2Fmn%3E%3C%2Fmfrac%3E%3C%2Fmtd%3E%3C%2Fmtr%3E%3Cmtr%3E%3Cmtd%2F%3E%3Cmtd%3E%3Cmo%20mathcolor%3D%22%23000%22%3E%3D%3C%2Fmo%3E%3C%2Fmtd%3E%3Cmtd%3E%3Cmn%20mathcolor%3D%22%23000%22%3E2%3C%2Fmn%3E%3Cmo%20mathcolor%3D%22%23000%22%3E.%3C%2Fmo%3E%3Cmn%20mathcolor%3D%22%23000%22%3E217%3C%2Fmn%3E%3Cmo%20mathcolor%3D%22%23000%22%3E%26%23xA0%3B%3C%2Fmo%3E%3Cmo%20mathcolor%3D%22%23000%22%3E.%3C%2Fmo%3E%3Cmo%20mathcolor%3D%22%23000%22%3E.%3C%2Fmo%3E%3Cmo%20mathcolor%3D%22%23000%22%3E.%3C%2Fmo%3E%3C%2Fmtd%3E%3C%2Fmtr%3E%3C%2Fmtable%3E%3C%2Fmath%3E–%3E%3Cdefs%3E%3Cstyle%20type%3D%22text%2Fcss%22%3E%40font-face%7Bfont-family%3A’math1b5dc6aeb84bcea29a76d1e9d00’%3Bsrc%3Aurl(data%3Afont%2Ftruetype%3Bcharset%3Dutf-8%3Bbase64%2CAAEAAAAMAIAAAwBAT1MvMi7iBBMAAADMAAAATmNtYXDEvmKUAAABHAAAAERjdnQgDVUNBwAAAWAAAAA6Z2x5ZoPi2VsAAAGcAAABcWhlYWQQC2qxAAADEAAAADZoaGVhCGsXSAAAA0gAAAAkaG10eE2rRkcAAANsAAAAEGxvY2EAHTwYAAADfAAAABRtYXhwBT0FPgAAA5AAAAAgbmFtZaBxlY4AAAOwAAABn3Bvc3QB9wD6AAAFUAAAACBwcmVwa1uragAABXAAAAAUAAADSwGQAAUAAAQABAAAAAAABAAEAAAAAAAAAQEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAgICAAAAAg1UADev96AAAD6ACWAAAAAAACAAEAAQAAABQAAwABAAAAFAAEADAAAAAIAAgAAgAAACsALgA9%2F%2F8AAAArAC4APf%2F%2F%2F9b%2F1P%2FGAAEAAAAAAAAAAAAAAVQDLACAAQAAVgAqAlgCHgEOASwCLABaAYACgACgANQAgAAAAAAAAAArAFUAgACrANUBAAErAAcAAAACAFUAAAMAA6sAAwAHAAAzESERJSERIVUCq%2F2rAgD%2BAAOr%2FFVVAwAAAQCAAFUC1QKrAAsASQEYsgwBARQTELEAA%2FaxAQT1sAo8sQMF9bAIPLEFBPWwBjyxDQPmALEAABMQsQEG5LEBARMQsAU8sQME5bELBfWwBzyxCQTlMTATIREzESEVIREjESGAAQBVAQD%2FAFX%2FAAGrAQD%2FAFb%2FAAEAAAEAIAAAAKAAgAADAC8YAbAEELAD1LADELAC1LADELAAPLACELABPACwBBCwA9SwAxCwAjywABCwATwwMTczFSMggICAgAACAIAA6wLVAhUAAwAHAGUYAbAIELAG1LAGELAF1LAIELAB1LABELAA1LAGELAHPLAFELAEPLABELACPLAAELADPACwCBCwBtSwBhCwB9SwBxCwAdSwARCwAtSwBhCwBTywBxCwBDywARCwADywAhCwAzwxMBMhNSEdASE1gAJV%2FasCVQHAVdVVVQAAAAABAAAAAQAA1XjOQV8PPPUAAwQA%2F%2F%2F%2F%2F9Y6E3P%2F%2F%2F%2F%2F1joTcwAA%2FyAEgAOrAAAACgACAAEAAAAAAAEAAAPo%2F2oAABdwAAD%2FtgSAAAEAAAAAAAAAAAAAAAAAAAAEA1IAVQNWAIAAyAAgA1YAgAAAAAAAAAAoAAAAoQAAAOcAAAFxAAEAAAAEAF4ABQAAAAAAAgCABAAAAAAABAAA3gAAAAAAAAAVAQIAAAAAAAAAAQASAAAAAAAAAAAAAgAOABIAAAAAAAAAAwAwACAAAAAAAAAABAASAFAAAAAAAAAABQAWAGIAAAAAAAAABgAJAHgAAAAAAAAACAAcAIEAAQAAAAAAAQASAAAAAQAAAAAAAgAOABIAAQAAAAAAAwAwACAAAQAAAAAABAASAFAAAQAAAAAABQAWAGIAAQAAAAAABgAJAHgAAQAAAAAACAAcAIEAAwABBAkAAQASAAAAAwABBAkAAgAOABIAAwABBAkAAwAwACAAAwABBAkABAASAFAAAwABBAkABQAWAGIAAwABBAkABgAJAHgAAwABBAkACAAcAIEATQBhAHQAaAAgAEYAbwBuAHQAUgBlAGcAdQBsAGEAcgBNAGEAdABoAHMAIABGAG8AcgAgAE0AbwByAGUAIABNAGEAdABoACAARgBvAG4AdABNAGEAdABoACAARgBvAG4AdABWAGUAcgBzAGkAbwBuACAAMQAuADBNYXRoX0ZvbnQATQBhAHQAaABzACAARgBvAHIAIABNAG8AcgBlAAADAAAAAAAAAfQA%2BgAAAAAAAAAAAAAAAAAAAAAAAAAAuQcRAACNhRgAsgAAABUUE7EAAT8%3D)format(‘truetype’)%3Bfont-weight%3Anormal%3Bfont-style%3Anormal%3B%7D%3C%2Fstyle%3E%3C%2Fdefs%3E%3Cline%20stroke%3D%22%23000%22%20stroke-linecap%3D%22square%22%20stroke-width%3D%221%22%20×1%3D%222.5%22%20×2%3D%22195.5%22%20y1%3D%2223.5%22%20y2%3D%2223.5%22%2F%3E%3Ctext%20fill%3D%22%23000%22%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%2226.5%22%20y%3D%2216%22%3ETotal%3C%2Ftext%3E%3Ctext%20fill%3D%22%23000%22%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%2265.5%22%20y%3D%2216%22%3Etime%3C%2Ftext%3E%3Ctext%20fill%3D%22%23000%22%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%2292.5%22%20y%3D%2216%22%3Eof%3C%2Ftext%3E%3Ctext%20fill%3D%22%23000%22%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20text-anchor%3D%22middle%22%20x%3D%22113.5%2
Responses