树约束线性加工时间的单机排序问题

讨论工件具有线性加工时间,工件间优先约束为树约束的单机排序问题。当目标函数为极小化加权完工时间和时,问题比相应的经典排序问题复杂,在工件间优先约束为出、入树2种情况下,分别给出了该问题最优排序的多项式算法。     

链约束线性加工时间单机排序问题

讨论工件具有线性加工时间,工件间具有链约束的单机排序问题。目标函数为极小化加权完工时间和。在这类问题中,工件的加工时间是其开工时间的线性函数。对链不允许中断和链允许中断两种情况分别给出了最优算法。     

加工时间线性递减的平行机排序问题

主要讨论了具有两台处理机的平行机排序问题和每批恰为k个工件的串行工件同时加工排序的平行机排序问题。在这两个问题中,工件加工时间均为开工时间的线性递减函数,目标函数为极小化总完工时间。对于第一个问题,证明了其最优排序可由工件按基本加工时间不减排列得到,由此得出其最优算法,并指出了该结论对于加工时间随开工时间线性递增的情况并不成立。对于第二个问题,根据其与第一个问题在某些性质上的相似性,给出了其最优算法。最后指出所讨论的两个问题的结论均可推广到m台处理机的情况。     

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

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

一类资源约束单机排序问题

讨论具有连续资源的单机排序问题．在这一模型中，工件的释放时间是所消耗资源的非负严格减少连续函数，工件的加工时间是开工时间的严格增加线性函数．考虑两类问题，第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量、第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间．对两类问题讨论了最优排序的某些特征．基于对问题的分析，分别给出了求解最优资源分配的方法．结果表明，加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立。     

链优先约束工件单机随机排序问题

讨论单机随机排序问题，目标函数为确定工件的排列顺序使工件的加权完工时间和的数学期望最小。设工件问具有平行链优先约束，机器发生随机故障。考虑两种情况，第一种情况是链不允许中断．第二种情况是链允许中断，对两种情况分别给出最优算法。     

具有优势机器和恶化工件的流水作业排序问题

针对流水作业排序问题,建立了具有优势机器和恶化工件并且有无空闲限制的排序模型.在该排序模型中,机器加工工件时,工件的相邻加工工序之间不允许出现空闲,工件的加工时间是其开工时间的严格增加线性函数.其中讨论的优势机器有2种情况:机器形成增减增优势关系和机器形成减增减优势关系.考虑了多台机器的流水作业排序问题,其中,目标函数分别为极小化最大完工时间和极小化总完工时间,对于这两类问题分别给出了求解最优排序的多项式算法和它们的计算复杂性,并通过证明证实了算法的有效性.     

线性减少加工时间的资源约束单机排序问题

讨论具有连续资源的单机排序问题。在这一模型中,工件的准备时间是所消耗资源的非负严格减少连续函数,工件的加工时间是开工时间的严格减少线性函数。考虑两类问题,第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量。第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间。对两类问题讨论了最优排序的某些特征。基于对问题的分析,分别给出了求解最优资源分配的方法。结果表明,加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立。     

带有减少线性恶化效应的双代理调度问题

本文研究带有减少线性恶化效应的双代理单机调度问题.该问题来源于钢铁企业中的连铸-轧制生产过程.两个代理在共同的单机上竞争加工各自的工件,每个代理都有自己的目标函数需要优化.目的是找到一个调度使得满足第二个代理的目标函数不超过一个给定的上界的约束下,第一个代理的目标函数最小.本文把减少线性恶化效应引入到双代理调度中,工件的加工时间定义为它们开始时间的减少线性函数.对于带有减少线性恶化效应的双代理单机调度的两个问题,分别给出了问题的一些最优性质,并提出了多项式时间最优算法.     

一类带有安装时间的单机成组排序问题

针对一类带有准备时间和安装时间的单机成组排序问题,给出了求解最优排序的多项式算法。其中每个工件都具有自己的准备时间,组和组之间具有安装时间,并且安装时间和已经加工完工件的加工时间有关。所有工件在机器上加工时,一次只能加工一个工件,工件不可中断,组内工件连续加工,组和组之间需要安装时间。对目标函数为极小化最大完工时间的单机成组排序问题,给出了求解最优排序的多项式算法。原问题不是成组问题,为此在原问题的基础上添加了工件的成组问题且组内每个工件都具有自己准备时间,其结果是依然能给出求解最优排序的多项式算法。     

MPS上作业的分配和调度问题

多处理机系统MPS(MultiprocessorSystem)上作业的分配和调度问题是其运行效率的关键.本文讨论的是具有不相容性作业集的作业分配和调度问题,提出了一种启发式方法及其定量分析技术,并证明了相关定理和若干推论.     

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

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

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

讨论了平行机串联工件同时加工排序问题。目标函数是极小化加权总完工时间,并假设满足每批均含有k个工件,并且每批的加工时间为该批中所有工件的加工时间之和。对平行机的情况,该问题是强NP难的。本文主要针对该问题的两种特殊情况:(1)所有工件的权相等;(2)所有工件的加工时间相等,分别给出了最优算法,分析了算法的时间复杂性,同时用数值例子作了说明。     

On-Line Scheduling of Unit Time Jobs with Rejection on Uniform Machines

The authors consider the problem of on-line scheduling of unit execution time jobs on uniform machines with rejection penalty. The jobs arrive one by one and can be either accepted and scheduled, or be rejected. The objective is to minimize the total completion time of the accepted jobs and the total penalty of the rejection jobs. The authors propose an on-line algorithm and prove that the competitive ratio is 1/2 （2 W √3） ≈ 1.86602.     

具有阻塞影响的柔性制造系统排队网络模型

用有限容量局部库区的开排队网络模拟柔性制造系统，模型中，机床加工工件的时间服从指数分布，运送台车按照静态Ｍａｒｋｏｖ方式运送工件且运送时间服从指数分布，被阻塞的工件按照ＢＡＲ机理被处理，静态Ｍａｒｋｏｖ工件运送方式中的概率值受工件被阻塞的影响。     

工件带有温降的生产与前运输协调调度问题

研究单机环境下生产与生产前运输的协调调度问题,目标函数是最大完成时间最小化.具有热状态的工件等待加工时温度降低会导致处理时间的增加,从而假设具有热状态工件的实际处理时间为等待时间与初始处理时间之和,温度无变化工件的处理时间不变.对于车辆数为1,被调度工件均温度不变化问题,给出最优算法;证明了车辆数为1,同时存在热状态工件和温度不变化工件的调度问题和车辆数为2,同时存在热状态工件的调度问题是强NP困难问题.     

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.     

An improved branch-and-bound algorithm to minimize the weighted flowtime on identical parallel machines with family setup times

This article investigates identical parallel machines scheduling with family setup times. The objective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.