{"id":9977,"date":"2023-10-25T18:47:59","date_gmt":"2023-10-25T18:47:59","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&p=9977"},"modified":"2025-08-29T20:55:52","modified_gmt":"2025-08-29T20:55:52","slug":"operations-and-supply-chain-learn-it-4","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/operations-and-supply-chain-learn-it-4\/","title":{"raw":"Operations and Supply Chain: Learn It 4","rendered":"Operations and Supply Chain: Learn It 4"},"content":{"raw":"

Scheduling Cont.<\/h2>\r\n

Adding an algorithm<\/h3>\r\n

Up until now, we have been creating schedules by guess-and-check, which works well enough for small schedules, but would not work well with dozens or hundreds of tasks. To create a more procedural approach, we might begin by somehow creating a\u00a0priority list<\/b>. Once we have a priority list, we can begin scheduling using that list and the\u00a0list processing algorithm<\/b>.<\/p>\r\n

\r\n

priority list<\/h3>\r\n

A priority list<\/strong> is a list of tasks given in the order in which we desire them to be completed.<\/p>\r\n

 <\/p>\r\n

The List Processing Algorithm<\/strong> turns a priority list into a schedule.<\/p>\r\n<\/section>\r\n

\r\n

How To: List Processing Algorithm<\/strong><\/p>\r\n

    \r\n\t
  1. On the digraph or priority list, circle all tasks that are ready, meaning that all prerequisite tasks have been completed.<\/li>\r\n\t
  2. Assign to each available processor, in order, the first ready task. Mark the task as in progress, perhaps by putting a single line through the task.<\/li>\r\n\t
  3. Move forward in time until a task is completed. Mark the task as completed, perhaps by crossing out the task. If any new tasks become ready, mark them as such.<\/li>\r\n\t
  4. Repeat until all tasks have been scheduled.<\/li>\r\n<\/ol>\r\n<\/section>\r\n
    \r\n[caption id=\"\" align=\"aligncenter\" width=\"324\"]\"A Figure 1. The complete digraph for car conversion[\/caption]\r\n<\/center>\r\n

     <\/p>\r\n

    Using our complete digraph for the car conversion we found earlier, let's schedule the tasks using the priority list below:<\/p>\r\n

    [latex]\\mathrm{T}_{1}, \\mathrm{T}_{3}, \\mathrm{T}_{4}, \\mathrm{T}_{5}, \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, \\mathrm{T}_{2}, \\mathrm{T}_{9}[\/latex]<\/p>\r\n

    Time 0<\/b>: Mark ready tasks.<\/p>\r\n

    Priority list: [latex]({\\mathrm{T}_{1}}), (\\mathrm{T}_{3}), (\\mathrm{T}_{4}), (\\mathrm{T}_{5}), \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, \\mathrm{T}_{2}, \\mathrm{T}_{9}[\/latex]<\/p>\r\n

    We assign the first task, [latex]\\mathrm{T}_{1}[\/latex] to the first processor, [latex]\\mathrm{P}_{1}[\/latex], and the second ready task, [latex]\\mathrm{T}_{3}[\/latex], to the second processor. Making those assignments, we mark those tasks as in progress:<\/p>\r\n

    Priority list: [latex]\\cancel{(\\mathrm{T}_{1})}, \\cancel{(\\mathrm{T}_{3})}, (\\mathrm{T}_{4}), (\\mathrm{T}_{5}), \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, \\mathrm{T}_{2}, \\mathrm{T}_{9}[\/latex]<\/p>\r\n

    Schedule up to here:<\/p>\r\n

    \r\n[caption id=\"\" align=\"aligncenter\" width=\"584\"]\"A Figure 2. Mark ready tasks in the schedules for the two processors[\/caption]\r\n<\/center>\r\n

     <\/p>\r\n

    We jump to the time when the next task completes, which is at time [latex]2[\/latex].<\/p>\r\n

    Time 2<\/b>: Both processors complete their tasks. We mark those tasks as complete. With Task [latex]1[\/latex] complete, Task [latex]2[\/latex] becomes ready:<\/p>\r\n

    Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, (\\mathrm{T}_{4}), (\\mathrm{T}_{5}), \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, (\\mathrm{T}_{2}), \\mathrm{T}_{9}[\/latex]<\/p>\r\n

    We assign the next ready task on the list, [latex]\\mathrm{T}_{4}[\/latex] to [latex]\\mathrm{P}_{1}[\/latex], and [latex]\\mathrm{T}_{5}[\/latex] to [latex]\\mathrm{P}_{2}[\/latex].<\/p>\r\n

    Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, \\cancel{(\\mathrm{T}_{4})}, \\cancel{(\\mathrm{T}_{5})}, \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, (\\mathrm{T}_{2}), \\mathrm{T}_{9}[\/latex]<\/p>\r\n

    \r\n[caption id=\"\" align=\"aligncenter\" width=\"591\"]\"Timeline Figure 3. Put in new tasks into the schedules of the two processors[\/caption]\r\n<\/center>\r\n

     <\/p>\r\n

    Time 3<\/b>: Processor 1 has completed [latex]\\mathrm{T}_{4}[\/latex]. Completing [latex]\\mathrm{T}_{4}[\/latex] does not make any other tasks ready (note that all the rest require that [latex]\\mathrm{T}_{2}[\/latex]\u00a0be completed first).<\/p>\r\n

    Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, \\xcancel{(\\mathrm{T}_{4})}, \\cancel{(\\mathrm{T}_{5})}, \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, (\\mathrm{T}_{2}), \\mathrm{T}_{9}[\/latex]<\/p>\r\n

    Since the next three tasks are not yet ready, we assign the next ready task, [latex]\\mathrm{T}_{2}[\/latex] to [latex]\\mathrm{P}_{1}[\/latex].<\/p>\r\n

    Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, \\xcancel{(\\mathrm{T}_{4})}, \\xcancel{(\\mathrm{T}_{5})}, \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, \\cancel{(\\mathrm{T}_{2})}, \\mathrm{T}_{9}[\/latex]<\/p>\r\n

    \r\n[caption id=\"\" align=\"aligncenter\" width=\"582\"]\"Timeline Figure 4. Assign the next ready task, since the three tasks are not yet ready[\/caption]\r\n<\/center>\r\n

     <\/p>\r\n

    Time 3.5<\/b>: Processor [latex]1[\/latex] has completed [latex]\\mathrm{T}_{2}[\/latex]. Completing [latex]\\mathrm{T}_{2}[\/latex] causes [latex]\\mathrm{T}_{6}[\/latex] and [latex]\\mathrm{T}_{7}[\/latex] to become ready. We assign [latex]\\mathrm{T}_{6}[\/latex] to [latex]\\mathrm{P}_{1}[\/latex].<\/p>\r\n

    Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, \\xcancel{(\\mathrm{T}_{4})}, \\xcancel{(\\mathrm{T}_{5})}, \\cancel{(\\mathrm{T}_{6})}, (\\mathrm{T}_{7}), \\mathrm{T}_{8}, \\xcancel{(\\mathrm{T}_{2})}, \\mathrm{T}_{9}[\/latex]<\/p>\r\n

    \r\n[caption id=\"\" align=\"aligncenter\" width=\"577\"]\"Timeline Figure 5. Assign the next task in the first processor schedule[\/caption]\r\n<\/center>\r\n

     <\/p>\r\n

    Time 4<\/b>: Both processors complete their tasks. The completion of [latex]\\mathrm{T}_{5}[\/latex] allows [latex]\\mathrm{T}_{8}[\/latex] to become ready. We assign [latex]\\mathrm{T}_{7}[\/latex] to [latex]\\mathrm{P}_{1}[\/latex] and [latex]\\mathrm{T}_{8}[\/latex]\u00a0to [latex]\\mathrm{P}_{2}[\/latex].<\/p>\r\n

    Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, \\xcancel{(\\mathrm{T}_{4})}, \\xcancel{(\\mathrm{T}_{5})}, \\xcancel{(\\mathrm{T}_{6})}, \\cancel{(\\mathrm{T}_{7})}, \\cancel{(\\mathrm{T}_{8})}, \\xcancel{(\\mathrm{T}_{2})}, \\mathrm{T}_{9}[\/latex]<\/p>\r\n

    \r\n[caption id=\"\" align=\"aligncenter\" width=\"580\"]\"Timeline Figure 6. After both processors complete their tasks, add new tasks in the schedules[\/caption]\r\n<\/center>\r\n

     <\/p>\r\n

    Time 4.5<\/b>: Both processors complete their tasks. [latex]\\mathrm{T}_{9}[\/latex] becomes ready, and is assigned to [latex]\\mathrm{P}_{1}[\/latex]. There is no ready task for [latex]\\mathrm{P}_{2}[\/latex] to work on, so [latex]\\mathrm{P}_{2}[\/latex]\u00a0idles.<\/p>\r\n

    Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, \\xcancel{(\\mathrm{T}_{4})}, \\xcancel{(\\mathrm{T}_{5})}, \\xcancel{(\\mathrm{T}_{6})}, \\xcancel{(\\mathrm{T}_{7})}, \\xcancel{(\\mathrm{T}_{8})}, \\xcancel{(\\mathrm{T}_{2})}, \\cancel{(\\mathrm{T}_{9})}[\/latex]<\/p>\r\n

    \r\n[caption id=\"\" align=\"aligncenter\" width=\"583\"]\"Timeline Figure 7. After both processors complete their tasks again, add in new tasks[\/caption]\r\n<\/center>\r\n

     <\/p>\r\n

    With the last task completed, we have a completed schedule, with finishing time [latex]5.5[\/latex] days.<\/p>\r\n

    \r\n

    Using the digraph below, create a schedule using the priority list with two processors:<\/p>\r\n

    [latex]\\mathrm{T}_{1}, \\mathrm{T}_{2}, \\mathrm{T}_{3}, \\mathrm{T}_{4}, \\mathrm{T}_{5}, \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, \\mathrm{T}_{9}[\/latex]<\/p>\r\n

    \"Diagram<\/center>[reveal-answer q=\"4331\"]Show Solution[\/reveal-answer] [hidden-answer a=\"4331\"]\r\n\r\n

    Time [latex]0[\/latex]: Tasks [latex]1, 4,[\/latex] and [latex]7[\/latex] are ready. Assign Tasks [latex]1[\/latex] and [latex]4[\/latex].<\/p>\r\n

    Time [latex]9[\/latex]: Task [latex]4[\/latex] completes. Only task [latex]7[\/latex] is ready; assign task [latex]7[\/latex].<\/p>\r\n

    Time [latex]10[\/latex]: Task [latex]1[\/latex] completes. Task [latex]2[\/latex] now ready. Assign task [latex]2[\/latex].<\/p>\r\n

    Time [latex]17[\/latex]: Task [latex]2[\/latex] completes. Nothing is ready. Processor [latex]1[\/latex] idles.<\/p>\r\n

    Time [latex]22[\/latex]: Task [latex]7[\/latex] completes. Tasks [latex]5[\/latex] and [latex]8[\/latex] are ready. Assign tasks [latex]5[\/latex] and [latex]8[\/latex].<\/p>\r\n

    Time [latex]26[\/latex]: Task [latex]8[\/latex] completes. Task [latex]9[\/latex] is ready. Assign task [latex]9[\/latex].<\/p>\r\n

    Time [latex]27[\/latex]: Task [latex]5[\/latex] completes. Tasks [latex]3[\/latex] and [latex]6[\/latex] are ready. Assign task [latex]3[\/latex].<\/p>\r\n

    Time [latex]31[\/latex]: Task [latex]3[\/latex] completes. Assign task [latex]6[\/latex].<\/p>\r\n

    Time [latex]35[\/latex]: Everything is done. Finishing time is [latex]35[\/latex] for this schedule.<\/p>\r\n

    \"Timeline<\/center>[\/hidden-answer]<\/section>\r\n

    There are other algorithms that can be used to create the priority list including, the decreasing time algorithm, the critical path algorithm, and the backflow algorithm. We will explore these algorithms in the Apply It section.\u00a0<\/p>","rendered":"

    Scheduling Cont.<\/h2>\n

    Adding an algorithm<\/h3>\n

    Up until now, we have been creating schedules by guess-and-check, which works well enough for small schedules, but would not work well with dozens or hundreds of tasks. To create a more procedural approach, we might begin by somehow creating a\u00a0priority list<\/b>. Once we have a priority list, we can begin scheduling using that list and the\u00a0list processing algorithm<\/b>.<\/p>\n

    \n

    priority list<\/h3>\n

    A priority list<\/strong> is a list of tasks given in the order in which we desire them to be completed.<\/p>\n

     <\/p>\n

    The List Processing Algorithm<\/strong> turns a priority list into a schedule.<\/p>\n<\/section>\n

    \n

    How To: List Processing Algorithm<\/strong><\/p>\n

      \n
    1. On the digraph or priority list, circle all tasks that are ready, meaning that all prerequisite tasks have been completed.<\/li>\n
    2. Assign to each available processor, in order, the first ready task. Mark the task as in progress, perhaps by putting a single line through the task.<\/li>\n
    3. Move forward in time until a task is completed. Mark the task as completed, perhaps by crossing out the task. If any new tasks become ready, mark them as such.<\/li>\n
    4. Repeat until all tasks have been scheduled.<\/li>\n<\/ol>\n<\/section>\n
      \n
      \"A
      Figure 1. The complete digraph for car conversion<\/figcaption><\/figure>\n<\/div>\n

       <\/p>\n

      Using our complete digraph for the car conversion we found earlier, let’s schedule the tasks using the priority list below:<\/p>\n

      [latex]\\mathrm{T}_{1}, \\mathrm{T}_{3}, \\mathrm{T}_{4}, \\mathrm{T}_{5}, \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, \\mathrm{T}_{2}, \\mathrm{T}_{9}[\/latex]<\/p>\n

      Time 0<\/b>: Mark ready tasks.<\/p>\n

      Priority list: [latex]({\\mathrm{T}_{1}}), (\\mathrm{T}_{3}), (\\mathrm{T}_{4}), (\\mathrm{T}_{5}), \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, \\mathrm{T}_{2}, \\mathrm{T}_{9}[\/latex]<\/p>\n

      We assign the first task, [latex]\\mathrm{T}_{1}[\/latex] to the first processor, [latex]\\mathrm{P}_{1}[\/latex], and the second ready task, [latex]\\mathrm{T}_{3}[\/latex], to the second processor. Making those assignments, we mark those tasks as in progress:<\/p>\n

      Priority list: [latex]\\cancel{(\\mathrm{T}_{1})}, \\cancel{(\\mathrm{T}_{3})}, (\\mathrm{T}_{4}), (\\mathrm{T}_{5}), \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, \\mathrm{T}_{2}, \\mathrm{T}_{9}[\/latex]<\/p>\n

      Schedule up to here:<\/p>\n

      \n
      \"A
      Figure 2. Mark ready tasks in the schedules for the two processors<\/figcaption><\/figure>\n<\/div>\n

       <\/p>\n

      We jump to the time when the next task completes, which is at time [latex]2[\/latex].<\/p>\n

      Time 2<\/b>: Both processors complete their tasks. We mark those tasks as complete. With Task [latex]1[\/latex] complete, Task [latex]2[\/latex] becomes ready:<\/p>\n

      Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, (\\mathrm{T}_{4}), (\\mathrm{T}_{5}), \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, (\\mathrm{T}_{2}), \\mathrm{T}_{9}[\/latex]<\/p>\n

      We assign the next ready task on the list, [latex]\\mathrm{T}_{4}[\/latex] to [latex]\\mathrm{P}_{1}[\/latex], and [latex]\\mathrm{T}_{5}[\/latex] to [latex]\\mathrm{P}_{2}[\/latex].<\/p>\n

      Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, \\cancel{(\\mathrm{T}_{4})}, \\cancel{(\\mathrm{T}_{5})}, \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, (\\mathrm{T}_{2}), \\mathrm{T}_{9}[\/latex]<\/p>\n

      \n
      \"Timeline
      Figure 3. Put in new tasks into the schedules of the two processors<\/figcaption><\/figure>\n<\/div>\n

       <\/p>\n

      Time 3<\/b>: Processor 1 has completed [latex]\\mathrm{T}_{4}[\/latex]. Completing [latex]\\mathrm{T}_{4}[\/latex] does not make any other tasks ready (note that all the rest require that [latex]\\mathrm{T}_{2}[\/latex]\u00a0be completed first).<\/p>\n

      Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, \\xcancel{(\\mathrm{T}_{4})}, \\cancel{(\\mathrm{T}_{5})}, \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, (\\mathrm{T}_{2}), \\mathrm{T}_{9}[\/latex]<\/p>\n

      Since the next three tasks are not yet ready, we assign the next ready task, [latex]\\mathrm{T}_{2}[\/latex] to [latex]\\mathrm{P}_{1}[\/latex].<\/p>\n

      Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, \\xcancel{(\\mathrm{T}_{4})}, \\xcancel{(\\mathrm{T}_{5})}, \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, \\cancel{(\\mathrm{T}_{2})}, \\mathrm{T}_{9}[\/latex]<\/p>\n

      \n
      \"Timeline
      Figure 4. Assign the next ready task, since the three tasks are not yet ready<\/figcaption><\/figure>\n<\/div>\n

       <\/p>\n

      Time 3.5<\/b>: Processor [latex]1[\/latex] has completed [latex]\\mathrm{T}_{2}[\/latex]. Completing [latex]\\mathrm{T}_{2}[\/latex] causes [latex]\\mathrm{T}_{6}[\/latex] and [latex]\\mathrm{T}_{7}[\/latex] to become ready. We assign [latex]\\mathrm{T}_{6}[\/latex] to [latex]\\mathrm{P}_{1}[\/latex].<\/p>\n

      Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, \\xcancel{(\\mathrm{T}_{4})}, \\xcancel{(\\mathrm{T}_{5})}, \\cancel{(\\mathrm{T}_{6})}, (\\mathrm{T}_{7}), \\mathrm{T}_{8}, \\xcancel{(\\mathrm{T}_{2})}, \\mathrm{T}_{9}[\/latex]<\/p>\n

      \n
      \"Timeline
      Figure 5. Assign the next task in the first processor schedule<\/figcaption><\/figure>\n<\/div>\n

       <\/p>\n

      Time 4<\/b>: Both processors complete their tasks. The completion of [latex]\\mathrm{T}_{5}[\/latex] allows [latex]\\mathrm{T}_{8}[\/latex] to become ready. We assign [latex]\\mathrm{T}_{7}[\/latex] to [latex]\\mathrm{P}_{1}[\/latex] and [latex]\\mathrm{T}_{8}[\/latex]\u00a0to [latex]\\mathrm{P}_{2}[\/latex].<\/p>\n

      Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, \\xcancel{(\\mathrm{T}_{4})}, \\xcancel{(\\mathrm{T}_{5})}, \\xcancel{(\\mathrm{T}_{6})}, \\cancel{(\\mathrm{T}_{7})}, \\cancel{(\\mathrm{T}_{8})}, \\xcancel{(\\mathrm{T}_{2})}, \\mathrm{T}_{9}[\/latex]<\/p>\n

      \n
      \"Timeline
      Figure 6. After both processors complete their tasks, add new tasks in the schedules<\/figcaption><\/figure>\n<\/div>\n

       <\/p>\n

      Time 4.5<\/b>: Both processors complete their tasks. [latex]\\mathrm{T}_{9}[\/latex] becomes ready, and is assigned to [latex]\\mathrm{P}_{1}[\/latex]. There is no ready task for [latex]\\mathrm{P}_{2}[\/latex] to work on, so [latex]\\mathrm{P}_{2}[\/latex]\u00a0idles.<\/p>\n

      Priority list: [latex]\\xcancel{(\\mathrm{T}_{1})}, \\xcancel{(\\mathrm{T}_{3})}, \\xcancel{(\\mathrm{T}_{4})}, \\xcancel{(\\mathrm{T}_{5})}, \\xcancel{(\\mathrm{T}_{6})}, \\xcancel{(\\mathrm{T}_{7})}, \\xcancel{(\\mathrm{T}_{8})}, \\xcancel{(\\mathrm{T}_{2})}, \\cancel{(\\mathrm{T}_{9})}[\/latex]<\/p>\n

      \n
      \"Timeline
      Figure 7. After both processors complete their tasks again, add in new tasks<\/figcaption><\/figure>\n<\/div>\n

       <\/p>\n

      With the last task completed, we have a completed schedule, with finishing time [latex]5.5[\/latex] days.<\/p>\n

      \n

      Using the digraph below, create a schedule using the priority list with two processors:<\/p>\n

      [latex]\\mathrm{T}_{1}, \\mathrm{T}_{2}, \\mathrm{T}_{3}, \\mathrm{T}_{4}, \\mathrm{T}_{5}, \\mathrm{T}_{6}, \\mathrm{T}_{7}, \\mathrm{T}_{8}, \\mathrm{T}_{9}[\/latex]<\/p>\n

      \"Diagram<\/div>\n