Parallel machine scheduling with earliness-tardiness penalties and space limits

In order to maximize an availability of machine and utilization of space, the parallel machines scheduling problem with space limit is frequently discussed in the industrial field. In this paper, we consider the parallel machine scheduling problem in which n jobs having different release times, due dates, and space limits are to be scheduled on m parallel machines. The objective function is to minimize the weighted sum of earliness and tardiness. To solve this problem, a heuristic is developed which is divided into three modules hierarchically: job selection, machine selection and job sequencing, and solution improvement. To illustrate its effectiveness, a proposed heuristic is compared with genetic algorithm (GA), hybrid genetic algorithm (HGA), and tabu search (TS), which are well-known meta-heuristics in a large number of randomly generated test problems based on the field situation. Also, we determine the job selection rule that is suitable to the problem situation considered in this paper and show the effectiveness of our heuristic method.     

Workflow balancing strategies in parallel machine scheduling

Workflow balancing on a shop floor helps to remove bottlenecks present in the manufacturing system. Workflow refers to the total time during which the work centres are busy. Idle time is not taken into account when calculating workflow. Earlier researchers have not specified the method for jobs to be executed in parallel in order to balance the workflow to each machine. In many manufacturing environments, multiple processing stations are used in parallel to obtain adequate capacity. In parallel machine scheduling there are m machines to which n jobs are to be assigned based on different priority strategies. The procedure is based on the idea of workload balancing and on balancing the workload among machines. In this paper, workflow and workload are assumed to have the same meaning. A machine with the lowest workflow is selected for assignment of a new job from the list of unfinished jobs. Different priority strategies are followed for the selection of jobs. Three different strategies are considered, namely random (RANDOM), shortest processing time (SPT) and longest processing time (LPT) for the selection of jobs for workflow balancing. The relative percentage of imbalance (RPI) is adopted among the parallel machines to evaluate the performance of these strategies in a standard manufacturing environment. The LPT rule shows better performance for the combination of larger job sizes and higher number of work centres or machines. A computer program was coded for validation in a standard manufacturing environment on an IBM/PC compatible system in the C++ language.     

基于工件聚类的并行机调度算法及其应用

针对纺织生产广泛存在的带工件释放时间、以最小化总拖期工件数和总拖期时间为目标的大规模并行机调度问题,提出一种基于工件聚类的遗传算法。该算法将求解过程分为工件聚类和工件排序两个阶段。在工件聚类阶段,基于影响并行机调度性能的重要调度特征量,采用改进的模糊C-均值聚类方法将所有待上机工件分为多个聚类;在工件排序阶段,采用基于规则编码的遗传算法,优化各聚类内工件的加工顺序。数值计算结果及实际应用效果表明,所提出的算法适用于求解带工件释放时间的大规模并行机调度问题。     

同型机在线调度问题研究进展

为了阐明在线调度的概念及其与在线算法的关系,为相关研究提供支持,对同型机在线调度问题的研究现状进行综述。描述了同型机在线调度问题的概念,以加工约束和目标函数为标准,对同型机在线调度问题进行分类。从基本模型、允许拒绝工件以及考虑机器适用约束等角度对逐个调度工件类在线调度问题进行回顾,从极小化最大完工时间、极小化加权完工时间和以及极大化加权按期完工工件数等角度对工件随时问到达类在线调度问题进行总结,指出了现有研究的不足,并探讨了同型机在线调度问题的未来研究方向。     

Unrelated parallel machine scheduling with secondary resource constraints

This paper considers unrelated parallel machine scheduling with secondary resource constraints. There are n jobs, each needing to be processed on one of the fitted machines. A setup that includes detaching one die and attaching another from the fitted die type is incurred if the type of job scheduled is different from the last job on that machine. For each kind of die type, the number of dies available is limited. Due to the mechanical structure of the machines, the processing time of a job depends on the machine on which the job is processed, and some jobs are restricted to be processed only on certain machines. In this paper, a heuristic with a capability relative to a runtime and solution quality is developed to minimise the makespan. The performance of the presented heuristic is evaluated through extensive computational experiments. Computational results show that the presented heuristic outperforms the search method tested. It is expected that this research can be applied in industry where unrelated parallel machines are used to process different components and setups for auxiliary equipments are required.     

基于粒子群算法的并行多机调度问题研究

