There are m available work queues and n jobs (m >= n > 0). The jobs are independent of each other. A job can be executed on any work queue at any time, but once started, it will fully occupy the work queue until finish. For job denoted as i (1

来源:学生作业帮助网 编辑:作业帮 时间:2024/05/13 15:36:57
There are m available work queues and n jobs (m >= n > 0). The jobs are independent of each other. A job can be executed on any work queue at any time, but once started, it will fully occupy the work queue until finish. For job denoted as i (1

There are m available work queues and n jobs (m >= n > 0). The jobs are independent of each other. A job can be executed on any work queue at any time, but once started, it will fully occupy the work queue until finish. For job denoted as i (1
There are m available work queues and n jobs (m >= n > 0). The jobs are independent of each other. A job can be executed on any work queue at any time, but once started, it will fully occupy the work queue until finish. For job denoted as i (1 <= i <= n), it will take t_i time to run on a work queue, and it has to be executed before the deadline d_i, or it is deemed abandoned. Please design an efficient algorithm that tries to maximize the number of jobs that can be arranged to execute before their respective deadlines. If possible, please also describe a scenario that the algorithm you propose might fail, a concrete example is preferred.

There are m available work queues and n jobs (m >= n > 0). The jobs are independent of each other. A job can be executed on any work queue at any time, but once started, it will fully occupy the work queue until finish. For job denoted as i (1
现有m个工作队列和n个作业(m>=N> 0).这些作业是相互独立的.一个作业可以在任何时候在工作队列中工作,不过一旦开始,就完全占据该工作队列直到完成该作业为止.一个作业i(1 <=i<= n),它将需要t_i的时间运行在一个work队列上,它必须在限期d_i前执行完,否则将被放弃.请设计一个有效的算法,它试图最大限度地利用,可安排他们各自的最后期限之前执行完所有的作业.如果可能的话,也请描述一个场景,你提出的算法可能会失败,一个具体的例子是首选.