Advertisement
Published in:
2015 | OriginalPaper | Chapter
Variants of Multi-resource Scheduling Problems with Equal Processing Times
Authors : Hamed Fahimi, Claude-Guy Quimper
Published in: Combinatorial Optimization and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We tackle the problem of non-preemptive scheduling of a set of tasks of duration p over m machines with given release and deadline times. We present a polynomial time algorithm as a generalization to this problem, when the number of machines fluctuates over time. Further, we consider different objective functions for this problem. We show that if an arbitrary function cost \(c_i(t)\) is associated to task i for each time t, minimizing \(\sum _{i=1}^n c_i(s_i)\) is NP-Hard. Further, we specialize this objective function to the case that it is merely contingent on the time and show that although this case is pseudo-polynomial in time, one can derive polynomial algorithms for the problem, provided the cost function is monotonic or periodic. Finally, as an observation, we mention how polynomial time algorithms can be adapted with the objective of minimizing maximum lateness.