Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines (Q600836): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 08:51, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines |
scientific article |
Statements
Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines (English)
0 references
3 November 2010
0 references
In this paper multi-slot just-in-time scheduling problems are considered. Given is a set of jobs \(j=1,\ldots,n\) where each job \(j\) has a processing time \(p_j\) and a due date \(d_j\). The objective is to schedule all jobs on a given number of parallel machines in time slots of length \(L\) such that job \(j\) is completed exactly at its due date in one time slot (i.e. at time \(iL+d_j\) for some integer \(i \geq 0\)) and the makespan is minimized. In this paper an \(O(n \log ^2 n)\)-time algorithm is presented for the single machine case and an \(O(n \log n)\)-time algorithm for an arbitrary number \(m>1\) of parallel machines where \(p_j \leq d_j\) for all jobs \(j\) holds. Finally, for the general case on \(m>1\) parallel machines a polynomial-time approximation algorithm with constant worst-case performance ratio is proposed.
0 references
just-in-time scheduling
0 references
makespan minimization
0 references
multi-slot
0 references