具有禁用区间的单机最小化加权完工时间和排序问题

研究具有禁用区间的单机最小化加权完工时间和排序问题.在该问题中,有一些禁用区间已经固定在机器上,工件将被安排在其余自由区间内进行加工且不能与禁用区间重叠.在文献中已经证明,该问题是强NP-困难的,并且在P不等于NP的假设下,该问题不存在2~(q(n))-近似算法.其中,n是工件个数,而q(n)是n的任一多项式.但是,其精确最优算法尚属未知.给出了该问题的一个动态规划最优算法.当禁用区间的数目是固定常数时,该算法是拟多项式的.     

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

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

求带释放时间的半导体煅烧排序的最短交付时间的一个高效PTAS

本文研究一个目标是最小化最大交付时间的能分批处理的非中断单机排序问题．这个问题来源于半导体制造过程中对芯片煅烧工序的排序．煅烧炉可以看成一个能同时最多加工B（〈n）个工件的处理机．此外，每个工件有一个可以允许其加工的释放时间和一个完成加工后的额外交付时间．该问题就是将工件分批后再依批次的排序加工，使得所有工件都交付后所需的时间最短．我们设计了一个用时O（f（l／ε）n^5/2）的多项式时间近似方案，其中关于1／ε的指数函数厂（1／ε）对固定的ε是个常数.     

一个非常规目标函数的单机随机调度的最优策略

本文考虑了n个工件在同一台机器上加工的调度问题 ,其中工件的加工时间和交货期都是具有任意分布的随机变量 .我们考虑了一个非常规目标函数 ,其中工件的权数与平均加工时间成比例 .在工件的交货期与加工时间满足相容条件下 ,得到了个简单的最优排序策略 .     

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

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

加工时间是开工时间线性分段函数的单机总误工问题

研究工件加工时间是开工时间的线性分段函数的单机排序问题,其中工件的加工时间是开工时间的线性增加函数,但是有一个上界,在时刻T(T是已知常数)以后开始加工的工件,其加工时间不再因开工时间的推迟而增大,优化的目标是极小化总误工工件数.当工件的工期与加工时间满足某种一致性关系的时候,不管工件的加工时间是开工时间的简单线性分段函数,还是其基本加工时间是与恶化率有关的分段线性函数,证明这两种情况都是多项式时间可解的.     

工件可转包加工的排序问题研究

研究工件可以转包加工的单台机排序问题: 有n个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问题已经被证明是NP-难的. 最后给出该问题的伪多项式时间最优算法, 并且提出一个完全多项式时间近似方案(FPTAS).     

具有线性恶化效应的在线分批排序问题

本文研究一类具有线性恶化效应的单机在线分批排序问题,工件$J_j$的加工时间为$p_j=b_j+\alpha t$, 其中$b_j$为基本加工时间, $\alpha>0$为恶化率, $t$是开工时间. 工件的到达时间是未知的, 工件的基本加工时间只有在工件到达之后才能知道.多个工件可以作为一批被机器同时加工, 批的加工时间为该批中工件最大加工时间.本文对于目标为极小化makespan的批容量无限的单机问题给出一个在线算法$\beta H^\infty$,并证明其竞争比和问题的下界相同, 进而算法是最优的.     

极小化最大完工时间的单机分批加工问题

