Unbounded parallel-batch scheduling with family jobs and delivery coordination |
| |
Authors: | Shisheng Li Jinjiang Yuan |
| |
Affiliation: | a Department of Mathematics, Zhengzhou University, Zhengzhou 450001, PR China b Department of Mathematics and Information, Ludong University, Yantai 264025, PR China |
| |
Abstract: | We study a scheduling problem that integrates parallel-batch production with family jobs and job delivery at the same time. The jobs are first processed on an unbounded parallel-batch machine and then delivered in batches to their specified customers by a transportation vehicle. We assume that jobs from different families (customers) cannot be processed together by the batch machine and also transported together by the vehicle. The objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. We first show that the problem is NP-hard, and then propose for it a heuristic algorithm with a worst-case performance ratio of 3/2. |
| |
Keywords: | Parallel-batch scheduling Family jobs Batch delivery Approximation algorithms |
本文献已被 ScienceDirect 等数据库收录! |