机器具有优势关系下的工件加工时间可控的流水作业排序问题

本文主要研究机器具有优势关系下的工件加工时间可控的流水作业排序问题.我们主要对以下两种情形进行了讨论:工件加工时间为线性恶化和线性学习.对于每一种加工模型,我们分别研究了几类不同的优势机器,并且对每种情况均给出了多项式时间算法.     

一类新的可控排序问题

本文讨论了一类新的加工时间可控的单机排序问题,我们所考虑的目标函数由所有工件的加权完工时间之和与对所有工件的实际加工时间偏离额定加工时间的最大满意程度这两部分组成,对此问题,我们提出了一个多项式算法。     

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

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

加工时间可控的单台机器排序问题的近似算法

本文研究加工时间可控的单台机器的赋权的总完工时间问题.它是一个NP 难问题.我们利用半定规划松弛的技巧给出它的一个1.2752-近似算法.     

加工时间可控和恶化的单机最大完工时间排序

本文研究加工时间可控并随开工时间简单线性增长的单机最大完工时间排序问题.该问题将加工时间可控排序和加工时间恶化排序两类研究连接到一起.通过比较技术证明了该问题存在满足以下性质的最优解:每个工件的加工时间或者完全压缩,或者完全不压缩;加工时间完全压缩的工件的顺序由一个工件参数和控制变量的函数的递增序给出,完全不压缩的工件在完全压缩的工件之后以任意序加工.通过将问题等价转换为0-1非线性整数规划问题,给出了单机排序问题的贪婪算法.     

加工时间可控和简单线性增长的平行机排序

本文研究加工时间可控并随开工时间简单线性增长的平行机排序问题.证明了该问题为NP-难问题,该问题存在满足以下性质的最优排序:每个工件的加工时间要么完全压缩,要么完全不压缩;每台机器的工件排序由一个工件参数和控制变量的函数的递增序给出.通过将问题等价转换为0-1非线性整数规划问题,给出了平行机排序问题的贪婪算法.     

工件带简单线性恶化函数和共同交货期单机排序问题

本文研究单机排序问题,其中工件加工时间具有简单线性恶化函数.同时,所有工件均具有一个给定共同交货期.目标函数为最小化提前有奖延误受罚之和.在逆一致性条件下,给出了求解该排序问题的一个伪多项式时间动态规划算法.同时借助于几何舍入技巧,对求解这类排序问题给出了一个充分多项式时间的近似算法(FPTAS)。     

具有学习效应和加工时间可控的平行机排序问题

本文研究了一类不相关平行机的排序问题,在该问题中工件的加工时间既具有学习效应,又资源可控,也就是说在该问题模型中,工件的实际加工时间为其正常的加工时间、加工过程中工件所处位置以及加工时间可控这些变量的函数。该研究的目的是为使得总机器负载和总的控制费用的加权和最小以及总的完工时间和总的控制费用的加权和最小。文章通过对问题的相关性质的分析和证明找到了一个解决问题的最优化算法,并且也证明了在处理机的数量给定的条件下,该问题的时间复杂性为O(n^m+2),最后也给出了相应的数值例子来阐述该问题。     

与交货期有关的供应链排序问题

本文在供应链中把多制造商、多客户的生产和运输集成起来研究,解决工件带有交货期的供应链排序问题.以生产和运输的总费用达到最小作为目标,建立问题的集成排序模型,在分析解的最优性条件基础上,分别用工件的最大延迟和误工工件数作为排序目标,给出相应的动态规划算法,并分析算法的复杂性.     

Asymmetric Earliness and Tardiness Scheduling with Exponential Processing Times on an Unreliable Machine

We address the problem of processing a set of jobs on a single machine under random due dates with a common distribution. The processing times of the jobs are exponentially distributed random variables with means _i , and the machine is subject to stochastic breakdowns governed by a Poisson process. Each job i is associated with a job-dependent weight w _i . The objective is to schedule the jobs so as to minimize the expected sum of the weighted earliness and tardiness costs of all jobs, which are quadratic functions of the deviations of job completion times from the due dates. We show that the problem is NP-complete. Nevertheless, important optimality properties exist, which can be utilized to develop effective algorithms to solve the problem. Specifically, we prove that, in the case where the weights assigned to both the earliness and tardiness are symmetric, an optimal sequence for the problem must be V-shaped with respect to { _i /w _i }, in the sense that the sequence will first process jobs in a nonincreasing order of { _i /w _i } and then in a nondecreasing order of { _i /w _i }. In the case where asymmetric weights are assigned to the earliness and tardiness costs, the optimal sequence must also be V-shaped with respect to { _i /w _i }, if the due dates are exponentially distributed. Dynamic programming algorithms are proposed which can find the best V-shaped sequences.     

非线性加工时间单机排序问题

讨论工件加工时间是等待时间的非线性增加函数的单机排序问题,目标函数为极小化完工时间和与极小化最大延误.基于对问题的分析,对于一般非线性函数的情况,给出了工件间的优势关系.对于某些特殊情况,利用工件间的优势关系得到了求解最优排序的多项式算法.推广了文献中的结论.     

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

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

Minimizing Completion Time Variance with Compressible Processing Times

We introduce a new formulation of the standard completion time variance (CTV) problem with n jobs and one machine, in which the job sequence and the processing times of the jobs are all decision variables. The processing time of job i (i=1, ,n) can be compressed by an amount within [l_i, u_i], which however will incur a compression cost. The compression cost is a general convex non-decreasing function of the amount of the job processing time compressed. The objective is to minimize a weighted combination of the completion time variance and the total compression cost. We show that, under an agreeable condition on the bounds of the processing time compressions, a pseudo-polynomial algorithm can be derived to find an optimal solution for the problem. Based on the pseudo-polynomial time algorithm, two heuristic algorithms H1 and H2 are proposed for the general problem. The relative errors of both heuristic algorithms are guaranteed to be no more than , where is a measure of deviation from the agreeable condition. While H1 can find an optimal solution for the agreeable problem, H2 is dominant for solving the general problem. We also derive a tight lower bound for the optimal solution of the general problem. The performance of H2 is evaluated by complete enumeration for small n, and by comparison with this tight lower bound for large n. Computational results (with n up to 80) are reported, which show that the heuristic algorithm H2 in general can efficiently yield near optimal solutions, when n is large.     

恶化率与工件无关的线性加工时间调度问题

讨论恶化率与工件无关的线性加工时间调度问题 .对于工件间具有平行链约束 ,目标函数为极小化最大完工时间的单机问题 ,分别就链不允许中断和链允许中断两种情况给出了最优算法 .对于工件间没有优先约束 ,目标函数为极小化完工时间和的平行机问题 ,证明了工件按基本加工时间不减排列可以得到最优调度 .     

工件有尺寸且分两批到达的单机分批排序

本文首次研究了工件有尺寸大小,有到达时间的分批排序问题,这里目标函数为工件的极大完工时间．就所有工件有两个到达时间的且工件加工时间与尺寸大小一致的排序给出算法,并证明了算法的性能比不超过33/14．     

基于一般学习效应下的单机排序问题

近来具有学习效应的机器排序问题收到广泛的关注.对于机器排序中工件的实际加工来说,与工件加工位置有关的学习模型更具有现实性.本文研究了工件加工位置和与已经加工过的工件之和有关的一般学习效应模型.首先证明文献中与位置和已经加工过的工件加工时间之和有关的学习模型是本模型的特殊情形.其次对于单机排序问题我们提出一般解法.