Customer order scheduling to minimize the number of late jobs |
| |
Authors: | B.M.T. Lin A.V. Kononov |
| |
Affiliation: | 1. Department of Finance and Information Management, Institute of Information Management, National Chiao Tung University, Taiwan;2. Sobolev Institute of Mathematics, Novosibirsk, Russia |
| |
Abstract: | In the order scheduling problem, every job (order) consists of several tasks (product items), each of which will be processed on a dedicated machine. The completion time of a job is defined as the time at which all its tasks are finished. Minimizing the number of late jobs was known to be strongly NP-hard. In this note, we show that no FPTAS exists for the two-machine, common due date case, unless P = NP. We design a heuristic algorithm and analyze its performance ratio for the unweighted case. An LP-based approximation algorithm is presented for the general multicover problem. The algorithm can be applied to the weighted version of the order scheduling problem with a common due date. |
| |
Keywords: | Order scheduling Number of late jobs Approximability Approximation algorithm Multicover problem |
本文献已被 ScienceDirect 等数据库收录! |
|