Scheduling multiple variable-speed machines

The paper examines scheduling problems where it controls not only the assignment of jobs to machines, but also the time used by the job on the machine. For instance, many tooling machines allow control of the speed at which a job is run. Increasing the speed incurs costs due to machine wear, but also increases throughput. The paper discusses some fundamental scheduling problems in this environment and gives algorithms for some interesting cases. Some cases are inherently difficult so for these it gives heuristics. The present approach illustrates the exploitation of underlying network structure in combinatorial optimization problems. The paper creates heuristics that optimally schedule a large portion of the jobs and then attempts to fit in the remainder. This also gives a method for quickly finding valid inequalities violated by the linear relaxation solution. For the problem of minimizing the sum of makespan and production costs, a rounding heuristic is within a constant factor of optimal. The present heuristics are compared to other classical heuristics.