具有退化工件和老化效应的单机可拒绝排序问题

研究同时具有退化工件和老化效应的单机可拒绝排序问题,即工件的实际加工时间是与其开工时间和所在位置有关的函数,同时生产商可以通过支付一定的处罚费用而拒绝加工某些工件。在生产加工过程中,考虑对机器进行选择性维修活动来提高加工的效率;机器进行维修活动后将恢复到初始状态,老化效应也将重新开始。目标是确定拒绝哪些工件、何时进行维修活动以及接受工件集中工件的次序,以便极小化接受加工工件的最大完工时间与拒绝加工工件总处罚费用的和。证明得到了所研究的问题是NP-难解的,并给出了解决问题的一个全多项式时间近似方案(FPTAS)算法。     

工期窗口安排与具有退化效应和维修活动的单机排序

考虑具有工件相关的退化效应和维修活动的单机排序模型,讨论了工期窗口安排问题.在这一模型中,机器在加工过程中产生退化使效率降低,工件的实际加工时间不仅与其所在排序中的位置有关并且与其本身的退化率有关;然而,维修活动能使机器的加工效率得到恢复.工期窗口的开始时间是已给定的常量,而工期窗口的结束时间是需要确定的变量.目标是得到安排维修活动的最佳时间、最佳工期窗口的大小和最优排序以便最小化流时间、提早、延误和工期窗口大小的总处罚函数.对这一问题,给出了一多项式算法.     

工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案.     

工件有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案.     

基于退化效应的两台机器流水作业可拒绝排序

考虑了工件具有退化效应的两台机器流水作业可拒绝排序问题,其中工件的加工时间是其开工时间的简单线性增加函数.每个工件或者被接收,依次在两台流水作业机器上被加工,或者被拒绝但需要支付一个确定的费用.考虑的目标是被接收工件的最大完工时间加上被拒绝工件的总拒绝费用之和.证明了问题是NP-难的,并提出了一个动态规划算法.最后对一种特殊情况设计了多项式时间最优算法.     

工件延误和可拒绝下的单机重新排序问题的近似方案

研究工件延误产生干扰且延误工件可拒绝下的单机重新排序问题。在该问题中,给定计划在零时刻到达的一个工件集需在一台机器上加工,工件集中的每个工件有它的加工时间和权重,在工件正式开始加工前,按照最短赋权加工时间优先的初始排序已经给定,目标函数是极小化赋权完工时间和,据此每个工件的承诺交付截止时间也给定。然而,在工件正式开始加工时,工件集中的部分工件由于延误不能按时到达,这对初始排序的执行产生了干扰,所以需要对初始排序进行调整,即重新排序。为了保证服务水平,允许对延误工件拒绝加工,但需支付相应的拒绝费用。调整后的重新排序的目标是在保证接受工件集中工件的最大延误不超过给定的上界的约束下,使得接受工件集的赋权完工时间和,拒绝工件集的拒绝费用和以及接受工件集中工件的最大延误的赋权惩罚费用之和达到极小。对该问题,设计了一个伪多项式时间动态规划精确算法,并利用稀疏技术得到了一个完全多项式时间近似方案。     

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

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

工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。     

工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。     

具有CON/SLK交货期指派的一类单机排序问题

研究工件的实际加工时间既具有指数学习效应,又依赖所消耗资源的准时制排序问题.在模型中,探讨了共同交货期(CON)和松弛交货期(SLK)两种情形.管理者的目标是确定最优序、最优资源分配方案和最佳工期(共同交货期或松弛交货期)以便极小化工件的总延误、总提前、总工期和资源消耗费用的总和.对于工件的实际加工时间是资源消耗量的线性函数的排序问题,通过将其转化为指派模型,给出了时间复杂性为O(n~3)的算法,从而证明该类排序问题是多项式时间可求解的.针对工件的实际加工时间是资源消耗量的凸函数的排序问题,也给出了多项式算法.     

Optimal due-date assignment problem with learning effect and resource-dependent processing times

In this paper, we consider a single-machine earliness-tardiness scheduling problem with due-date assignment, in which the processing time of a job is a function of its position in a sequence and its resource allocation. The due date assignment methods studied include the common due date, and the slack due date, which reflects equal waiting time allowance for the jobs. For each combination of due date assignment method and processing time function, we provide a polynomial-time algorithm to find the optimal job sequence, due date values, and resource allocations that minimize an integrated objective function, which includes earliness, tardiness, due date assignment, and total resource consumption costs.     

Deteriorating jobs scheduling on a single machine with release dates,rejection and a fixed non-availability interval

This paper studies single machine scheduling with a fixed non-availability interval. The processing time of a job is a linear increasing function of its starting time, and each job has a release date. A job is either rejected by paying a penalty cost or accepted and processed on the machine. The objective is to minimize the makespan of the accepted jobs and the total rejection penalties of the rejected jobs. We present a fully polynomial-time approximation scheme for the problem. We also show that the special case without non-availability interval can be solved using the same method with a lower order.     

The unbounded parallel-batch scheduling with rejection

In this paper, we consider the unbounded parallel-batch scheduling with rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and processed in batches on a machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. Four problems are considered: (1) to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs; (2) to minimize the total completion time of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs; (3) to minimize the total rejection penalty of the rejected jobs subject to an upper bound on the total completion time of the accepted jobs; (4) to find the set of all the Pareto optimal schedules. We provide a polynomial-time algorithm for the first problem. Furthermore, we show that all the other three problems are binary NP-hard and present a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for them.     

Single machine scheduling and due date assignment with positionally dependent processing times

We consider single machine scheduling and due date assignment problems in which the processing time of a job depends on its position in a processing sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and, possibly, the total earliness of the scheduled jobs. We present polynomial-time dynamic programming algorithms in the case of two popular due date assignment methods: CON and SLK. The considered problems are related to mathematical models of cooperation between the manufacturer and the customer in supply chain scheduling.     

The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times

We study the earliness-tardiness scheduling problem on a single machine with due date assignment and controllable processing times. We analyze the problem with three different due date assignment methods and two different processing time functions. For each combination of these, we provide a polynomial-time algorithm to find the optimal job sequence, due date values and resource allocation minimizing an objective function which includes earliness, tardiness, due date assignment, makespan and total resource consumption costs.     

Single-machine common due window assignment and scheduling to minimize the total cost

In this paper we consider a single-machine common due window assignment and scheduling problem with batch delivery cost. The starting time and size of the due window are decision variables. Finished jobs are delivered in batches. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find a job sequence, a delivery date for each job, and a starting time and a size for the due window that jointly minimize the total cost comprising earliness, weighted number of tardy jobs, job holding, due window starting time and size, and batch delivery. We provide some properties of the optimal solution and present polynomial-time algorithms for the problem.     

Single machine scheduling with release dates and rejection

In this paper, we consider the single machine scheduling problem with release dates and rejection. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the machine. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. We show that the problem is NP-hard in the ordinary sense. Then we provide two pseudo-polynomial-time algorithms. Consequently, two special cases can be solved in polynomial-time. Finally, a 2-approximation algorithm and a fully polynomial-time approximation scheme are given for the problem.