准时生产制（JIT）排序问题的发展和动态

本文综述十几年来国内外在准时生产制排序领域中取得的研究成果，提出这一领域有特继续研究的一些问题。     

一个宽容交货超前延误单机排序问题

此文考虑下述排序问题（P）：有n个工件需在同一台机器上加工,对各工件有一共同的宽容交货期。若一工件在此宽容期前完工则为一超前工件,若在此宽容期后完工则为一延误工件,要求适当安排一加工方式和宽容交货期的位置使加权超前延误工件数量小。文中证得（P）是NP-hard的,并给出一伪多项式时间的分枝状精确算法,这也就可以认为它是一般意义下的NP-hard问题而不是强NP-hard问题。     

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

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

具有相同批容量和相同工期的单机准时分批排序问题

研究具有相同批容量和相同工期的单机准时分批排序问题.这里相同批容量是指每批加工的工件数相同且恰为b个.准时排序要求工件在工期准时完工,提前或误工均受到惩罚.在两种分批方式下进行排序:继列分批和平行分批.目标函数为最小化加权总绝对误差和加权非准时惩罚.这里的权重不是工件自身所拥有的,而是工件所在的批一旦排在某个位置所获得的位置权重.证明了这些问题均可在O(nlogn)时间内解决.     

需求受价格、交货时间和服务水平影响下订单生产决策研究

在需求受价格、交货时间和服务水平影响环境下,考虑订单生产为M/M/1排队模型,建立订单生产价格与产能,交货时间与产能,价格、交货时间与产能决策模型.研究表明:对于价格与产能模型,当交货时间较小时,交货时间具有溢价作用和需要较多的产能才能缩短交货时间;对于价格、交货时间与产能模型,最优产能、最优价格与最优交货时间绑定于服务水平上,降低产能单位成本或提高服务水平可以增加利润.     

汽车企业集团的准时化集中生产配送系统研究

汽车企业集团的准时化集中生产配送是供应链物流一体化的重要环节。实现汽车企业集团的准时化集中生产配送,要明确其目标,做好供应商关系、配送物流的统一运作、基础数据、信息网络、配送中心仓库作业设备的现代化和领导支持六个方面的基础工作;针对我国汽车企业集团的实际,构建准时化集中配送系统的框架及流程;在准时化集中配送系统运作上探讨了包括配送资源的整合、配送中心库区的划分、配送中心库位管理、配送中心库存管理、不同物料配送流程(、6)配送中心信息系统、物料索取系统等七个方面问题。     

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

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

重入排序问题综述

重入排序问题打破传统假设：工件在加工过程中不止一次地访问某台机器,是一种新型的排序问题. 重入的特点源于半导体生产, 并广泛存在于其他领域. 对重入排序问题已有文献中的成果进行梳理和分析,按问题所处机器环境的不同, 对内容和方法进行分类介绍和总结：包括单机问题、流水作业问题、混合流水作业问题及其他机器环境下的重入排序问题. 最后展望未来的趋势和研究方向.     

排序问题中的凸性

凸性在连续性最优化理论中起着重要的作用，它在离散性最优化中的相应概念尚待研究，本文运用差分和次梯度的概念给出排序问题中离散凸性的描述，并指出凸性在构造最优排序中的重要性。     

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

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

Parallel-Machine Scheduling Problems with Earliness and Tardiness Penalties

We consider the problem of assigning a common due-date and sequencing a set of simultaneously available jobs on several identical parallel-machines. The objective is to minimize some penalty function of earliness, tardiness and due-date values. We show that the problem is NP-hard with either a total or a maximal penalty function. For the problem with a total penalty function, we show that the special case in which all jobs have an equal processing time is polynomially-solvable.     

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

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

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

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

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

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

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

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

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.     

Scheduling problems with random processing times under expected earliness/tardiness costs

This work is concerned with scheduling problems for a single machine. Taking earliness and tardiness of completion time and due–date value into consideration, the objective function with a common due date is considered. The processing time of each job is random. Sufficient conditions guaranteeing an optimal SEPT sequence are derived. Under exponential and normal processing times, further results are obtained     

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.