非线性加工时间单机排序问题

讨论工件加工时间是等待时间的非线性增加函数的单机排序问题,目标函数为极小化完工时间和与极小化最大延误.基于对问题的分析,对于一般非线性函数的情况,给出了工件间的优势关系.对于某些特殊情况,利用工件间的优势关系得到了求解最优排序的多项式算法.推广了文献中的结论.     

A Savings Index Heuristic Algorithm for Flowshop Scheduling with Sequence Dependent Set-up Times

This paper considers the permutation flowshop scheduling problem with significant sequence dependent set-up times and develops a savings index heuristic algorithm to find an approximately minimum makespan schedule. The proposed algorithm determines the savings in time associated with a particular sequence and selects the sequence with the maximum time savings as the best heuristic solution. Computational experience indicating the effectiveness and efficiency of the proposed savings index heuristic algorithm are reported and discussed.     

带到达时间的单机排序中的资源分配问题

讨论两个单机排序的资源分配问题1｜rj,pj=bj-ajuj,Cmax≤｜∑uj和1｜rj,prec,pj=bj-ajuj C max≤｜∑uj并给出求其最优资源分配的多项式算法.     

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

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

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

本讨论资源有限的加权总工时间单机排序问题，对现在仍为OPEN问题1｜pj=bj-ajuj，∑uj≤U｜∑wjCj给出了一个有关最优解中最优资源分配的重要性质，并利用该性质分别给出了三种情况bj=b,wj=w,aj=a；bj=b,wj=w,uj=u；aj=a,wj=w,uj=u的最优算法。     

求解带组换装时间单机调度问题的禁忌搜索算法

以包头某钢铁线材企业生产实际调度问题为背景,研究了一类带组换装时间的单机调度问题.由于该问题是NP难的,本文提出了一类适合该问题的禁忌搜索算法.此外,本文将问题性质引入了禁忌搜索算法以进一步提高算法寻优性能,降低算法运行时间.本文提出的算法在随机问题和实际问题上均进行了测试,实验结果表明,本文提出的算法能在不到10秒的时间内获得实际问题的一个近似最优解.     

工件可转包加工的排序问题研究

研究工件可以转包加工的单台机排序问题: 有n个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问题已经被证明是NP-难的. 最后给出该问题的伪多项式时间最优算法, 并且提出一个完全多项式时间近似方案(FPTAS).     

A Worst-case Performance of the Shortest-processing-time Heuristic for Single Machine Scheduling

This paper analyses a worst-case performance of the shortest-processing-time (SPT) heuristic in minimizing a quadratic function of job lateness for single machine scheduling. A sufficient condition on processing-plus-wait due dates is found for the SPT sequence to be optimal. A worst-case lower bound to the optimal solution is derived from the SPT sequence. It is then shown that the SPT sequence is asymptotically optimal. Extensive computational experiments suggest that the SPT heuristic may be a good choice for just-in-time production.     

带运输时间和自动机的法流水作业排序问题的复杂性

研究目标函数为使最大完工时间达到最小的三台机器情况下的流水作业排序问题,同一工件在某台机器上完工后和在下一台机器上开始加工这段时间内,存在称为运输时间的时间间隔,所有的运输工作均由自动机来完成,自动机在同一时间内最多运输一个工件,文章研究该问题及其特殊情况下的复杂性.     

一个不同时刻加工成本有差异的单机排序问题

考虑一个单机排序问题:一批工件在零时刻到达可加工,加工时不可中断,在某个给定时间区间外的加工工时将招致额外的加工成本;当时间区间为给定参数时,要求确定一个最优加工序,当时间区间为决策变量时,要求找到一个最优序及最优区间位置, 由此来最小化总额外加工成本．文中对各种区间外单位加工工时之额外成本的情况给出了多项式算法, NP-hardness的证明及伪多项式时间算法．     

带运输时间和自动机的流水作业排序问题的复杂性

研究目标函数为使最大完工时间达到最小的三台机器情况下的流水作业排序问题, 同一工件在某台机器上完工后和在下一台机器上开始加工这段时间内, 存在称为运输时间的时间间隔, 所有的运输工作均由自动机来完成, 自动机在同一时间内最多运输一个工件, 文章研究该问题及其特殊情况下的复杂性.     

带单服务器的自由作业排序问题的启发式算法

研究带单服务器的自由作业排序问题,证明在只有两台机器且加工时间相同的情况下该问题是强NP-困难的,引入了求解该问题的启发式算法,证明该算法的紧界为5/4.在具有m台机器的情况下,给出相应的启发式算法,其紧界为2-3/(m+2).     

