THE COORDINATION OF SINGLE-MACHINE SCHEDULING WITH AVAILABILITY CONSTRAINTS AND DELIVERY

摘要

Single-machine scheduling problems with production and delivery are studied in this paper. There is only one delivery vehicle with capacity z. Jobs are not allowed to resume. The P - D system and D - P system are considered, respectively. For the machine with an availability constraint, we present two 4/3-approximation algorithms and show that the bounds are tight. For the machine with periodic availability constraints, we provide two polynomial time approximation algorithms which are the best possible.