Scheduling two types of jobs with minimum makespan

June 15, 2024 Β· Declared Dead Β· πŸ› IJTCS-FAW

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Song Cao, Kai Jin arXiv ID 2406.10467 Category cs.DS: Data Structures & Algorithms Citations 0 Venue IJTCS-FAW Last Checked 5 months ago
Abstract
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.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted