Preemptive scheduling of independent jobs on parallel machines subject to financial constraints (Q791440)

The author considers a scheduling problem involving independent preemptable jobs, unrelated parallel machines, renewable resources (such as labor), and one nonrenewable resource (such as capital) that becomes available over time. There are two optimality criteria: makespan and total costs. A two-stage algorithm is developed. First, parametric linear programming yields a compromise between both criteria. Next, a feasible schedule is constructed in polynomial time. It is also shown that minimizing the number of preemptions is equivalent to a traveling salesman problem.