Approximation algorithms for common due date assignment and job scheduling on parallel machines |
| |
Authors: | Xiao Wen-qiang Li Chung-Lun |
| |
Affiliation: |
a Department of Industrial Engineering and Engineering Management, The Hong Kong University of Science and Technology, Kowloon, Hong Kong |
| |
Abstract: | We consider the problem of assigning a common due date to a set of jobs and scheduling the jobs on a set of parallel machines so that the weighted sum of the due date, total earliness, and total tardiness is minimized. A heuristic is developed to solve this problem, and an absolute performance ratio is provided for this heuristic. Another heuristic with a better worst-case performance bound is presented for the case with a zero earliness penalty. A fully polynomial approximation scheme is also developed. |
| |
Keywords: | |
本文献已被 InformaWorld SpringerLink 等数据库收录! |
|