Algorithms for the joint multitasking scheduling and common due date assignment problem
Algorithms for the joint multitasking scheduling and common due date assignment problem
复制标题
联合多任务调度和常见到期日分配问题的算法
DOI：
10.1080/00207543.2017.1321804
复制
发表时间：
2017
影响因子：
9.2
通讯作者：
Chengbin Chu
中科院分区：
文献类型：
--
作者：
Ming Liu;Shijin Wang;Feifeng Zheng;Chengbin Chu
本文研究了单机上的多任务联合调度和公共交货期分配问题，并以物流中的产品配送过程为例进行了研究。多任务允许机器执行多个任务。多任务现象已经在包括制造和管理在内的各种实际领域中被观察到。在多任务设置中，每个等待的作业都会中断当前正在处理的作业，从而产生中断时间和切换时间。在常见的交货期分配问题中，目标是确定最佳值的这个交货期的总惩罚函数，这是与服务质量最小化的目的。对于具有一般中断函数的问题，得到了减小最优解搜索空间的解析性质。对于线性中断函数的情况，我们提出了一个多项式时间算法。数值实验验证了算法的有效性。计算结果还显示了一个有趣的现象，在某些情况下，多任务下的最优解上级没有多任务的同行。此外，我们还设计了一个混合整数规划的情况下，线性中断功能。
In this paper, we investigate a joint multitasking scheduling and common due date assignment problem on a single machine, for which examples can be found in product delivery process in logistics. Multitasking allows the machine to perform multiple tasks. The multitasking phenomenon has been observed in various practical domains, including manufacturing and administration. In multitasking settings, each waiting job interrupts a currently in-processing job, causing an interruption time and a switching time. In common due date assignment problems, the objective is to determine the optimal value of this due date with the purpose of minimising a total penalty function, which is associated with service quality. For the problem with general interruption functions, analytical properties are obtained to reduce the search space of the optimal solutions. For the cases with linear interruption functions, we develop a polynomial-time algorithm. Numerical experiments have been conducted to validate the efficiency of our proposed algorithm. Computational results also demonstrate an interesting phenomenon that in some cases, the optimal solutions under multitasking are superior to the counterparts without multitasking. Besides, we also devise a mixed integer programme for the cases with linear interruption function.