算法分析与设计

调度问题

问题:有n项任务,每项任务加工时间已知.从0时刻开始陆续安排到一台机器上加工.每个任务的完成时间是从0时刻到任务加工截止的时间.
求:总完成时间最短的方案

问题建模:

• 输入:任务集:S={1,2,…,n} 第j项任务加工时间:tj∈Z+,j=1,2,…,n.

  贪心算法:
设计策略:加工时间短的先做
算法:根据加工时间从小到大排序,依次加工
算法正确性:对所有输入实例都得到最优解