并行多机成组工作总流水时间调度问题

有N个成组工件将在M台并行一致的机器上加工,当一个工件接在不同组的工件之后时需要装设,而接在同组工件之后时不需要重新装设,目标函数是使总的通过时间最短,这是一个NP难题,最优解很难找到笔者在文中提出了一个启发式算法,为了验证该算法的结果,又提出了一个求解最优解下界的线性规划模型,并用分枝定界法求解出下界解,在中小规模问题条件下,将下界解、启发式的解及最优解进行比较,证明了下界解的有效性,然后,在中等规模水平上,将启发式算法的结果与下界解进行了比较,最终证明该启发式算法具有解决大规模实际问题的潜力。     

可重入混合流水车间调度的改进遗传算法

研究了可重入多阶段混合流水车间调度问题,其中至少有一个加工阶段有多台同构并行机。考虑工件在相邻两阶段间的运输时间和工件动态到达等实际生产特征,以最小化最大完工时间为目标建立数学模型。在传统遗传算法的基础上,结合NEH启发式算法产生工件初始加工顺序,令遗传参数随进化代数和个体适应函数值2个方面进行自适应调节,以避免算法陷入早熟,提出改进遗传算法用以求解该NP-hard问题。分别利用所提出的改进遗传算法与传统遗传算法、NEH启发式算法对不同规模的问题进行仿真测试,结果表明,改进遗传算法在较短的计算时间内能够获得较好的近优解。     

考虑运输的柔性流水车间多处理器任务调度的混合遗传优化算法

多处理器任务调度在制造业有着较广泛的应用,为了解决实际柔性流水车间环境下的多处理器任务调度优化问题,研究了考虑运输时间和释放时间的多阶段柔性流水车间多处理器任务调度问题,该问题为NP-hard问题,以最小化最大完工时间为目标建立了柔性流水车间多处理器任务调度整数规划模型。为有效求解该问题,首先研究了工件加工机器流生成机制、单工件加工机器流矩阵编码方案和批量工件加工机器流编码方案。进而设计了基于机器空闲随机筛选的工件安排机制,产生该规划的初始解生成方法,以最小化最大完工时间原则进行新解筛选。然后构建基于工件顺序与加工机器流同步交叉的新解更新过程、基于工件顺序与加工机器流同步变异的新解调整过程,并利用迭代贪婪算法完成调整和重建操作,产生全新方案以改善求解质量,最终形成结合迭代贪婪算法的混合遗传融合优化策略。仿真实验利用解的下界得出偏差百分比,分别用遗传算法、迭代贪婪算法和混合遗传融合优化算法对不同规模的问题进行测试,结果表明,混合遗传融合优化算法能够获得较好的近优解。     

含串行批处理机的三阶段混合流水车间调度问题

基于钢铁行业炼钢-连铸-热轧一体化生产作业,提炼出新的三阶段混合流水车间调度问题。其中第二阶段有多台串行批处理机而其他阶段为离散机,批加工时间等于同一批内所有工件在第二阶段的加工时间之和,且考虑了设备需要调整时间等实际生产特征。以最小化总加权完成时间为目标函数,对该问题建立数学模型,提出基于工件分解策略的拉格朗日松弛算法,引入拉格朗日乘子将机器能力约束和批加工约束松弛到目标函数中,进而将形成的松弛问题分解为较易求解的多个工件级子问题,利用动态规划算法求解子问题,设计启发式算法将松弛问题的解转换为原问题的可行解。仿真实验表明,所设计的算法能够在可接受的运行时间内得到较好的近优解。     

单机成组调度问题的约束满足建模与求解方法

为适应多品种小批量生产需求,企业普遍采用基于成组技术的混流生产,由此产生的成组调度需要平衡安装时间减少与满足交期之间的冲突关系。在分析安装时间是否依赖工件组排序、工件组能否分割加工等成组特征的基础上,以最小化加权流程时间与加权拖期为目标,构建了单机成组调度问题的约束满足模型,提出了以变量排序启发式搜索和前向约束传播相结合的求解方法。典型生产数据的实证分析表明,所提出的方法建模能力强,解的适应性好。     

基于改进非支配排序遗传算法的多目标柔性作业车间调度

采用多目标进化算法解决具有工件释放时间、工件目标差异的柔性作业车间调度问题。依据实际制造系统中存在较多的最大完工时间、平均流经时间、总拖期时间、机器总负荷、瓶颈机器负荷和生产成本性能指标,建立多目标柔性作业车间调度模型。针对柔性作业车间调度问题的特点,设计一种扩展的基于工序的编码及其主动调度的解码机制,以及初始解产生机制和有效的交叉、变异操作;针对非支配排序遗传算法(Non-dominated sorting genetic algorithm II,NSGA-II)在非支配解排序和精英选择策略方面的不足,设计一种改进的非支配排序遗传算法,应用改进的算法求解柔性作业车间调度问题得到一组Pareto解集,并运用层次分析法选出最优妥协解。通过测试基准和模拟实际生产的实例,验证提出算法的可行性和有效性。     