单机排序中一个极小最大绝对迟后问题

本文考虑n个工件在单机上加工的排序问题,工作j的预期开始加工时间和所需加工时间分别为αj,pj,应交工时间为dj=αj kpj d,这里的k(≥0),d是待定的变量,目标函数为极小化最大绝对迟后。本文首先考虑了该问题一些特殊情况的研究结果,然后在强一致性条件下证得此问题O(nlogn)可解。     

几类任务到达时间受资源约束的单机排序问题

本研究了任务到达时间受资源影响的，与时间表长有关的几个问题。对问题1|rj=bj-ajuj,∑j=1^nju≤U|Cmax的一种特殊情况给出了求任务的最优排序的算法，对问题1|rj=fj(uj),pj=p,Cmax≤C|∑j=1^nuj给出了最优算法；还给出了问题1|rj=fj(uj)|∑j=1^nujΛCmax的一个算法。     

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

讨论了一类有准备时间且任务的加工时间依赖资源的单机排序问题.目标函数为最大完工时间与分配给各任务资源消耗量的加权线性组合.给出了问题的若干相关性质.在此基础上,对于任务之间无优先约束和有任意优先约束的情况.分别给出了最优排列算法和最优资源分配方法.并用数值例子作了说明.     

加工时间可控的单台机器排序问题的近似算法

本文研究加工时间可控的单台机器的赋权的总完工时间问题.它是一个NP 难问题.我们利用半定规划松弛的技巧给出它的一个1.2752-近似算法.     

A Hybrid Genetic Algorithm for the Single Machine Scheduling Problem

A hybrid genetic algorithm (HGA) is proposed for the single machine, single stage, scheduling problem in a sequence dependent setup time environment within a fixed planning horizon (SSSDP). It incorporates the elitist ranking method, genetic operators, and a hill-climbing technique in each searching area. To improve the performance and efficiency, hill climbing is performed by uniting the Wagner-Whitin Algorithm with the problem-specific knowledge. The objective of the HGA is to minimize the sum of setup cost, inventory cost, and backlog cost. The HGA is able to obtain a superior solution, if it is not optimal, in a reasonable time. The computational results of this algorithm on real life SSSDP problems are promising. In our test cases, the HGA performed up to 50% better than the Just-In-Time heuristics and 30% better than the complete batching heuristics.     

A Heuristic for a Resource-capacitated Multi-stage Lot-sizing Problem with Lead Times

In this paper we propose a heuristic for the resource-capacitated multi-stage lot-sizing problem with general product structures, set-up costs and resource usage, work-in-process inventory costs and lead times. To facilitate the functioning of the heuristic, we use the formulation of the problem based on Echelon Stock in a rolling horizon scheme. The heuristic first obtains a reasonable solution to the corresponding uncapacitated problem and then tries to attain capacity feasibility by shifting production backwards in time. The concept of echelon stock makes the task of checking the inventory feasibility of proposed shifts easier than would be the case with conventional installation stock. The heuristic is first tested computationally for problems with a five-component product structure over a 12 period planning horizon for which optimal solutions were available and for which optimality precision guarantees were also obtained via Lagrangian Relaxation. The heuristic's performance is also explored with two different 40-component product structures, with high and low set-up costs, and is compared with the Lagrangian precision guarantees.     

具有优先约束的单机随机排序问题

讨论工件的加工时间为常数,机器发生随机故障的单机随机排序问题,目标函数极小化工件的加权完工时间和的数学期望最小.考虑两类优先约束模型.在第一类模型中,设工件间的约束为串并有向图.证明了模块M的ρ因子最大初始集合I中的工件优先于模块中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到机器发生随机故障的情况.在第二类模型中,设工件间的约束为出树优先约束.证明了最大家庭树中的工件优先于家庭树中其它的工件加工,并且其工件连续加工所得到的排序为最优排序并给出了最优算法.     

同顺序流水作业排序问题的一个启发式算法

本文主要给出了同顺序m×n排序问题初始序的选取方法以及通过计算可避免出现高重循环的初始序的排序算法,然后又给出了利用矩阵可行线性质将初始序调试成较优序的可行方法.利用该文方法对n=15,m=3～14的144个例题计算,得出平均相对误差为3.145%的结果,对于m=3与m=4的128个例题计算,得出平均相对误差为0.6306%.统计结果表明该方法可在实际中进行应用.