Algorithms for scheduling incompatible job families on single batching machine with limited capacity |
| |
Affiliation: | 1. ABB Corporate Research Germany, Wallstadter Str. 59, Ladenburg 68526, Germany |
| |
Abstract: | Motivated by applications in food processing and semiconductor manufacturing industries, we consider the scheduling problem of a batching machine with jobs of multiple families. The machine has a limited capacity to accommodate jobs. The jobs are in arbitrary sizes and multiple families. Jobs from different families cannot be processed in a batch. We show the problems of minimizing makespan and total batch completion time are both NP-hard in the strong sense. We present a mixed integer programming model for the problems. Then we propose two polynomial time heuristics based on longest processing time first rule and first fit rule. For the special case where a larger job also has a longer processing time, the heuristic for minimizing makespan is optimal. For the general case, we show the performance guarantee of the methods for the two objectives respectively. |
| |
Keywords: | Scheduling Single batching machine Incompatible job families Arbitrary job sizes Approximation algorithm |
本文献已被 ScienceDirect 等数据库收录! |