Algorithms for scheduling incompatible job families on single batching machine with limited capacity
Algorithms for scheduling incompatible job families on single batching machine with limited capacity
复制标题
DOI：
10.1016/j.cie.2014.06.014
复制
发表时间：
2014-09
期刊：
影响因子：
--
通讯作者：
B. Cheng;J. Cai;Shanlin Yang;Xiaoxuan Hu
中科院分区：
文献类型：
--
作者：
B. Cheng;J. Cai;Shanlin Yang;Xiaoxuan Hu
受食品加工和半导体制造业中的应用启发，我们考虑了具有多个工件族的机器排序问题。这台机器容纳工作的能力有限。工作是在任意大小和多个家庭。来自不同系列的作业不能批量处理。我们证明了最小化完工时间和总批完工时间的问题都是强NP困难的。我们提出了一个混合整数规划模型的问题。在此基础上，提出了基于最长处理时间优先规则和最佳匹配规则的两种多项式时间算法。对于较大工件的加工时间也较长的特殊情况，最小化最大完工时间的启发式算法是最优的。对于一般的情况下，我们显示的性能保证的方法分别为两个目标。
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.