A fully polynomial time approximation scheme for weighted job-dependent earliness-tardiness problem with agreeable ratios

This article considers a job scheduling problem arising in JIT context where a job may incur both earliness and tardiness penalty and these penalties are dependent on the job as well as amount of earliness and tardiness. Special cases of the problems have been shown to be NP-Complete. To the best of our knowledge, there is no fully polynomial approximation scheme (FPTAS) for this problem. This article proposes a FPTAS for the problem.