准时生产和宽容交货中的排序问题

本文综述了近年来国内外对宽容交货中排序问题的研究．     

公共交货期窗口的提前／延期惩罚

本讨论n个独立工件在一台机器上加工,而且加工时间服从正态分布的公共交货期窗口的提前/延期惩罚问题,在确定公共交货期窗口情况下,推导出工件的最优排序具有V型特征。     

超前/延误排序问题的进展(英文)

近年来对超前／延误（Ｅ／Ｔ）排序问题进行了广泛的研究．本文总结了对Ｅ／Ｔ排序问题的各种研究中的一些特别领域,虽然没有覆盖所有的新成果,但对该课题有兴趣的读者提供了指导．     

单台机器E-T随机排序问题的多项式算法

本文研究排序问题中的E—T问题，工件在单台机器上加工，n个工件的加工时间都为整数P，相同的工期d为离散分布，满足∑i=1^mP（d=ξi）=1,其中ξ为整数，目标是使E（∑（Ei＋Tj））的期望值最小。应用贪婪算法和二分法思想，我们提出解决该问题的一个最优算法，并得出该算法的复杂性为O（nmlogp）。     

一个超前有奖迟后受罚的排序问题

本文考虑货物装卸管理中船主和港口之间的下述相互制约关系；有n条船在同一时刻到达同一港口，因而也希望在同一时刻完成装卸货物。如某船的货物不能如期装卸完，船主会向港方索取赔偿，反之，如货物提前装卸完，则船主会向港方付取奖金，因此从港方来说是适当考虑n条船的一个装卸程序以使总费用最少。对这样一个NP－困难的排序问题，本文给出了一个动态规划解法，且在逆一致性条件下给出了一伪多项式时间的动态规划算法。     

On the Single-machine Scheduling Problem with Tardiness Penalties

The n-job, single-machine total tardiness problem is considered in this paper. A branching algorithm based on three theorems is proposed to generate a reduced set of candidate sequences. The computational results indicate that the proposed algorithm provides a smaller set of candidate sequences than the DP algorithm of Schrage and Baker.     

A Hybrid Approach to Scheduling with Earliness and Tardiness Costs

A hybrid technique using constraint programming and linear programming is applied to the problem of scheduling with earliness and tardiness costs. The linear model maintains a set of relaxed optimal start times which are used to guide the constraint programming search heuristic. In addition, the constraint programming problem model employs the strong constraint propagation techniques responsible for many of the advances in constraint programming for scheduling in the past few years. Empirical results validate our approach and show, in particular, that creating and solving a subproblem containing only the activities with direct impact on the cost function and then using this solution in the main search, significantly increases the number of problems that can be solved to optimality while significantly decreasing the search time.     

求解带有时间窗和提前/拖期惩罚的飞机着陆问题的遗传算法

研究了带有时间窗、飞机着陆的总提前/拖期惩罚最小为目标函数的飞机着陆问题。针对此问题设计了一种遗传算法进行求解。染色体表示为飞机着陆次序和着陆跑道两个向量,一个新的解码算法来计算飞机的着陆时间。采用数据库OR-Library中的实例进行数值实验,实验结果表明：设计的算法是有效的, 主要原因是解码算法能大大提高解的质量。该算法对于求解带有时间窗、目标函数为提前/拖期惩罚最小的调度问题具有借鉴意义。     

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.     

混合FlowShop环境下的提前／滞后调度问题的遗传算法

讨论了混合Flow Shop环境下的提前/滞后调度问题,这是一个NP-难题。为此,首先给出了问题的数学模型,然后构造了一个有效的遗传算法。最后给出了实验结果和结论。     

具有学习效应的超前有奖延误受罚的排序问题(英文)

本文考虑具有学习效应和共同交货期的单机排序问题.目标函数是加权超前有奖延误受罚总和.我们的目标是寻找一个最优序使得目标函数的值最小.由于该问题是NP-hard的,我们给出一些特殊情况下多项式时间可解的特例.同时在快速估计下界的基础上给出了分支定界算法来求一般情况下的最有排序.     

Heuristics for Flowshop Scheduling Problems Minimizing Mean Tardiness

