Keyun Cheng

Reading Notes: COMMACM’1974 Scheduling

Title: Scheduling independent tasks to reduce mean finishing time

Conference (Communications of the ACM’1974): Link

Journal (): Link

Summary

This paper (1) Provides an algorithm to solve scheduling parallel unrealted machines with mean-finish-time as objective; (2) Show that minimizing the maximum finish time is NP-complete

Main Contributions

• The algorithm to solve mean-finish-time is of great importance. It models the problem as a min-cost-flow problem

Details

• The problem reduction to a transportation problem, then applying a min-cost-flow graph is straight forward

• Solving a weighted mean-finish-time problem is NP-complete

• There is a set of analysis on maximum-finish-time analysis and comparisons beween SPT and LPT (shortest / largest processing time first) heuristics

Strength

Weakness