具有不可用区间且工件可拒绝下的单机重新排序问题的近似方案

本文考虑了机器具有不可用区间且工件可拒绝下的单机重新排序问题,在该问题中,给定一个工件集需在一台机器上加工,每个工件有自己的加工时间和权重,且对该工件集目标函数为极小化总加权完工时间的排序计划已给定,根据该排序计划中每个工件的完工时间已确定每个工件的承诺交付时间。然而,在工件正式开始加工前,原计划用于加工的某段时间区间因临时用于检修机器而导致机器在该时间区间不再可用,需要对工件重新排序。为了确保在新的重新排序中,工件的延误成本不致太大,决策者可以选择拒绝部分工件,但需支付相应的拒绝费用。任务是确定接受工件集和拒绝工件集,并将接受的工件在考虑机器具有不可用区间的条件下重新排序使得接受工件集的总加权完工时间,总拒绝费用及赋权最大延误之和最小。该问题是NP-困难的,对此给出了伪多项式时间动态规划精确算法,利用稀疏技术设计了完全多项式时间近似方案。

Approximation Scheme for Single Machine Rescheduling Problem with an Unavailable Interval and Job Rejection

In this paper, we consider the single machine rescheduling problem with an unavailable interval and job rejection. In this problem, given a set of jobs to be processed on a single machine, each job has its processing time and its weight and a planned schedule with the goal to minimize the total weighted completion time has been made. The promised deliver time for each job is determined based on its completion time in the planned schedule. However, before the formal job processing begins, a given interval that is originally used to process jobs in the planned schedule becomes unavailable due to the temporary occupation for maintaining the machine. The planned schedule becomes unfeasible and is required to reschedule. To assure that the tardiness penalty for jobs is not too much in the adjusted schedule, the decision-maker has the option to reject some jobs by paying the corresponding reject costs. The task is to determine the accepted set of jobs and the rejected set of jobs and reschedule the accepted jobs subject to a given unavailable interval on the machine to minimize the sum of the total weighted completion time for the accepted jobs, the total reject cost for the rejected jobs and the weighted maximum tardiness penalty. This problem is NP-hard. We propose a pseudo-polynomial time dynamic programming exact algorithm and a fully polynomial time approximation scheme by using the sparse technique.