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

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

带有运输且加工具有灵活性的无等待流水作业排序问题

研究一类带有运输且加工具有灵活性的两阶段无等待流水作业排序问题, 其中每阶段只有一台机器, 每个工件有两道工序需要依次在两台机器上加工, 工件在两台机器上的加工及两道工序之间不允许等待. 给出两种近似算法, 并分别分析其最坏情况界. 第一种算法是排列排序, 证明了最坏情况界不超过5/2; 第二种算法将工件按照两道工序加工时间之和的递增顺序排序, 证明其最坏情况界不超过2. 最后, 通过数值模拟比较算法的性能. 对问题中各参数取不同值的情况, 分别生成若干个实例, 用算法得到的解与最优解的下界作比值, 通过分析这些比值的最大值、最小值和平均值来比较上述两个算法的性能.     

一类带机器准备时间的排序复杂性及算法

1引言文[2-4]中考虑了如下定义的一个排序模型：m台同型机器加工n个工件，每个工件在零时刻到达，第i个工件需加工时间pi,而各机器有各自的准备时间Tj≥0,怎样安排工件加工顺序，使机器总完工时间（makespan）尽可能早．这是一个强NP-完全问题．本文考虑增加这样一个约束，即每     

二台机器的流水作业中存在调整时间的LOT—STREAMING问题

对二台机器流作业中的Ｌｏｔ－Ｓｔｒｃａｍｉｎｇ问题（简称ＬＳ），以往的研究多为固定分批数寻找各批大小，或对二台机器引入相同的调整时间，寻找量优分批数及和批大小，本文对机器１，２每生产一个新的子批量分别引入一独立的调整时间Ｓ１，Ｓ２，研究同时决定最优分批数和最优分批大小，并给出相应的最优算法。     

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

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

机器具有优势关系下的工件加工时间可控的流水作业排序问题

本文主要研究机器具有优势关系下的工件加工时间可控的流水作业排序问题.我们主要对以下两种情形进行了讨论:工件加工时间为线性恶化和线性学习.对于每一种加工模型,我们分别研究了几类不同的优势机器,并且对每种情况均给出了多项式时间算法.     

一种可控的两台机流水作业排序问题

在经典的两台机流水作业排序问题F_2‖C_(max)的基础上进行修改,将工件J_j在两台机上的加工时间由常数A_j和B_j改成A_j(x)=a_j+c_jx和B_j(x)=b_j-d_jx,其中x是某区间上的可控(决策)变量.排序的目标是,选择适当的x(对应相应的加工时间是A_j(x)、B_j(x))(j=1,2,…,n)及相应的工件的加工顺序σ=[σ(1),σ(2),…,σ(n)],使时间表长(即最后一个工件J_σ(n)在第二台机上的完工时间)G_(max达到最小.给出了解决问题的有效方法.     

二机器流水作业排序问题全部最优解的结构

排序问题F2||Cmax,Johnson条件只是最优解的充分条件,不是必要的．本文绘出一个充分必要条件,由此得到生成全部最优解的算法．主要理论是基于一种序论方法．     

多台机器流水作业中存在调整时间的Lot—streaming问题

多台机器流水作业的Lot-streaming问题（简称LS）,以往的研究都不考虑调整时间,固定分批数,寻找最优分批大小;本文对机器引入调整时间,研究同时决定最优分批数及分批大小,并给出了相应最优算法。     

带广义偏序约束的Flow—shop排序问题

本文研究了一种新的排序问题：带“广义偏序”约束的ｆｏｌｗ－ｓｈｐｏ排序问题。如工件Ｊｊ与工件Ｊｋ之间有广义偏序，则Ｊｊ→Ｊｋ，且Ｊｊ的完工时间与Ｊｋ的开工时间的间隔洋小于ｌｊｋ和不大于ｕｊｋ，０≤ｌｊｋ≤ｕｊｋ。问题的目标函数是最大完工时间。     

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

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

Alternative Formulations of a Flow-shop Scheduling Problem

This paper presents an alternative approach to an earlier model developed by other authors to formulate a problem of sequencing N jobs on M machines in a standard flow-shop. The objectives of the model are to minimize makespan and flow-time. The new formulation involves substantially fewer variables, at the expense of a rise in the number of constraints. Practical limitations of both approaches are discussed.     

A New Heuristic for a Single Machine Scheduling Problem with Set-up Times

This paper examines the problem of scheduling jobs on a single machine with set-up times. The jobs are divided into mutually exclusive classes and a set-up task is required when processing switches from a job of one class to a job of another class. The set-up times are assumed to be sequence independent. A number of necessary conditions for a schedule to minimize mean flow time have previously been stated, but do not uniquely define the optimal solution, and the problem is apparently NP-complete. We propose a new polynomial-time heuristic, based on these conditions, and compare its performance with some existing heuristics.     

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

讨论两个单机排序的资源分配问题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秒的时间内获得实际问题的一个近似最优解.     

模糊加工时间排序问题的性质

本文根据实际背景提出加工时间为三角形模糊数的排序问题,分析这个问题的性质,并就进一步研究提出几个思考。     

具有优先权和准备时间的自由作业时间表问题

研究具有优先权和准备时间的自由作业时间表问题 ,在稠密时间表的情况下 ,给出一种启发式算法 ,猜想该算法的紧界是 2 -2 /( m +1 ) ,其中 m是机器台数 .对于只有两台机器的情况 ,即当 m =2 时 ,证明该算法的最坏性能比是 4/3 ,并通过实例证明上界是紧的 .