将港口拖轮作业调度问题描述为一类带特殊工艺约束的并行多机调度问题,采用粒子群算法求解该类调度问题,提出了一种2维粒子表示方法,通过对粒子位置向量进行排序生成有效调度,并采用粒子位置向量多次交换的局部搜索方法来提高算法的搜索效率。最后,通过计算验证了混合粒子群算法的有效性。     

一类并行机调度问题的动态调度算法

针对不确定制造环境中配件数量约束条件发生变化后的并行机动态调度问题,提出了一种基于操作属性模式的并行机动态调度算法.该算法针对总拖期时间性能指标的优化,根据配件负载的裕量和相邻操作的属性模式,对原调度方案的操作次序和操作上机时间进行了调整.在不同操作和设备规模下,以及不同配件数量变化幅度下进行了数值计算.数值计算结果和实际应用结果表明,该算法是有效的,具有计算复杂度低、实时性好、对原调度算法不敏感的特点.     

带特殊工艺约束的双目标并行多机调度问题研究

港口的拖轮调度过程是一类带特殊工艺约束的并行多机调度问题.采用基于进化策略的混合算法,设计了基于工件的编码方式,对次序杂交算子进行了扩展,设计了一种扩展“倒位”变异算子,并采用相邻不同基因多次交换的局部搜索方法.算法的设计自动满足了工艺约束,保证了种群的多样性.设计了最大完工时间和生产加工成本双目标评价函数,最后通过计算对混合算法进行了验证.     

基于工序约束并行机模型的冲压线调度

根据双向冲压线的实际生产特点,提出了一种基于工序约束并行机的双向冲压线调度模型.在该模型中,工件同时在牛产线两端按设备顺序加工,且加工工件及其加工开始时间和完工时间受生产线两端工件工序数目约束和生产线设备加工能力的约束,给出了该约束的规则;设计了启发规则和遗传算法混合的求解算法.最后,以最大完工时间为优化指标进行验证,证明该模型具有较好的实用价值.     

Minimization of maximum tardiness on unrelated parallel machines with process restrictions and setups

We consider the problem of scheduling N jobs on M unrelated parallel machines to minimize maximum tardiness. Each job has a due date and requires a single stage of processing. A setup for dies is incurred if the type of the job scheduled is different from the previous one on that machine. For each die type, the number of dies is restricted. Because of the mechanical structure of the machines and the fitness of dies to each machine, the processing time depends on both the job and the machine. In this paper, an efficient heuristic based on guided search, record-to-record travel, and tabu lists is presented to minimize maximum tardiness. Computational characteristics of the proposed heuristic are evaluated through extensive experiments, which show that the proposed heuristic outperforms a simulated annealing method tested and is able to prescribe the optimal solutions for problems in small scales.     

Minimization of maximum tardiness on unrelated parallel machines with process restrictions and setups

We consider the problem of schedulingN jobs onM unrelated parallel machines to minimize maximum tardiness. Each job has a due date and requires a single stage of processing. A setup for dies is incurred if the type of the job scheduled is different from the previous one on that machine. For each die type, the number of dies is restricted. Because of the mechanical structure of the machines and the fitness of dies to each machine, the processing time depends on both the job and the machine. In this paper, an efficient heuristic based on guided search, record-to-record travel, and tabu lists is presented to minimize maximum tardiness. Computational characteristics of the proposed heuristic are evaluated through extensive experiments, which show that the proposed heuristic outperforms a simulated annealing method tested and is able to prescribe the optimal solutions for problems in small scales.     

A note on single-machine scheduling with learning effect and an availability constraint

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.” However, most of the papers assume that the machine is available at all times. In reality, the machine might become unavailable due to machine breakdowns or preventive maintenance during the scheduling period. Motivated by this, single-machine scheduling problems with considerations of the learning effect and machine availability are considered in this paper. It is shown that the shortest processing time rule provides the optimal schedules for the makespan and the total completion time minimization problems when jobs are assumed to be resumable. Moreover, mixed integer programming techniques are used to solve the problems when jobs are non-resumable.     

Scheduling on identical parallel machines to minimize total completion time with deadline and machine eligibility constraints

