Complexity Results for Scheduling Tasks in Fixed Intervals on Two Types of Machines

摘要

A natural generalization of the fixed job schedule problem is considered. Potential applications in areas as vehicle scheduling, machine scheduling, and computer wiring are pointed out. Each task requires a given processing time on a slow machine or a given smaller processing time on a fast machine. Two different feasibility assumption are made: (1) each task has a specified processing interval, the length of which is equal to the processing time on a slow machine; (2) each task has a specified starting time. For either problem type, a feasible schedule of minimum total machine cost is sought. The results are complemented by polynomial algorithms for special cases.