两台可拒绝同型机半在线排序问题

本文讨论一个两台可拒绝同型机半在线排序问题.当工件到达时,可以被拒绝,但要付出一定的罚值,也可以被接收加工,消耗一定的加工时间.其目标是要使所有加工工件生成的makespan和被拒绝工件的总罚值之和最小.加工不允许中断.进一步,机器带有两个并行处理子系统,可以提供两种排序方案,最后选取较好的一种.这是第一个在可拒绝同型机排序模型中使用半在线信息,我们设计出一个近似算法,其竞争比为3/2,另外又给出一个√3+1/2≈1.366的下界.     

两台可拒绝同类机在线排序问题近似算法的参数性能比

讨论两台可拒绝同类机在线排序问题的近似算法。设两台机器的速度之比为ｓ（≥１）。工件逐个到位,可以被加工,也可以被拒绝,但要付出相应的罚值ｐｊ。并且只有在安排完当前工件之后,下一个工件才到达。目标函数要求被加工工件集的最迟工件完工时间与被拒绝工件集的总罚值之和达到最小。文中设计出线性时间的ＲＬＳ（α）算法,并证明了其关于ｓ的参数紧界,这个界于ｓ＝１以及ｓ≥（５＋１）／２均是不可改进的。     

两台带服务等级的可拒绝同型机排序问题的在线算法

两台同型机M_1,M_2, 加工速度一致, 但拥有不同的加工能力,用其服务等级表示, M_1的服务等级为1, M_2的服务等级为2. 工件j按列表在线到达,每个工件带有三个参数: 长度t_j,等级g_j=1或2, 罚值p_j. 当j到达时, 可以被拒绝, 但要付出相应的罚值p_j, 也可以被接受并分配给服务等级不超过该工件等级的机器加工,事实上等级为1的工件只能分给M_1加工, 等级为2的工件可以分给M_1或M_2加工, 加工不允许中断. 目标为极小化加工工件集的最晚完工时间(makespan)和拒绝工件集的总罚值之和. 对于该问题给出了一个在线算法, 其竞争比为11/6, 以及问题一个下界5/3.     

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

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

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

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

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

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

同型机和两台批处理机组成三阶段流水作业的最小加工全程问题

讨论一类三阶段流水作业的问题,第一阶段由m台同型机组成,第二阶段和第三阶段分别为1台批处理机,目标函数为最小加工全程.在同型机和两台批处理机上工件的加工时间分别相同情况下,给出了一般情况和几类特殊情况的算法.     

带机器准备时间的两台同型机复合半在线排序问题

本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法.     

带有拒绝的单机和同型机排序问题

研究了带有拒绝的单机和同型机排序问题. 对于单机情形, 工件的惩罚费用是对应加工时间的\alpha倍.如果工件有到达时间, 目标为最小化时间表长与惩罚费用之和, 证明了这个问题是可解的.如果所有工件在零时刻到达, 目标为最小化总完工时间与惩罚费用之和, 也证明了该问题是可解的.对于同型机排序问题, 研究了工件分两批在线实时到达的情形, 目标为最小化时间表长与惩罚费用之和.针对机器台数2和m, 分别给出了竞争比为2和4-2/m的在线算法.     

费用有限的柔性两机自由作业与流水作业排序问题

研究制造商加工环境为两机自由作业和流水作业柔性排序问题,即工件既可以在制造商两台机器上加工,又可以转包给承包商机器加工.承包商有足够多机器,使得每台机器至多加工一个工件.工件在制造商及承包商机器上所需加工时间及费用均不同.本文需要确定被转包的工件集及未转包工件的加工顺序,在加工及转包总费用不超过给定值的情况下,分别极小...     

On-line scheduling of unit time jobs with rejection: minimizing the total completion time

