Operations Research Seminars Amsterdam

Speaker(s)
Tjark Vredeveld (Maastricht University)
Date
Wednesday, 2 December 2015
Location
Amsterdam

We study a preemptive single machine scheduling problem where the machine speed is externally given and depends on the number unfinished jobs. The objective is to minimize the sum of weighted completion times. When the order of job completions is known, we give an LP-formulation that finds the optimal value. Using this formulation, we can give some structural property on an optimal solution. Using this structural property, we can show that the problem is NP-hard in the general case, but can be solved in polynomial time in the case of unit weights or unit processing times. Moreover, we develop a greedy algorithm that finds an optimal schedule given the order in which the jobs complete.