一个批处理机随机E/ T 调度问题研究

对批处理机随机E/T(earliness and tardiness)调度问题,假设各批的加工时间独立同分布;各工件的交付期相互独立,并与加工时间独立;目标是极小化所有工件的提前与延迟时间和的均值.在加工时间和工件的交付期都服从指数分布的条件下,得到了最优调度的几个性质,基于这些性质用动态规划给出了一个求问题最优解的算法,此算法的时间复杂度为O(n2B2)(B相似文献   

Unbounded batch scheduling with a common due window on a single machine*

The common due window scheduling problem with batching on a single machine is dealt with to minimize the total penalty of weighted earliness and tardiness. In this paper it is assumed that a job incurs no penalty as long as it is completed within the common due window. It is the first time for the due window scheduling to be extended to this situation so that jobs can be processed in batches. An unbounded version of batch scheduling is also considered. Hence, jobs, no matter how many there are, can be processed in a batch once the machine is free. For two cases that the location of due window is either a decision variable or a given parameter, polynomial algorithms are proposed based on several optimal properties.     

基于PSO-H优化算法的单机E/T调度问题

经典的粒子群优化算法是一个有效的寻找连续函数极值的方法。其在离散空间的应用还很不成熟。主要针对公共交货期下E/T(Earliness/Tardiness)指标的单机调度问题进行研究,并基于粒子群与启发式集成的优化算法(Particle Swarm Optimization integrated with Heuristic:PSO-H)对该问题进行求解。启发式信息由工件加工时间和拖期惩罚构成,它对算法的寻优性能有明显的改善。同时,采用OR-Library中的标准算例对该算法进行仿真实验,显示出理想的寻优结果。     

带有交货期窗口的调度问题及算法

对不同交货期窗口下的提前／拖期单机调度问题进行了分析，给出了最优序列中相邻工件对所满足的必要条件，提出了两个优先级法则，并利用优先级法则设计出遗传算法的交叉算子，在文章的最后，给出了实验结果和结论．     

The Effect of Worker Learning on Scheduling Jobs in a Hybrid Flow Shop: A Bi-Objective Approach

This paper studies learning effect as a resource utilization technique that can model improvement in worker’s ability as a result of repeating similar tasks. By considering learning of workers while performing setup times, a schedule can be determined to place jobs that share similar tools and fixtures next to each other. The purpose of this paper is to schedule a set of jobs in a hybrid flow shop (HFS) environment with learning effect while minimizing two objectives that are in conflict: namely maximum completion time (makespan) and total tardiness. Minimizing makespan is desirable from an internal efficiency viewpoint, but may result in individual jobs being scheduled past their due date, causing customer dissatisfaction and penalty costs. A bi-objective mixed integer programming model is developed, and the complexity of the developed bi-objective model is compared against the bi-criteria one through numerical examples. The effect of worker learning on the structure of assigned jobs to machines and their sequences is analyzed. Two solution methods based on the hybrid water flow like algorithm and non-dominated sorting and ranking concepts are proposed to solve the problem. The quality of the approximated sets of Pareto solutions is evaluated using several performance criteria. The results show that the proposed algorithms with learning effect perform well in reducing setup times and eliminate the need for setups itself through proper scheduling.     

Order scheduling with controllable processing times,common due date and the processing deadline

Due date quotation and scheduling are important tools to match demand with production capacity in the MTO (make-to-order) environment. We consider an order scheduling problem faced by a manufacturing firm operating in an MTO environment, where the firm needs to quote a common due date for the customers, and simultaneously control the processing times of customer orders (by allocating extra resources to process the orders) so as to complete the orders before a given deadline. The objective is to minimize the total costs of earliness, tardiness, due date assignment and extra resource consumption. We show the problem is NP-hard, even if the cost weights for controlling the order processing times are identical. We identify several polynomially solvable cases of the problem, and develop a branch and bound algorithm and three Tabu search algorithms to solve the general problem. We then conduct computational experiments to evaluate the performance of the three Tabu-search algorithms and show that they are generally effective in terms of solution quality.     

平顺移动模式下考虑加工时间与调整时间可分离的多目标流水车间批量调度

对平行顺序移动模式下考虑加工时间与调整时间可分离的多目标流水车间批量调度问题展开研究.构建以加工制造设备总停机次数、批量工件生产周期以及搬运批量工件的总次数为决策目标的基于分层序列法的多目标决策模型,利用该模型可确定批量工件的最优加工排序方案.建立平行顺序移动模式的加工与调整时间模型,该模型是求解生产周期的基础,也是为批量工件的最优调度方案制定生产作业计划的依据.提出并设计平行顺序移动模式下考虑加工时间与调整时间可分离的禁忌搜索算法对问题进行求解.研究结果表明:本研究可为平顺移动模式下考虑加工时间与调整时间可分离的批量生产流水车间选出批量工件的最优调度方案,同时可为批量工件的加工和加工制造设备的调整制定精确的生产作业计划.     

考虑恶化和学习效应的单机成组排序问题

讨论了工件加工时间同时具有恶化和学习效应的单机成组排序问题。在这类问题中,同一组中的工件不允许分开加工,各组之间有安装时间,其中安装时间是工件组开始加工时间的简单线性函数,各组内工件的实际加工时间是关于恶化和学习效应的函数。对目标函数为最大完工时间和总完工时间两类问题分别给出了多项式时间最优算法。     

Hybrid Genetic Algorithms with Fuzzy Logic Controller

SYSTEMS ENGINEERING1. IMTSODUCTIONMachine scheduling problem is the study of constructing schedules of machine processing for a set of jobs inorder to ensure the execution of all jobs in a reasonable amount of time or cost. Usually, it deals with whatmachines to be allocated to which jobs and how to order the jobs in an appropriate processing sequence. Inparallel machine system, two machines are identical and a job can be processed by any one of the free machines.Each finished job …     

A case study for advanced planning and scheduling (APS)

This paper presents a case study for the advanced planning and scheduling (APS) problem encountered in a light source manufacturer. The APS problem explicitly considers due dates of products, operation sequences among items, and capacity constraints of the manufacturing system. The objective of the problem is to seek the minimum cost of both production idle time and tardiness or earliness penalty of an order. An intelligent heuristic is applied to the problem, and the results demonstrate that significant production performances can be achieved while ensuring customer satisfaction as opposed to normal practices followed in the company relying on human expertise.     

不确定条件下不同交货期窗口的Flow Shop调度

研究了具有不同交货期窗口的Flow Shop的提前／拖期调度问题，并考虑了处理时间的不确定性。采用三角模糊数表示不确定性信息，引入两种模糊运算，建立了问题的模糊规划模型，并采用“中间值最大隶属度”的算法将模糊规划模型转化为清晰的非线性规划模型。针对清晰的数学模型提出了基于遗传算法的优化方法，最小化对所有工件提前／拖期惩罚。最后，大量仿真实验验证了算法的有效性。     

一种新的制造系统仿真调度规则

针对制造系统的调度问题，提出了一种新的决策规则。它根据系统的当前状态和各任务的进展情况，综合利用最早交货期优先规则（ＥＤＤ） 的减小最大延迟时间的特点和最小松弛优先规则（ＬＳＫ）的减小最大提前完成时间的特点，在不增加平均推迟的情况下使最大延迟时间和最大提前完成时间之间的区间收缩，向平均值附近逼近，适用于以保证交货期为目标的调度问题。通过仿真证明了该方法的有效性     

An M/M/1 Queueing-Inventory System with Geometric Batch Demands and Lost Sales

This paper studies an M/M/1 queueing-inventory system with batch demands. Customers arrive in the system according to a compound Poisson process, where the size of the batch demands for each arrival is a random variable that follows a geometric distribution. The inventory is replenished according to the standard (s,S) policy. The replenishment time follows an exponential distribution. Two models are considered. In the first model, if the on-hand inventory is less than the size of the batch demands of an arrived customer, the customer takes away all the items in the inventory, and a part of the customer’s batch demands is lost. In the second model, if the on-hand inventory is less than the size of the batch demands of an arrived customer, the customer leaves without taking any item from the inventory, and all of the customer’s batch demands are lost. For these two models, the authors derive the stationary conditions of the system. Then, the authors derive the stationary distributions of the product-form of the joint queue length and the on-hand inventory process. Besides this, the authors obtain some important performance measures and the average cost functions by using these stationary distributions. The results are illustrated by numerical examples.     

有模具约束的平行机台最小拖期和调度问题

针对某电器企业的一个瓶颈工序来制定调度方案，该问题归纳为平行机台具有模具约束，目标为最小拖期和的调度问题．本文提出了如下的启发式算法：根据模具情况运用成组技术对工作成组并生成运行表：按运行表顺序对各个运行中的工作进行指派机台，设置禁忌模具集合，避免对运行的短视性；根据工作的交货期和加工时间选择适当的机台进行加工；在各个机台运用ＮＢＲ（ＮｅｔＢｅｎｅｆｉｔｏｆＲｅｌｏｃａｔｉｏｎ）算法调节顺序以减少拖期和．该算法在厂家的实际测试中，通过三个不同的实例与手工排程进行了比较，各项指标均有明显优势．     

批量制造业交货窗口提前／拖期生产计划方法

建立批量制造企业在交货期窗口下的提前／拖期生产计划模型,将交货期窗口（ｄｕｅ－ｗｉｎｄｏｗ）概念引入到带有能力约束的提前／拖期生产计划中,拓宽了生产计划问题研究的范围．并利用数学推导,将所建模型转化为线性规划模型,使得该模型运用单纯形法就可求取精确的最优解,从而解决了开发中的ＣＯＮＷＩＰ集成化生产管理软件对不确定交货期主生产计划的编制问题．     

Job-Shop调度问题的优化模型及算法

建立了关于 Job-Shop调度问题的一般优化模型 ,将问题归结为双层规划 ,以特例形式给出了最小完工时间与提前 /拖期 Job-Shop调度批量模型 ,构造了一个有效的求解算法 ,数值实验表明了模型及算法的正确性和有效性 .     

整数比策略下含变质产品且缺货部分需补的VMI模型

在不考虑原材料变质而产品变质且订货商处缺货部分需补的集成供应商管理库存(VMI)系统中, 由于生产准备成本的影响, 供应商采用批对批策略生产产品不一定最优, 因此文中允许供应商采购原材料和生产产品均采用整数比策略, 即一次采购的原材料分整数次生产, 一次生产的产品分整数次给订货商供货, 建立了包含一个供应商和一个订货商的VMI模型. 通过基于遗传算法设计的求解步骤得到了一次采购的原材料用于生产产品的次数, 一次生产的产品给订货商供货的次数、供货间隔期以及订货商处的服务水平等决策变量的值. 算例结果表明: 供应商采用整数比策略采购原材料和生产产品可得到VMI系统最小单位时间总成本的满意解; 进一步的分析表明生产准备成本、产品变质率、丢单系数等各自的变化均会对供应商的生产决策以及VMI系统最小单位时间总成本产生影响.     

基于准时制的主生产计划方法

在当今的市场竞争中，能否及时供货和满足客户的要求关系到企业的信誉。为了提高企业的竞争能力，制造业都致力于采用日本的准时生产的策略。在前人研究的基础上，建立了适合于单件小批的主生产计划模型，这一模型有３个特点：（１）保证产品及时交货，也就是提前和滞后于交货期都要受到惩罚；（２）模型考虑了带有小批与单件并存的生产情况；（３）产品对能力的需求数据，考虑了分时段分布特点，并采用聚合算法从工艺路线和产品结构数据聚合而成。在对这一模型构造启发式算法的基础上，实现了主生产计划系统。该系统具有方便的人机界面，能够对由启发式算法产生的解进行修改。     

Allocating fixed costs with considering the return to scale: A DEA approach

When the allocated fixed cost is treated as the complement of other costs, conventional data envelopment analysis (DEA) researches have ignored the effect of the return to scale (RTS) in fixed cost allocation problems. This paper first demonstrates why the RTS should be considered in fixed cost allocation problems. Then treating the fixed cost as a complementary input, the authors investigate the relationship between the allocated cost and the variable return to scale (VRS) efficiency based on the super BCC DEA model. However, the infeasibility problem may exist in this situation. To deal with it, the authors propose an algorithm. The authors find that the super BCC efficiency is a monotone non-increasing function of the allocated cost. Based on the relationship, the authors finally propose a fixed cost allocation approach in terms of principles as: (i) The fixed cost proportion allocated to inelastic DMUs should be consistent with their consumed cost proportion, and (ii) the same efficiency satisfaction degree to the rest DMUs. The optimal allocation scheme is unique. A numerical example and a real example of allocating fixed costs among 13 subsidiaries are employed to illustrate the proposed approach.     

基于资源流网络优化的鲁棒性项目调度

针对项目执行过程中由于活动拖期导致基准调度计划不断变更的问题，从资源分配的角度构建基于资源流网络优化的鲁棒性调度计划。首先设计拖期惩罚成本指标来衡量调度计划的鲁棒性，并构建以拖期惩罚成本最小化为目标的资源流网络优化动态模型。针对该模型设计MTPC资源流网络优化算法，该算法以活动为基准，采用拖期惩罚成本最小的资源分配方案实现资源在活动节点之间的有效流动，提升调度计划的鲁棒性。最后，为验证MTPC优化算法的有效性和可行性，通过采用蒙特卡罗模拟仿真实验将MTPC优化算法与RRAS，Min-EA和MABO等3种资源分配算法进行对比分析。实验结果表明：MTPC算法在调度计划的鲁棒性，资源分配方案的稳定性以及算法的时间效率上都优于其他3种算法。MTPC算法不仅能快速有效地完成资源配置，还能通过降低活动的拖期风险提升调度计划的鲁棒性，这可以帮助项目管理者构建抗干扰能力较强的基准调度计划。