问答题

试题四
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
[说明] 用
两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为a_i和b_i。由于各个作业的特点和机器性能的关系，对某些作业，在A上处理时间长，而对某些作业在B上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得n个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。

考虑6个作业的实例，各个作业在两台处理机上的处理时间如表4-1所示。该实例的最优解为（7），最优解的值（即最短处理时间）为（8）。最优解用（x₁,x₂,x₃,x₄,x₅,x₆）表示，其中若第i个作业在A上赴理，则x_i=l，否则x_i=2。如（1，1，1，1，2，2）表示作业1，2，3和4在A上处理，作业5和6在B上处理。

点击查看答案&解析