Several heuristics are presented for the flowshop scheduling problem with the objective of minimizing mean tardiness. We consider the cases in which job sequences on all machines are the same (permutation flowshop) and in which they may be different. For the former case, the various methods that have been devised for minimizing the makespan are modified for our objective, while the list scheduling algorithm is used for the latter case. These heuristics are tested and compared with each other on randomly-generated test problems.     

解特殊工艺约束下提前/拖后调度问题的新遗传算法

针对非一致并行机环境下特殊工艺约束提前/拖后调度问题,设计了一个基于向量组编码的新遗传算法,此算法的编码方法简单,能有效地反映实际调度方案,即清楚地反映出每机器加工产品的代号和顺序.引入浓度概念,对种群中浓度高的个体进行抑制,从而增加群体多样性,同时,利用爬山算法对种群中个体进行局部搜索,提高了种群质量,加快了收敛速度.仿真结果表明,此算法是有效的,适用于解实际的此类调度问题.     

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

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

Scheduling Jobs of Equal Durations with Tardiness Costs and Resource Limitations

In this paper it is shown that the combinatorial problem of scheduling jobs of equal duration with tardiness costs and resource limitations can be solved by formulating the problem as a classical transportation model which is here highly degenerate. A new algorithm derived from the classical stepping stone method is given. The algorithm produces a strict decrease of the objective at each iteration. A special case which could be called the simplest problem of scheduling is also studied.     

极小化最大提前完工费用的可中断排序问题

讨论了带截止期限的$n$个工件在单机上加工,工件间存在优先约束,在允许机器空闲的条件下,确定一个工件的可中断排序,极小化最大提前完工费用.首先考虑两种特殊情形:(1)截止期限相同,存在优先约束;(2)截止期限任意,不存在优先约束.针对两种情形分别给出了时间复杂度为$O(n^2)$的算法.在此基础上,考虑普遍情形,即截止期限任意,存在优先约束,也给出了一个时间复杂度为$O(n^2)$的算法.由于工件不允许延迟,问题可能会无可行排序,需先对问题的可行性进行讨论.     

模糊环境下批量制造业提前/拖期交货的生产计划

描述了基于客户需求为模糊量的批量生产提前/拖期交货的生产计划,并建立了模糊环境下的三个模型.为了有效求解优化模型,我们将模糊模拟和遗传算法相结合给出了混合智能算法.最后通过数值例子说明算法的有效性.     

工件优先级图为非连接图且含环的单机总加权拖期调度问题

为满足实际生产环境对工件加工顺序和工件到达时间的要求,提出了具有新特征的单机总加权拖期调度问题,其特点体现在:工件有动态到达时间,且由工件优先级关系构成的优先级图为非连接图且存在环的情况,对该问题建立数学规划模型,在扩展Tang和Xuan等的基础上,提出了结合双向动态规划的拉格朗日松弛算法求解该问题。在该算法的设计中,提出双向动态规划算法求解拉格朗日松弛问题,使得它可处理优先级图中一个工件可能有多个紧前或紧后工件的情况,采用次梯度算法更新拉格朗日乘子,基于拉格朗日松弛问题的解设计启发式算法构造可行解。实验测试结果显示,所设计的拉格朗日松弛算法能够在较短的运行时间内得到令人满意的近优解,为更复杂的调度问题的求解提供了思路。     

极小化最大提前完工时间的两平行机排序问题

讨论了在两台同型平行机上,加工带截止期限的n个工件,在机器可空闲条件下,确定一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会无可行排序.先讨论问题的可行性,通过子集和问题归约,证明了判定问题的可行性是NP-complete的.如果问题可行,接着讨论了问题的复杂性,通过划分问题归约,证明了其是NP-complete的.最后,考虑了工件加工时间相等的特殊情形,提出了一个算法在多项式时间内获得最优排序.     

带调整时间的一类排序问题

进一步讨论带磨损因子的排序问题,在相应问题中对工件j,j=1,2,…,n,引入了调整时间sj,它同磨损因子bj一样同该工件何时加工无关.要求适当排列这n个工件的加工顺序,使目标函数值达最小.给出了加工全程、完工时间之和及JIT问题在引入调整时间下的最优算法.