We consider on-line scheduling of unit time jobs on a single machine with job-dependent penalties. The jobs arrive on-line (one by one) and can be either accepted and scheduled, or be rejected at the cost of a penalty. The objective is to minimize the total completion time of the accepted jobs plus the sum of the penalties of the rejected jobs.We give an on-line algorithm for this problem with competitive ratio . Moreover, we prove that there does not exist an on-line algorithm with competitive ratio better than 1.63784.     

工件存在不同交货宽容期的最大加权超前延误问题

本文考虑下述排序问题：有n个工件需在同一台机器上加工,对各工件有一宽容交货期,若一工件在其宽容期前完工则受加权超前惩罚,若在其宽容期后完工则受加权延误惩罚,要求适当安排一加工方式使最大惩罚最小,文中相应某指定工件需准时完工的上述问题证得了Np-hard性,给出了最优算法,并作了一些讨论。     

Parallel machine scheduling with a common due window

In this paper, we consider a machine scheduling problem where jobs should be completed at times as close as possible to their respective due dates, and hence both earliness and tardiness should be penalized. Specifically, we consider the problem with a set of independent jobs to be processed on several identical parallel machines. All the jobs have a given common due window. If a job is completed within the due window, then there is no penalty. Otherwise, there is either a job-dependent earliness penalty or a job-dependent tardiness penalty depending on whether the job is completed before or after the due window. The objective is to find an optimal schedule with minimum total earliness–tardiness penalty. The problem is known to be NP-hard. We propose a branch and bound algorithm for finding an optimal schedule of the problem. The algorithm is based on the column generation approach in which the problem is first formulated as a set partitioning type formulation and then in each branch and bound iteration the linear relaxation of this formulation is solved by the standard column generation procedure. Our computational experiments show that this algorithm is capable of solving problems with up to 40 jobs and any number of machines within a reasonable computational time.     

A novel ant colony optimization approach for on-line scheduling and due date determination

This paper aims to develop an on-line Ant Colony Optimization (ACO) framework, where jobs arrive over time, and at any time we lack knowledge concerning future jobs. A due date is determined upon job arrival, and jobs are sequenced on the machine to optimize the sum of weighted lead times with all due dates met. We propose that each ant is associated with a sequence of waiting jobs with quoted due dates. This waiting sequence is constantly updated over time (whenever a job is selected to be processed or a new job arrives). The on-line schedule is constructed by selecting the first job in the waiting list of the “best” ant to process (along with its due date) as the machine becomes available. However, for the ant where this job is not the first one in the list, processing it pushes back the waiting jobs positioned before it. If such push back results in a due date violation, this ant will be eliminated. Further, our ACO framework does not include the iterative procedure due to the characteristics of the on-line problem; this is one difference from the traditional ACO framework besides ant elimination. The computational testing on generated instances shows that our ACO algorithm outperforms an existing effective on-line algorithm in the literature. Also, with local search incorporated using the EDD (Earliest Due Date) rule, improvements can be obtained in both computational outcome and time.     

可拒绝的同类机在线排序(英文)

考虑了带拒绝费用的在线同类机排序模型.工件一个一个的到达,到达后或被接受,或以一定的费用被拒绝,目标是最小化最大完工时间与总的拒绝费用之和.我们提供了一个在线算法和分析了算法的竞赛比.     

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.     

ON-LINE PROBLEMS OF MINIMIZING MAKESPAN ON A SINGLE BATCH PROCESSING MACHINE WITH NONIDENTICAL JOB SIZES

The on-line problem of scheduling on a batch processing machine with nonidentical job sizes to minimize makespan is considered. The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is given by the longest processing time of any job in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time becomes known upon its arrival. The paper deals with two variants： the case only with two distinct arrival times and the general case. For the first case, an on-line algorithm with competitive ratio 119/44 is given. For the latter one, a simple algorithm with competitive ratio 3 is given. For both variants the better ratios can be obtained if the problem satisfies proportional assumption.     

Parallel-machine scheduling with release dates and rejection

In this paper, we consider the parallel-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 one of the m identical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. When m is a fixed constant, we provide a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for the problem. When m is arbitrary, we present a 2-approximation algorithm for the problem.