周期式退火炉作批处理机的可重入批离散机流水车间调度

针对无缝钢管冷拔生产中的周期式退火炉作批处理机的可重入批离散机流水车间调度问题,建立以总工件完工时间与批处理机总能源消耗最小化的双目标优化调度模型,设计包括多目标粒子群算法、快速非支配等级排序、拥挤度比较以及变异进化操作的多目标粒子群算法,该算法采用非支配等级排序与拥挤度比较进行最优粒子的选择策略和算法前期与后期变异相结合使用策略。试验结果表明,与带变异进化操作的多目标粒子群算法和非支配排序粒子群算法相比,该算法在两个目标函数上都找到更优的最小值,其结果平均水平更靠近Pareto解集的前沿,有效提高了算法的优化求解能力。通过Pareto解的方式该算法可得到一组综合权衡了完工时间和退火炉能源消耗两个指标的Pareto解集,能提供多种可选的调度方案,当生产时间充足,可尽量选取退火炉能源消耗较低的方案,当企业订单繁多追求生产效率时,可尽量选取完工时间较小的方案,有效地解决了此类实际问题。     

柔性流水车间调度模型与混合引力算法

针对柔性流水车间调度问题,利用机器特定事件点来描述工件的机器选择,再以最小化最大完工为目标,考虑工艺约束和时间约束构建了柔性流水车间调度的混合整数线性规划模型,用GAMS/Cplex找到小规模问题的全局最优解。为快速求解大规模问题的近优解,提出了结合瓶颈启发式的引力搜索算法,利用瓶颈移动技术和John Son方法的解码机制,寻找最小化最大完工时间的最优调度方案。实验结果表明,所提出的模型及算法能高效地求解以最小化最大完工时间为目标的柔性流水车间调度问题。     

考虑机器周期性维护的不确定加工车间调度优化研究

为使加工车间调度问题更加符合实际,将不确定加工时间和机器的预防性维护周期考虑到车间调度问题中。首先,建立考虑服从正态分布的随机加工时间和机器的预防性维护周期的联合优化模型,该模型以最大完工时间的期望最小为目标函数;其次,对基于多层编码的遗传算法进行编码操作,每个个体表示全部工件的加工顺序;最后,通过MATLAB中进行了仿真实验。通过实例验证了该模型的合理性和算法的有效性。对实际工业生产中车间加工调度具有重要的意义。     

加工时间可变的含多功能机的柔性制造单元调度

考虑了加工时间可变且制造单元中包含多功能机的工件加工调度问题.工件包含前道和后道两道工序,且工序加工时间线性增加.多功能机具有加工工件前、后道工序的能力,建立数学模型,模型的目标是时间最小化最大完工的时间,解的形式为工件加工路径的组合,采用遗传算法和启发式算法进行求解.最后,实验结果显示了所述方法的有效性.     

Single machine group scheduling with general linear deterioration to minimize the makespan

In this paper, we consider a single machine scheduling problem with deteriorating jobs and group technology assumption. By deteriorating jobs and group technology assumption, we mean that the group setup times and job processing times are both increasing functions of their starting times, i.e., group setup times and job processing times are both described by function, which is a general linear function of time. The objective of the scheduling problem is to minimize the makespan. We show that the problem remains solvable in polynomial time when general linear deterioration and group technology are considered simultaneously.     

Two-agent group scheduling with deteriorating jobs on a single machine

This paper considers the two-agent scheduling problems with deteriorating jobs and group technology on a single machine, where the objective is to minimize the total completion time of the first agent with the restriction that the maximum cost of the second agent cannot exceed a given upper bound. Two agents compete to perform their respective jobs on a common single machine, and each agent has his own criterion to optimize. We introduce deteriorating jobs and group technology into the two-agent single-machine scheduling where the job processing times and group setup times are both functions of their starting times. There are two different linear deterioration functions. We propose the optimal properties and present the optimal polynomial time algorithms for two different scheduling problems, respectively.     

Scheduling on unrelated parallel machines with sequence- and machine-dependent setup times and due-date constraints

We consider the unrelated parallel-machine scheduling problem with sequence- and machine-dependent setup times and due-date constraints. There are N jobs, each having a due date and requiring a single operation on one of the M machines. A setup is required if there is a switch from processing one type of job to another. Due to the characteristics of machines, the processing time depends upon the job and machine on which the job is processed, and the setup time is sequence and machine dependent. In addition, certain jobs have strict due-date constraints. An effective heuristic based on a modified apparent-tardiness-cost-with-setup procedure, the simulated annealing method, and designed improvement procedures is proposed to minimize the total tardiness of this scheduling problem. Computational characteristics of the proposed heuristic are evaluated through an extensive experiment using a newly created data set. Computational results show that the proposed heuristic is able to effectively improve the initial solutions, obtained by a modified apparent-tardiness-cost-with-setup procedure, and obtains better results than a random descent heuristic.     

