Single-machine parallel-batching scheduling with family jobs to minimize weighted number of tardy jobs |
| |
Affiliation: | 1. Department of Industrial Engineering and System Management, Feng Chia University, Taichung, Taiwan, ROC;2. Department of Statistics, Feng Chia University, Taichung, Taiwan, ROC;3. Department of Computer Science and Information Management, Hungkuang University, Taichung, Taiwan, ROC |
| |
Abstract: | We consider the problem of scheduling n jobs in batches on a single parallel-batching machine, where the jobs are partitioned into jobs families and the jobs in each family have the same due date. The objective is to minimize the weighted number of tardy jobs. We first devise an efficient pseudo-polynomial time and a fully polynomial time approximation scheme for the weighted problem. Then we present -time and -time algorithms for the case where the jobs have the same weight and for the case where the jobs have the same processing time, respectively. |
| |
Keywords: | Parallel-batching scheduling Family jobs Uniform family due dates Fully polynomial time approximation scheme |
本文献已被 ScienceDirect 等数据库收录! |
|