Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines
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.
- scientific article; zbMATH DE number 2139462
- A quadratic time algorithm to maximize the number of just-in-time jobs on identical parallel machines
- Just-in-time scheduling with controllable processing times on parallel machines
- The just-in-time scheduling problem in a flow-shop scheduling system
- Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs
- Bounds on Multiprocessing Timing Anomalies
- Fairness Measures for Resource Allocation
- scientific article; zbMATH DE number 3898613 (Why is no real title available?)
- scientific article; zbMATH DE number 1128827 (Why is no real title available?)
- Just-in-time scheduling. Models and algorithms for computer and manufacturing systems
- On the \(k\)-coloring of intervals
- Optimal flows in networks with multiple sources and sinks
- Precoloring extension. I: Interval graphs
- Proportional optimization and fairness
- Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs
- Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
- Simple algorithms for gilmore-gomory's traveling salesman and related problems
- A study on the enhanced best performance algorithm for the just-in-time scheduling problem
- A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria
- Makespan optimization in a single-machine scheduling problem with dynamic job ready times-complexity and algorithms
- A quadratic time algorithm to maximize the number of just-in-time jobs on identical parallel machines
- Routing equal-size messages on a slotted ring
- scientific article; zbMATH DE number 2139462 (Why is no real title available?)
This page was built for publication: Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q600836)