Single-machine group scheduling problems with deteriorating jobs

This paper investigates single-machine scheduling problems with deteriorating jobs and the group technology (GT) assumption. By deteriorating jobs and the group technology assumption, we mean that the group setup times and job processing times are both increasing functions of their starting times, i.e., the group setup times and job processing times are both described by a function which is proportional to a linear function of time. The two objectives of scheduling problems are to minimize the makespan and the total weighted completion time, respectively. We show that these problems remain solvable in polynomial time when deterioration and group technology are considered simultaneously.     

A bicriteria parallel machine scheduling with a learning effect

Conventionally, job processing times are assumed to be constant from the first job to be processed until the last job to be completed. However, recent empirical studies in several industries have verified that unit costs decline as firms produce more of a product and gain knowledge or experience. This phenomenon is known as the “learning effect.” In this paper a bicriteria m-identical parallel machine scheduling problem with a learning effect is considered. The objective function of the problem is to find a sequence that minimizes a weighted sum of total completion time and total tardiness. Total completion time and total tardiness are widely used performance measures in scheduling literature. To solve this scheduling problem, a mathematical programming model is formulated.     

Scheduling with past-sequence-dependent setup times and learning effects on a single machine

In this paper, we study the single-machine scheduling problems with learning effect and setup time considerations. The setup times are proportional to the length of the already-processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). The objective functions are to minimize the sum of the quadratic job completion times, the total waiting time, the total weighted completion time, the maximum lateness, the total absolute differences in waiting times, and the sum of earliness penalties subject to no tardy jobs, respectively. We show that the sum of the quadratic job completion times minimization problem, the total waiting time minimization problem, the total absolute differences in waiting times minimization problem, and the sum of earliness penalties minimization problem subject to no tardy jobs can be solved in polynomial time, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under some special cases.     

Analysis of dispatching rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times

Stochastic dynamic job shop scheduling problem with consideration of sequence-dependent setup times are among the most difficult classes of scheduling problems. This paper assesses the performance of nine dispatching rules in such shop from makespan, mean flow time, maximum flow time, mean tardiness, maximum tardiness, number of tardy jobs, total setups and mean setup time performance measures viewpoint. A discrete event simulation model of a stochastic dynamic job shop manufacturing system is developed for investigation purpose. Nine dispatching rules identified from literature are incorporated in the simulation model. The simulation experiments are conducted under due date tightness factor of 3, shop utilization percentage of 90 % and setup times less than processing times. Results indicate that shortest setup time (SIMSET) rule provides the best performance for mean flow time and number of tardy jobs measures. The job with similar setup and modified earliest due date (JMEDD) rule provides the best performance for makespan, maximum flow time, mean tardiness, maximum tardiness, total setups and mean setup time measures.     

Single-machine scheduling with past-sequence-dependent setup times and effects of deterioration and learning

The paper deals with some single-machine scheduling problems with setup time considerations where the processing time of a job is given as a function of its starting times and position in a sequence. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). We consider the following objective functions: the makespan, the total completion time, the sum of the δth ( $ \delta \geqslant 0 $ ) power of job completion times, the total weighted completion time, the maximum lateness and the number of tardy jobs. We show that the makespan minimization problem, the total completion time minimization problem, and the sum of the δth power of job completion times minimization problem can be solved in polynomial time, respectively. We also show that the total weighted completion time minimization problem, the maximum lateness minimization problem and the number of tardy jobs minimization problem can be solved in polynomial time under certain conditions.     

A Pareto evolutionary algorithm approach to bi-objective unrelated parallel machine scheduling problems

This paper addresses the unrelated parallel machine scheduling problem with job sequence- and machine-dependent setup times. The preemption of jobs is not permitted, and the optimization criteria are to simultaneously minimize total weighted flow time and total weighted tardiness. The problem has applications in industries such as TFT-LCD, automobile, and textile manufactures. In this study, a Pareto evolutionary approach is proposed to solve the bi-objective scheduling problem. The performance of this approach using different encoding and decoding schemes is evaluated and is compared with that of two multi-objective simulated annealing algorithms via a set of instances generated by a method in the literature. The experimental results indicate that the Pareto evolutionary approach using random key representation and weighted bipartite matching optimization method outperforms the other algorithms in terms of closeness metric, based on similar computation times. Additionally, although the proposed method does not provide the best distribution in terms of diversity metric, it found most of the reference solutions.     

Scheduling with deteriorating jobs and past-sequence-dependent setup times

In this paper, we presented a scheduling model in which the deteriorating jobs and the setup times are considered at the same time. Under the proposed model, the actual job processing time is a general function of the processing times of jobs already processed and its scheduled position, while the setup time is past-sequence-dependent. We provided the optimal schedules for some single-machine scheduling problems.