本文考虑极小化最大完工时间的单机分批加工问题．设有n个工件和一台批加工机器．每个工件有一个释放时间和一个加工时间．批加工机器可以同时加工b(b相似文献   

一类具有资源约束和优先加工顺序约束极小化加权总完工时间调度优化问题研究

本文针对工件间具有链状优先约束和relocation资源约束的极小化加权总完工时间调度优化问题展开研究.针对这一NP难问题,利用relocation约束的性质和贪婪算法的思想,设计了一个多项式近似算法,并证明了当链不可中断,每个链具有相同工件数和工件间具有相同加工时间时,2为该算法的紧界.     

On A Scheduling Problem of Time Deteriorating Jobs

We consider a scheduling problem with a single machine and a set of jobs which have to be processed sequentially. While waiting for processing, jobs may deteriorate, causing the processing requirement of each job to grow after a fixed waiting timet₀. We prove that the problem of minimizing the makespan—completion time for all jobs—is NP-hard. Next we consider the problem for a natural special case where the job requirement grows linearly at a job-specific rate aftert₀. We develop a fully polynomial time approximation scheme for the problem in this case. We also give further NP-hardness results, and a polynomial time algorithm for the case where the job-specific rate is proportional to the initial processing requirement of each job.     

最小化加权误工工件数的多代理平行分批排序

考虑多代理的平行分批排序,不同代理的工件不能放在同一批中加工,目标函数是最小化加权误工工件数.本文考虑两种模型,证明了甚至当所有工件具有单位权时,这两个模型都是强NP困难的.但当代理数给定时,这两个问题都可在拟多项式时间解决,并且当工件具有单位权时,可在多项式时间解决.进一步证明当代理数固定时,两个问题都有FPTAS算法.     

具有特殊工件的平行机在线排序问题

本文研究一类具有特殊工件的平行机在线排序问题,目标是最小化最大完工时间.此模型有两种工件:正常工件和特殊工件.正常工件能够在m台平行机的任何一台机器上加工,而特殊工件仅能够在它唯一被指定的机器上加工.文中所有特殊工件的指定机器为M1.我们提供了竞争比为(2m2-2m 1)/(m2-m 1)的在线近似算法.当m=2时,算法是最好可能的.当m=3时,算法的竞争比为13/7≈1.857,并且提供了竞争比的下界(1 (平方根33))14≈1.686.     

Integrated scheduling of production and distribution for manufacturers with parallel batching facilities

We consider a class of integrated scheduling problems for manufacturers. The manufacturer processes job orders and delivers products to the customer. The objective is to minimize the service span, that is, the period lasting from the time when the order is received to the time when all the products have been delivered to the customer. In the production phase, parallel batch-processing facilities are used to process the jobs. Jobs have arbitrary sizes and processing times. Each facility has a fixed capacity and jobs are processed in batches with the restriction that the total size of jobs in a batch does not exceed the facility capacity. When all the jobs in a batch are completed, the batch is completed. In the distribution phase, the manufacturer uses a vehicle with a fixed capacity to deliver products. The transportation time from the manufacturer to the customer is a constant. Completed products can be delivered in one transfer if the total size does not exceed the vehicle capacity. We first consider the problem where jobs have the same size and arbitrary processing times. We propose approximation algorithms for the problem and we show that a worst-case ratio performance guarantee is respectively 2–1/m. Then we consider the problem where jobs have the same processing time and arbitrary sizes. An approximation algorithm is proposed with an absolute worst-case ratio of 13/7 and an asymptotic worst-case ratio of 11/9. Both the proposed algorithms can be executed in polynomial time.     

Approximability of single machine scheduling with fixed jobs to minimize total completion time

We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1 − δ)n-approximation algorithm exists even if all the release dates are zero, for any constant δ > 0, if P ≠ NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2 − δ)-approximation algorithm, for any constant δ > 0, if P ≠ NP, and for the weighted version, we show that the problem has no polynomial-time 2^q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem.     

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

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

单位工件的平行机并行分批在线排序问题的算法

本文研究一类批容量有界的并行分批、平行机在线排序问题。模型中有n个相互独立的工件J={J₁,…,J_n}要在m台批处理机上加工。批处理机每次可同时加工至多B(Bj(1≤j≤n)的到达时间为r_j,加工时间为1,工件是否会到达事先未知,而只有等到工件的到达时间才能获知它的到达。目标为最小化工件的最大完工时间。针对该排序问题,本文设计了两个竞争比均达到最好可能的在线算法。     

单机最优交货期决策及工件排序

本文考虑n个独立工件在一台机器上加工的排序问题,每个工件J_i的交货期设置为d_i=kP_i~α(α≥1),目标是寻找工件最优加工时间乘子及工件最优排序S(?),使工件完工时间与交货期的最大偏差最小。给出寻找最优加工时间乘子k(?)及工件最优排序S(?)的方法。