Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874227 | Information Processing Letters | 2018 | 5 Pages |
Abstract
We study the scheduling problem of minimizing total load on a proportionate flowshop. We consider position-dependent job processing times in the most general way. We show that this problem is solved in O(n4) time, where n is the number of jobs. We then extend the setting to allow job-rejection, where the scheduler may decide to process only a subset of the jobs, and the rejected jobs are penalized. This extension is shown to be solved in O(n5) time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Shir Fiszman, Gur Mosheiov,