Scholarlink

We consider scheduling two types of jobs (A-job and B-job) to p machines and minimizing their makespan. A group of same type of jobs processed consecutively by a machine is called a batch. For machine v, processing x A-jobs in a batch takes \(k^A_vx^2\) time units for a given speed \(k^A_v\) , and processing x B-jobs in a batch takes \(k^B_vx^2\) time units for a given speed \(k^B_v\) . We give an \(O(n^2p\log (n))\) algorithm based on dynamic programming and binary search for solving this problem, where n denotes the maximal number of A-jobs and B-jobs to be distributed to the machines.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Scheduling Two Types of Jobs with Minimum Makespan

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Song Cao,
  • Kai Jin

摘要

We consider scheduling two types of jobs (A-job and B-job) to p machines and minimizing their makespan. A group of same type of jobs processed consecutively by a machine is called a batch. For machine v, processing x A-jobs in a batch takes \(k^A_vx^2\) time units for a given speed \(k^A_v\) , and processing x B-jobs in a batch takes \(k^B_vx^2\) time units for a given speed \(k^B_v\) . We give an \(O(n^2p\log (n))\) algorithm based on dynamic programming and binary search for solving this problem, where n denotes the maximal number of A-jobs and B-jobs to be distributed to the machines.