两个带有分批费用的平行分批排序问题的算法

本文研究两个带有分批费用的平行分批排序问题.平行分批是将工件集分割成若干批在机器上成批加工,机器可同时加工在一批的多个工件,每批的加工时间等于该批中最大的加工时间.假设每分一批都产生一个固定的分批费用,本文目标是将工件分成若干批且排出各批的加工顺序,使目标值最优.这里假定工件和批处理机都在零时刻到达,一旦开始加工就不允许中断.本文利用动态规划方法分别给出下面两个问题的多项式时间算法:一是最小化总加权完工时间与分批费用之和;二是最小化最大延迟与分批费用之和.     

同时最优化时间表长与总完工时间的双代理单机序列分批排序问题（英）

本文研究在一台序列分批处理机上同时最优化$A$代理的时间表长和$B$代理的总完工时间的双代理排序问题．在序列分批的背景下,工件被分批加工（但不同代理的工件不能在同一批中加工,且每个代理都希望最小化仅依赖于各自工件完工时间的费用函数）且一批的加工时间等于这一批中所有工件的加工时间和．而且在一个新批开始加工前,机器有一个常数的安装时间．此外,根据批容量,序列分批模型又被分成有界模型和无界模型．在本文中,我们对所研究问题的有界模型和无界模型分别给出了一个多项式时间算法．     

具有双工期的最小化最大延迟的双目标排序

本文研究一个双目标排序问题.由于决策者的利益不同,他们对工件的加工有不同的工期要求,因而可导出两个最大误工问题.我们证明了可在多项式时间内找到关于这两个目标函数的所有Pareto最优点.     

供应链管理中生产和运输集成的排序问题

分析了供应链管理中多制造商、多客户的生产和运输集成起来的排序(调度)问题.建立了集成排序模型,在研究解的最优性条件基础上,用工件的总流程时间作为排序目标,解决使总费用达到最小的问題,给出相应的动态规划算法,并分析算法的复杂性.     

使带权总完工时间为最小的自由作业排序问题

本文研究多工序排序中的一类自由作业模式。对于使机器带权总完工时间为最小或者使工件带权总完工时间为最小的两类问题,本文用组合方法或者数学规划方法分别给出了稠密时间表的算法或者置换排序的算法,并分析算法的性能比。此方法在理论和应用两方面都是有意义的。     

多任务在多处理机上执行的排序问题研究

随着网络的日益普及,研究如何合理地安排网络资源的下载具有重要的理论意义和实际应用价值。本文首先建立的解决网络资源下载排序问题的数学模型;然后结合具体的实例给出了具体的下载方案,并指出贪婪算法排序有时并非是最优的排序;最后给出了采用贪婪算法需要的下载时间与最小下载时间之间的关系。该种分析过程对于解决最优排序问题具有一定的参考价值。     

反相容工件系统的加权完工时间和的重新排序问题

重新排序问题是指在原始工件已经安排好的情形下,新到的工件集与原始工件集一起重新再排序,这是实际工作中常见一类优化问题。本文考虑了单机上当工件加工时间与权重反相容时,在最大错位量约束下的加权完工时间和最小化的重新排序问题。对于提出的四个问题,即在最大序列错位、最大时间错位、总序列错位和总时间错位约束下的加权完工时间和重新排序,基于问题的结构性质,运用动态规划方法分别给出了这些问题的多项式时间或拟多项式时间算法。     

总迟后相关的两个工况代理的单机排序问题

研究了两个代理的单机排序问题.其中一个代理以工件总迟后相关的为目标函数(总迟后和加权总迟后),第二个代理以最大费用函数为目标函数.排序问题的目标就是寻找一个序列,使得在第二个代理的目标函数不超过给定的上界的情况下,第一个代理的目标函数最小.对于总迟后的情形,并给出拟多项式时间的动态规划算法.当第一个代理中的工件具有相等工期时,考虑了加权总迟后问题,并给出了一个多项式时间算法.最后对于总迟后问题给数值实验.     

关于工期分配与加权误工数的双指标排序问题

排序问题中工期分配的目的是处理分配费用与性能指标的利益平衡,由此提出工期分配的双目标排序问题。关于工期分配与加权误工数的单机双指标排序问题,文献中只研究了其线性组合形式。针对该问题,本文针对约束形式及Pareto优化形式进一步研究了更多的模型。主要结果包括NP-困难性、多项式可解情形以及多项式时间近似方案等结果。通过这些结果,一个多目标优化问题的特征得以完整地刻画。     

具有区间摄动鲁棒性的调度问题