This study addresses the identical parallel machine scheduling problem with job deadlines and machine eligibility constraints to minimize total job completion time. Jobs must be completed before or at a deadline and preemptions are not allowed. Every job is allowed to be processed on a specified subset of machines. This problem is NP-hard. A heuristic and a branch and bound algorithm are developed to solve the problem. For the branch and bound algorithm, a lower bound based on the dual solution of the assignment problem is proposed and the heuristic serves as the initial upper bound. Many dominance rules are developed to curtail the branching nodes during the search procedure. Computational results indicate that the lower bound improves the performance of those in the literature in terms of execution time, and heuristic consistently generates a good quality schedule.     

求解相同并行机混合流水线车间调度问题的分布估计算法

针对相同并行机混合流水车间调度问题,提出了一种有效的分布估计算法.针对基于排列的编码方式,设计了改进的启发式解码规则,进而提出了一种评价个体优劣的混合解码方式.建立了描述问题解空间分布的概率模型,通过对概率模型采样产生新个体,并基于优势种群更新概率模型的参数.通过基于标准测试集的数值仿真以及与已有算法的比较,验证了所提算法的有效性.     

双目标函数下需要安装时间的平行多功能机排序问题

讨论了双目标函数下需要安装时间的平行多功能机排序问题。在该问题中,每个工件对应机器集合的一个子集,且每个工件只能在相应子集中的任一台机器上加工,工件分组,不同组中的工件连续加工需要安装时间,目标函数为极小化最大完工时间和安装次数。根据实际应用背景确定双目标排序问题的形式,并证明了该问题是NP—难的。设计了一个求启发式有效解的算法,首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后逐步改进最大完工时间和拆分工件组,从而得到一系列的启发式有效解。实验表明,该算法是实用而有效的。     

基于免疫算法的并行机间歇过程模糊生产调度

研究了一类具有顺序无关模糊产品切换时间和成本以及模糊单位加工时间和成本的并行机间歇过程调度问题,目的是确定每种产品在每个设备上处理的批次数目、批量以及批次顺序,优化目标为最小化总完成时间和最小化总生产成本。根据任意设备上同种产品的所有批次均顺序处理的性质,建立了问题的模糊运输模型。利用加权和方法将多目标函数转化为单目标函数,并使用基于积分值的方法对模糊数进行排序。提出了基于排列边集编码的免疫算法,通过求解不同规模的问题实例证明,免疫算法不仅能获得比遗传算法和免疫遗传算法更好的解,而且比免疫遗传算法更高效,同时具有良好的动态性能。     

模具电火花加工车间的非同等并联机混合遗传算法

针对模具企业电火花加工车间的生产调度特点,提出了一种非同等并联机的调度数学模型.与此同时,建立了一种遗传与模拟退火的混合算法,并应用于模具企业电火花加工车间,实际算例说明了该数学模型和求解方法的可靠性和有效性.     

具有随机加工时间和机器故障的流水车间调度

不同的流水车间往往具有不同的生产方式,为提高调度方案对不同生产方式下随机因素的处理能力,重点考虑了2种生产方式下3种不同情况的随机调度。针对这3种情况,以最小化最大完工时间为目标,研究了具有随机加工时间和随机机器故障的置换流水车间调度问题,提出了处理不同生产方式下随机因素的3种计算方法,通过预测机器的期望故障时刻来计算每个任务的完工时间。采用启发式规则和遗传算法相结合的方法,确定出最佳调度方案,并进行了实验分析和比较。     

具有工件约束的模具制造优化调度算法研究

为解决具有工件约束的模具制造优化调度问题,提出了一种利用蚁群算法和优先分配启发式调度算法相结合的调度算法。该算法能够方便地描述问题的约束条件的特点。首先,由蚁群算法确定模具零件各工序所用的加工机床,用节点模式下的有向图描述问题的解空间,用蚂蚁种子信息素踪迹更新策略对信息素进行更新,以获得问题的解;然后,利用优先分配启发式调度算法确定在同一台机床上加工的各零件的先后顺序。实验结果验证了算法的有效性。     

一种求解变速机调度问题的混合蚁群优化算法

针对一类变速机总加权拖期调度问题,提出一种混合蚁群优化算法.引人单机拖期调度问题中性能良好的修正预计完成时间的一种修改版本启发式规则,计算信息素初值,有利于算法跳出局部极值,并在局部搜索阶段,采用单亲遗传算法基因移位算子,有效优化当代最优解.通过均匀试验设计和统计分析,确定算法的关键参数组合,将算法应用于随机生成的不同规模的40个算例,并将其结果与同类文献中算法的优化结果进行对比分析.结果表明,在相同迭代次数下,混合算法优于对比算法.