Minimizing total load on a proportionate flowshop with position-dependent processing times and job-rejection

摘要

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(n(4)) 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(n(5)) time. (C) 2017 Elsevier B.V. All rights reserved.