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.     

并行分批排序综述

并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。     

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

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

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

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

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

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

Scheduling with batch setup times and earliness-tardiness penalties

We consider a scheduling model in which several batches of jobs need to be processed by a single machine. During processing, a setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. All the jobs in the same batch have a common due date that is either externally given as an input data or internally determined as a decision variable. Two problems are investigated. One problem is to minimize the total earliness and tardiness penalties provided that each due date is externally given. We show that this problem is NP-hard even when there are only two batches of jobs and the two due dates are unrestrictively large. The other problem is to minimize the total earliness and tardiness penalties plus the total due date penalty provided that each due date is a decision variable. We give some optimality properties for this problem with the general case and propose a polynomial dynamic programming algorithm for solving this problem with two batches of jobs. We also consider a special case for both of the problems when the common due dates for different batches are all equal. Under this special case, we give a dynamic programming algorithm for solving the first problem with an unrestrictively large due date and for solving the second problem. This algorithm has a running time polynomial in the number of jobs but exponential in the number of batches.     

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

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

Scheduling with partial rejection

We study a single machine scheduling problem with partial rejection. Each job is with an integer processing time. Partial rejection occurs when a job is only partly processed with penalty for the rejected part. We focus on integer size rejection. The objective is to minimize the total weighted completion time of processed jobs plus the total rejection cost. We develop a polynomial time optimal algorithm to solve the problem. We also present an easy-to-implement pseudopolynomial time optimal algorithm.     

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

研究工件延误产生干扰且延误工件可拒绝下的单机重新排序问题.在该问题中,给定计划在零时刻到达的一个工件集需在一台机器上加工,工件集中的每个工件有它的加工时间和权重,在工件正式开始加工前,按照最短赋权加工时间优先的初始排序已经给定,目标函数是极小化赋权完工时间和,据此每个工件的承诺交付截止时间也给定.然而,在工件正式开始加...     

Single machine batch scheduling with resource dependent setup and processing times

Jobs are processed by a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time common for all batches. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource, which may be different from that for the jobs. Polynomial time algorithms are presented to find an optimal batch sequence and resource values such that either the total weighted resource consumption is minimized, subject to meeting job deadlines, or the maximum job lateness is minimized, subject to an upper bound on the total weighted resource consumption. The algorithms are based on linear programming formulations of the corresponding problems.     

On scheduling an unbounded batch machine

A batch machine is a machine that can process up to c jobs simultaneously as a batch, and the processing time of the batch is equal to the longest processing time of the jobs assigned to it. In this paper, we deal with the complexity of scheduling an unbounded batch machine, i.e., c=+∞. We prove that minimizing total tardiness is binary NP-hard, which has been an open problem in the literature. Also, we establish the pseudopolynomial solvability of the unbounded batch machine scheduling problem with job release dates and any regular objective. This is distinct from the bounded batch machine and the classical single machine scheduling problems, most of which with different release dates are unary NP-hard. Combined with the existing results, this paper provides a nearly complete mapping of the complexity of scheduling an unbounded batch machine.     

Scheduling linear deteriorating jobs with rejection on a single machine

We consider several single machine scheduling problems in which the processing time of a job is a linear function of its starting time and jobs can be rejected by paying penalties. The objectives are to minimize the makespan, the total weighted completion time and the maximum lateness/tardiness plus the total penalty of the rejected jobs. We show that these problems are NP-hard, and design algorithms based on dynamic programming (including pseudo-polynomial time optimal algorithms and fully polynomial time approximation schemes) to solve them.     

Realistic two-stage flowshop batch scheduling problems with transportation capacity and times

This paper investigates single-batch and batch-single flow shop scheduling problem taking transportation among machines into account. Both transportation capacity and transportation times are explicitly considered. While the single processing machine processes one job at a time, the batch processing machine processes a batch of jobs simultaneously. The batch processing time is the longest processing times of jobs assigned to that batch.Each problem is formulated as a mixed integer programming model to find optimal makespan. Lower bounds and heuristic algorithms are proposed and computational experiments are carried out to verify their effectiveness.     

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.     

分类数很大时的成组排序问题

成组排序具有深刻的实际应用背景,是近年来国外研究得较多的一个热点.已有的某些动态规划算法的复杂性随分类数的增长呈指数型增长趋势,本文用“归并”和解不超过四个新的子问题的方法把分类数较大时的问题转化为分类数较小时的相应问题,简化了问题的求解.     

极小化总完工时间的同时加工排序

讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况.     

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.     

无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案

本文考虑n个工件的无限批量机器调度问题．一台机器可以同时加工B≥n个工件．每个工件具有一个正权因子、一个释放时间和一个加工时间．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间，即它们的共同开始时间加上该批次的加工时间．对于最小化加权完工时间和问题，本文给出了第一个多项式时间近似方案(PTAS)．对任意给定精度，该算法的运行时间为线性的．     

Vector scheduling with rejection on a single machine

In this paper, we study a vector scheduling problem with rejection on a single machine, in which each job is characterized by a d-dimension vector and a penalty, in the sense that, jobs can be either rejected by paying a certain penalty or assigned to the machine. The objective is to minimize the sum of the maximum load over all dimensions of the total vector of all accepted jobs, and the total penalty of rejected jobs. We prove that the problem is NP-hard and design two approximation algorithms running in polynomial time. When d is a fixed constant, we present a fully polynomial time approximation scheme.     

Single Machine Batch Scheduling Problem with Resource Dependent Setup and Processing Time in the Presence of Fuzzy Due Date

We consider a batch scheduling problem on a single machine which processes jobs with resource dependent setup and processing time in the presence of fuzzy due-dates given as follows:1. There are n independent non-preemptive and simultaneously available jobs processed on a single machine in batches. Each job j has a processing time and a due-date.2. All jobs in a batch are completed together upon the completion of the last job in the batch. The batch processing time is equal to the sum of the processing times of its jobs. A common machine setup time is required before the processing of each batch.3. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource.4. The due-date of each job is flexible. That is, a membership function describing non-decreasing satisfaction degree about completion time of each job is defined.5. Under above setting, we find an optimal batch sequence and resource values such that the total weighted resource consumption is minimized subject to meeting the job due-dates, and minimal satisfaction degree about each due-date of each job is maximized. But usually we cannot optimize two objectives at a time. So we seek non-dominated pairs i.e. the batch sequence and resource value, after defining dominance between solutions.A polynomial algorithm is constructed based on linear programming formulations of the corresponding problems.