Due window assignment and scheduling on parallel machines: a FPTAS for a bottleneck criterion

摘要

A fully polynomial time approximation scheme (FPTAS) with run time is developed for a problem which combines common due window assignment and scheduling n jobs on m identical parallel machines. The problem criterion is bottleneck (min-max) such that the maximum cost, which includes job earliness, job tardiness and due window size costs, is minimized.