Scheduling two types of jobs with minimum makespan
<|reference_start|>Scheduling two types of jobs with minimum makespan: 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. Our algorithm also fits the easier linear case where each batch of length $x$ of $A$-jobs takes $k^A_v x$ time units and each batch of length $x$ of $B$-jobs takes $k^B_vx$ time units. The running time is the same as the above case.<|reference_end|>
@article{cao2024scheduling,
    title={Scheduling two types of jobs with minimum makespan},
    author={Song Cao, Kai Jin},
    journal={arXiv preprint arXiv:2406.10467},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.10467},
    primaryClass={cs.DS}
}