Single machine scheduling - Problem and solution

Main Ideas

The video explains how a company with one machine can sequence jobs from multiple customers. Different scheduling rules prioritize different goals, such as serving customers in arrival order, completing short jobs quickly, or reducing delays.

Seven Scheduling Rules

• First Come, First Served (FCFS): Process jobs in the order customers submit them.
• Shortest Processing Time (SPT): Process the job requiring the least time first; the longest job is last.
• Longest Processing Time (LPT): Process the job requiring the most time first; the shortest job is last.
• Earliest Due Date (EDD): Process jobs in order of their due dates, starting with the soonest.
• Preferred Customer Order: Give priority to selected customers, such as loyal or otherwise important customers.
• COVERT (Cost Over Time): Consider the cost of delaying a job relative to its processing time. The video defines the measure as the cost of delay divided by processing time and suggests prioritizing jobs with greater delay costs.
• Random Selection: Choose the next job at random.

Worked Example and Evaluation Method

The example includes five jobs:

Job Processing time Due date A 6 days Day 8 B 2 days Day 6 C 8 days Day 18 D 3 days Day 15 E 9 days Day 23

The presenter compares FCFS, EDD, and SPT:

1. Set the job sequence according to the rule being evaluated:
   • FCFS: A–B–C–D–E
   • EDD: B–A–D–C–E
   • SPT: B–D–A–C–E
2. Calculate each job’s flow or completion time by adding its processing time to the processing times of all jobs before it.
3. Calculate late days as the amount by which completion exceeds the due date, using zero if a job finishes on time or early.
4. Total the flow times and late days, then compare the results:
   • Average flow time = total flow time ÷ number of jobs
   • Average number of jobs in the system = total flow time ÷ total processing time
   • Average job lateness = total late days ÷ number of jobs

Results and Conclusion

Rule Total flow time Total late days Average flow time Average jobs in system Average lateness FCFS 77 11 15.4 2.75 2.2 EDD 68 6 13.6 2.43 1.2 SPT 65 9 13.0 2.32 1.8

The presenter selects SPT for this example because it gives the lowest average flow time and average number of jobs in the system. EDD performs best on average lateness, so the preferred rule depends on which measure the company values most.

Speakers and Sources

• Unnamed presenter/instructor: Explains the scheduling rules and works through the example.
• No other speakers or external sources are featured in the subtitles.