Scheduling of two parallel machines with linear decreasing time slot costs to minimize total weightedcompletion time

Abstract

We consider a scheduling problem with two parallel machines to minimize the sum of total weighted completion time and total machine time slot cost. In this paper we focus on the case of the constant or linear decreasing sequences of time slot costs. We suggest an exact pseudopolynomial DP algorithm for the case of arbitrary integer processing times of jobs. If all jobs have unit processing times, we modify our approach to obtain a polynomial algorithm.