流水作业调度问题
成绩 | 100 | 开启时间 | 2016年05月27日 星期五 19:50 |
折扣 | 0.8 | 折扣时间 | 2016年05月27日 星期五 19:50 |
允许迟交 | 是 | 关闭时间 | 2016年05月27日 星期五 19:50 |
输入文件 | flowshop.in | 输出文件 | flowshop.out |
【题目描述】流水作业调度问题(flowshop.cpp/c/pas) POJ 2751
有句谚语说如果马有投票权,世界上不会有汽车。而事实是就算马有投票权,它们还是会被汽车淘汰。正所谓生产力和科技进步的车轮是谁也无法抵挡的。魔法世界的工业生产早已实现了自动化,虽然这曾经引起长达十余年的由失业工人发动的大规模抗议浪潮。
话说逆转“时空陷”的机器就是在魔法学院的自动化生产线上完成的,已知完成N个作业要在由两台机器M1和M2组成的流水线上完成加工,每个作业i必须先在M1上然后在M2上加工,时间分别为ai和bi。
确定这n个作业的加工顺序,使得从第一个任务开始在M1上加工到最后一个任务在M2上加工完成的总时间尽量小。
【输入格式】
每组测试数据第一行有一个整数N(1 ≤ N ≤ 10000), 表示作业数,以下N行每行包含两个整数a和b (0≤a,b≤100),表示作业在M1和M2上加工的时间。所有测试数据结束标志为0。
【输出格式】
每组测试数据输出一行最少完成时间。
【输入样例】
4
1 2
3 4
5 6
7 8
4
10 1
10 1
1 10
1 10
5
4 5
4 1
30 4
6 30
2 3
6
5 7
1 2
8 2
5 4
3 7
4 4
0
【输出样例】
24
23
47
28