本文讨论了目标函数为折扣加权总完工时间的调度问题。对调度问题中最优调度关于加工时间在某一闭区间上任意变化时的不变性进行了讨论,得出了当加工时间在某一闭区间上变化时最优调度不变的充要条件。     

考虑工序并行的差异工件批调度研究

针对铸造车间差异工件组批多约束的问题,在工序可并行加工的前提下构建以最小化最大完工时间和最小化沙箱空置率为优化目标的并行工序批调度模型,设计一种改进和声算法求解该调度模型,提出一种单工序编解码方式和2种机器分配规则用于解决工件分批、沙箱选择、工序分配及机器选择的问题。在算法中提出一种新的和声产生方式和更新机制,同时为改善算法的局部搜索能力,加入模拟退火算法执行局部搜索过程。最后根据企业实际生产数据进行仿真实验,验证本文模型的有效性。     

等待时间受限的并行批处理调度问题研究

研究了任务等待时间受限的并行批处理调度问题,建立它的约束规划模型,设计调度任务的“小s大S”规则,该调度规则最重要的参数为临界队长参数和考虑受限时间的紧急时间参数.基于该规则进行模拟实验,用RSM响应面方法进行参数优化,将模拟结果同约束规划模型(CP方法)在CPLEX环境下求得的解进行比较,分析“小s大S”规则的性能和效果.     

求解一类无关并行机调度的遗传迭代贪心算法

以最小化最大完工时间为优化目标,建立带工单加工约束和序相关设置时间无关并行机调度问题的混合整数规划模型;考虑现实生产对求解算法在质量、收敛速度和鲁棒性等方面的较高要求,构建一种混合遗传-迭代贪心算法。在遗传变异操作中嵌入一种迭代贪心策略的破坏和构建机制,用于提高算法的种群多样性;引入基于破坏与构建操作设计而成的快速局部搜索算法来增强算法的局部开发能力;基于实际生产数据的相关特征随机生成了一系列计算案例,并通过实验说明所提新型混合算法相较于传统混合算法的优越性。     

Parallel machine scheduling with tool loading: a constraint programming approach

This paper presents constraint programming models that aim to solve scheduling and tool assignment problems in parallel machine environments. There are a number of jobs to be processed on parallel machines. Each job requires a set of tools, but limited number of tools are available in the system due to economic restrictions. The problem is to assign the jobs and the required tools to machines and to determine the schedule so that the makespan is minimised. Three constraint programming models are developed and compared with existing methods described in the literature.     

基于最优解下限的单工序平行机排序启发式算法

针对单工序平行机排序LPT方法计算步骤多等问题,提出了一种适用于中小企业现场排序的最优解下限截取启发式算法。传统平行机排序最优解下限表达式存在因偏离最优解过大而难以引导排序走向最优的缺陷,改进后的下限表达式更加接近于最优解。从计算步骤多少和偏离最优解下限的最大偏差率两个角度,比较分析了最优解下限截取法与LPT法的特点。经实验数据验证,得出零件数与平行机数之比非整除且满足一定条件时,简单易行的截取法更优于LPT法的结论。     

考虑有限可用性可控的两批次并行机调度研究

构建了一个考虑有限可用性可控的两批次并行机调度模型.每台机器在考虑周期内可实施一次关机操作,由此形成一个不可用的时间段,关机开始时间和长度都不确定,需要在决策过程中决定,目标是最小化由完成时间和关机时间组成的总成本.先证明了问题最优解的一些性质,然后采用了基于列生成的分支定界法来求解,并结合了动态规划法来提高方法的效率...     

三坐标批量测量典型零件的方法

在相同类型零件测量任务中,一次性送检批量零部件时,按照原单件零件的测量方法,不能按时完成任务。为准确而高效的实现批量测量,需研究并改进原有方法。本文通过研究典型零件如回转件测量点数对测量结果的影响、设计固定夹具、建立坐标系、设计编写程序模块,实现了批量零件多件同时连续不间断自动测量及测量结果自动文本输出,建立了批量关键件的自动化测量方法。此方法在保证测量结果准确性的同时,提高了测量效率,减轻了劳动强度,为科研和生产提供了有效保障。     

带成组加工的二阶段柔性流水作业问题

本文仔细剖析混杂二阶段流水作业问题,其中第一阶段由m台同型机组成,第二阶段由一台批处理机M组成,并以最大完工时间Cmax为极小化目标函数.我们证明了该类问题除一种情况有多项式时间可解外,其余情况为(强)NP-hatd的.文中对所有(强)NP-hard情况均给出了近似算法并作了性能比分析.