加权总完工时间有限的受资源约束排序问题

研究1|pj=fj(uj),∑jwjCj≤|∑juj型受资源约束排序问题.针对问题中加工顺序确定的情况给出两个寻求其最优资源分配的算法;就fj=f和fj=b-ajuj,wj=w等问题的最优排序.     

带有资源消耗的加权总完工时间单机排序问题

讨论了带有资源消耗的加权总完工时间单机排序问题,其加工时间是资源量的线性函数,目标函数是完工时间和消耗资源量的加权总和。由于该问题是NP 难问题,所以给出了一个非常有效的局部搜索算法及其算法复杂性和一个算例。利用有关资源分配的性质分别对单位资源分配量的消耗相等、工件的权因子相等、工件的资源分配上限相等和单位资源分配量的消耗相等、工件的权因子相等、工件的正常加工时间相等两种特殊情况给出了最优算法。     

折扣加权总完工时间的调整时间可分离无等待Flow Shop排序问题

研究3台机器调整时间可分离的无等待F1ow Shop排序问题，目标函数为极小化折扣加权总完工时间。对某些特殊情况，给出问题存在多项式最优算法的充分条件。在此条件下得到求解调整时间可分离的无等待F1ow Shop排序问题的分派规则。     

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

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

交货期固定的工件准时完工数——最大排序问题的多项式时间算法

给出了求解交货期固定的工件准时完工数最大的排序问题的多项式时间算法。     

一类加工时间依赖资源的排序问题

讨论一类工件的加工时间受资源约束的单机排序问题1|pj=bj-ajuj,∑uj≤U|∑ωjCj，给出它的最优解的两个性质，证明该类问题是NP-难的。     

具有学习效应的总完工时间流水作业问题

研究工件具有学习效应的2台机器流水作业排序问题.工件的学习效应指工件的加工时间为所排位置的指数函数.目标函数为极小化总完工时间.给出该问题的数学规划模型.同时对大规模问题给出3个启发式算法,计算结果表明,用这3个算法解决所研究问题比较有效.     

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

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

处理机具有不同开始加工时间的排序问题$Q,a_i‖C_{max}$

讨论任务的加工是不可中断、处理机是恒速机的排序问题$Q,a_i‖C_{max}$,证明了用ＬＰＴ算法求解该问题的误差界是２．     

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

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

Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times

A class of nonidentical parallel machine scheduling problems are considered in which the goal is to minimize the total weighted completion time.Models and relaxations are collected.Most of these problems are NP-hard,in the strong sense,or open problems,therefore approximation algorithms are studied.The review reveals that there exist some potential areas worthy of further research.     

Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times

A class of nonidentical parallel machine scheduling problems are considered in which the goal is to minimize the total weighted completion time. Models and relaxations are collected. Most of these problems are NP-hard, in the strong sense, or open problems, therefore approximation algorithms are studied. The review reveals that there exist some potential areas worthy of further research.     

处理机具有准备时间的恒速机排序问题

讨论任务的加工是不可中断,处理机是恒速机且处理机具有准备时间的排序问题,对一般情况的LPT排的界做了改进,同时对m＝2的情况给出了一个与处理机加工速度有关的LPT排序的界。     

IFF算法求解顺序依赖的单机总权重拖期调度问题

转换(启动)时间是工业中带有清洗、更换物料工序的生产过程所需要的, 该时间一般很大程度上依赖于紧接工序. 这种环境下的调度问题都是工件顺序依赖的. 本文研究顺序依赖的单机总权重拖期调度问题, 为NP难的组合优化问题. 针对该问题, 提出了一种迭代的过滤-扇出算法(IFF), 算法以分支树的结构形式在解空间中搜索. 在算法中, 当分支移动不能改进根节点时, 重新产生有继承性的根节点, 使得算法继续进行. 根据问题特性, 提出了带序列片段重组和参考局部搜索的分支移动策略, 获得分支节点. 对文献中的120组数据的算法测试结果表明: 对大多数实例, IFF算法的计算结果优于或不劣于DE算法和DPSO算法的计算结果, 同时改进了42个实例的最好解.     

带不可用时间段的部分可续型单机加权完工时间和调度

研究了机器带有一个不可用时间段的单机最小化加权完工时间和调度问题,并假定被中断工件是部分可续的,即其已加工部分在机器重新可用之后需进行部分重新加工.文中简单说明此问题为NP-难问题,并提出了一种动态规划算法和一种分枝定界算法来求得此问题的最优解.实验结果证实了这两种算法的正确性及有效性,且表明分枝定界算法要优于动态规划算法.     

有里程和时间窗约束的一体化车辆调度智能优化

针对一体化车辆调度问题(vechicle scheduling problem,VSP)提出了一种智能优化方法,采用了基于自然数的配送对路径表示方法,用里程约束来控制车场的插入,以增加惩罚的方式加入时间窗约束,并且设计了里程和时间窗约束的协调系数等措施。用改进的禁忌算法实现了有里程和时间窗约束的集送一体化车辆调度问题。给出了一个具有代表性的算例试验结果和分析,通过试验表明了此方法对优化有里程和时间窗约束的车辆调度问题的有效性。     

有时间窗的非满载车辆调度问题的遗传算法

有时间窗的车辆调度问题是一个典型的ＮＰ－难题,传统求解方法往往不能令人满意,本文将货运量约束和时间窗约束转化为目标约束,设计了基于自然数编码的可同时处理软、硬时间窗约束的遗传算法,实验分析获得了较好的结果。     

Improved differential evolution algorithm for resource-constrained project scheduling problem

An improved differential evolution (IDE) algorithm that adopts a novel mutation strategy to speed up the convergence rate is introduced to solve the resource-constrained project scheduling problem (RCPSP) with the objective of minimizing project duration. Activities priorities for scheduling are represented by individual vectors and a serial scheme is utilized to transform the individual-represented priorities to a feasible schedule according to the precedence and resource constraints so as to be evaluated. To investigate the performance of the IDE-based approach for the RCPSP, it is compared against the meta-heuristic methods of hybrid genetic algorithm (HGA), particle swarm optimization (PSO) and several well selected heuristics. The results show that the proposed scheduling method is better than general heuristic rules and is able to obtain the same optimal result as the HGA and PSO approaches but more efficient than the two algorithms.       

最小化流水时间的工作流资源优化模型和算法

资源在工作流实例间的分配决定了工作流实例中活动的平均处理时间和等待时间,针对优化资源分配,研究使整个工作流的流水时间最小问题。总结了最小化工作流实例的平均响应时间问题的目标和约束条件,提出了以工作流实例平均响应时间最小化为目标的求解最优资源配置数量的方法;建立了最小化工作流时间属性的工作流资源优化数学模型,设计了改进的遗传算法。仿真实验显示,通过适当增加调用的资源数量可减小工作流实例平均响应时间,优化工作流的流水时间。模拟实验通过将提出的改进算法与传统遗传算法的对比,验证了算法的计算效率。