工件可拒绝的单机多任务排序问题研究

Multitasking Scheduling Problems with Job Rejection on Single Machine

文章研究了工件可拒绝的单机多任务排序问题.在多任务环境下,当某个工件(主工件)在加工时,会被其他未完成加工的工件(等待工件)所打扰,则主工件的实际加工时间由三部分组成:主工件剩余部分的加工长度,等待工件的打扰时间以及等待工件的切换时间.在经典的排序模型中,要求每个工件都被加工,然而在高负荷的定制化生产系统中,接受所有工件可能会导致订单交付延迟,进而导致高成本,故文章考虑了工件可拒绝的排序问题.为了保证一定的服务水平,要求拒绝工件的总惩罚不超过给定值,目标是选择哪些工件加工并给出其排序以使得最大完工时间、总完工时间和总加权完工目标最小.这三个问题都是NP-难问题,对此给出了伪多项式时间动态规划算法.

This work studies multitasking scheduling on a single machine with job rejection.In multitasking environment,the processing of a primary job is interrupted by the waiting jobs that are available but unfinished.The duration of processing a primary job is comprised of three parts:The processing time of the remaining part of the primary job,the interruption time denoting the time of the partial processing time of the waiting job,and the switching time denoting the time during which no jobs are processed when the primary job scheduled.However,mostly in highly loaded make-to-order production systems,accepting all jobs may cause a delay in the completion of orders which in turn may lead to high costs,so this paper assumed jobs can be rejected or outsourced.To keep a certain service level,it is required that the total rejection cost is not greater than a given threshold.The goal is to select which jobs to process and schedule them to minimize the maximum completion time,the total completion time and the total weighted completion time.Since these problems are NP-hard,we pay attention to providing pseudo polynomial dynamic programming algorithms.