一种应用于柔性作业车间成组调度问题的分级优化算法

提出一种求解柔性作业车间成组调度FGJSS(flexible grouped job-shop scheduling)问题的蚁群粒子群求解算法。算法采用主从递阶形式,主级为蚁群优化算法,选择零件加工设备;从级为粒子群优化算法,在主级零件加工设备约束下优化设备作业排序以实现流通时间最小的目标。算法中,以工序加工时间和设备承载的作业族数为启发式信息设计蚂蚁在工序可用设备间转移概率;以粒子向量优先权值和作业族号为依据设计解码方法实现设备上的成组作业排序。最后,通过仿真实验,验证了该算法的有效性。     

基于改进遗传算法的单机成组作业调度

提出了单机成组作业调度的改进遗传算法。优化目标为总流程时间的单机成组作业调度问题明显是NP-hard问题,此问题的多项式求解方法不能求取最优解,而一些启发式算法也只能求出此问题的次优解。为获得单机成组作业最优调度,通过采用整数实值编码,随机采样选择,单点交叉以及变异检查,设计了单机成组作业调度的改进遗传算法。仿真结果表明,算法能够找到此问题的最优解,其性能优于加权最短加工时间(WSPT)启发式算法。改进遗传算法能够灵活解决各种单目标调度及多目标调度问题。     

并行机成组调度问题的启发式算法

研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题,提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题,以最小化总拖后时间为优化目标排列工件的加工次序;然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上;最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。     

一种求解单机成组作业优化调度的启发算法

优化目标为总流程时间的单机成组作业优化调度问题，明显是NP－hard的。该文在利用优化性质的基础上，提出了一种构造性的启发算法。该算法计算量小，可应用于大规模优化调度问题，仿真结果表明该算法能够找到次优解，其性能优于已的启发算法。     

流水车间成组工件调度问题的多目标优化算法

针对优化目标是最小化全部提前/拖期和机器调整次数的多目标流水车间成组工件调度问题,提出了一种改进的变权重进化算法结合延迟调整算法的联合优化方法。首先采用改进的变权重进化算法对加工排序进行寻优;其次,在给定调度序列的情况下采用延迟调整算法对加工时刻进行优化。仿真实验表明,所设计的算法能够有效地求解该类问题。     

车间作业调度问题的仿真研究

研究车间作业调度优化问题,使资源、车辆调试、交通分配等达到优化配置,因此车间作业调度问题是一个多约束条件的目标优化问题,采用多项式求解方法不能获得最优解,导致车间作业调度效率低.为了提高车间作业调度效率,提出了一种蚁群算法的车间作业调度优化算法.首先以最小加工时间作为优化目标,蚂蚁爬行路径为作业调度方案,通过蚁群中个体间互相协作和信息交流获得最优车间作业调度方案.通过车间作业调度测试案例对算法进行验证性实验,实验结果表明,蚁群算法提高了车间作业调度效率,能在最短时间找到最优调度方案,为车间作业调度优化提供了依据.     

改进灰狼优化算法求解机器人作业车间调度问题

针对物料机器人指派和作业车间的联合调度问题,设计了一种改进灰狼优化算法进行求解。根据机器人作业车间调度和灰狼优化算法的各自特点,提出一种面向机器人转移工序的编码方式。解码时,考虑工件运输的前提是工件在当前机器的工序已加工,提出融合间隙解码方法的驱动解码方法。为避免算法陷入局部最优,在灰狼个体位置更新后加入个体变异方法。最后,通过与其他智能优化算法及同类算法进行比较,验证了所提灰狼优化算法的有效性。     

恒速处理机的多机Flow shop最小和调度问题的启发式算法分析

本文研究有n个作业需在5个处理机中心进行加工，处理机中心i由l1个恒速机组成的非抢占式多机flow shop调度最小和问题．每个作业有s个工序，每个工序需在对应的处理机中心的任一台机器上加工处理，作业到达前不能加工，所有作业通过处理机中心的路径相同．目标是确定一个作业在每个处理机中心机器上的可行调度序列，使所有作业在最后处理机中心的加权完成时间总和最小化．在作业处理时间需求、作业权重分别为独立同分布的有界随机变量时，通过特殊flow shop调度松弛方法，我们证明该问题在作业数趋于无穷时，一个基于有效作业最短加权平均处理时间需求的启发式算法是渐近最优的．     

非同起点加工的多机调度合成算法

针对调度h个独立任务到初始时刻并非都空闲的m台机器上加工，使得机器最长加工时间（makespan）最短的问题，改进MLPT算法以减少运行时间，改进MULTIFIT算法以减少迭代次数，提出以改进的MLPT算法结果为改进的MULTIFIT算法的初始上界的合成算法－CMM，从理论上对MLPT，MULTIFIT和CMM算法的时间复杂度和调度结果进行了分析和比较，实验结果表明：改进的MULTIFIT经MULTIFIT的平均迭代次数少；CMM在平均迭代次数方面甚至比改进的MULTIFIT还少得多且调度结果不次于MULTIFIT和MLPT的优者。     

基于需求优先的多目标柔性车间调度研究

为满足按时提交客户货物的要求,需要优化企业的生产调度,现实的生产调度问题是传统车间调度问题的扩充,具有多目标、柔性等特性。针对柔性作业车间调度的需要,提出了在精益制造下的基于需求优先的多目标柔性车间调度算法。该算法以工件提前／拖期惩罚代价最小,调度最小生产周期为目标,基于规则的改进启发式调度,在调度过程中通过需求日期计算工件的优先级为每道工序分配合适的机器进行加工,可得到满意的较优解。与其他方法进行对比试验的结果表明,该算法在求解柔性作业车间调度问题是有效的。     

Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness

In many realistic production situations, a job processed later consumes more time than the same job when it is processed earlier. Production scheduling in such an environment is known as scheduling with deteriorating jobs. However, research on scheduling problems with deteriorating jobs has rarely considered explicit (separable) setup time (cost). In this paper, we consider a single-machine scheduling problem with deteriorating jobs and setup times to minimize the maximum tardiness. We provide a branch-and-bound algorithm to solve this problem. Computational experiments show that the algorithm can solve instances up to 1000 jobs in reasonable time.     

Optimal schedules for single facility with two job classes

A single facility scheduling problem with jobs divided into two mutually exclusive classes is considered when the setup time depends on the class of jobs immediately preceding the job being currently processed. The jobs in a given class need not be processed together. Based on a combinatorial analysis of the problem, an algorithm is developed to obtain an optimal schedule when the objective is to minimize mean flow time. The proposed algorithm is polynomially bounded in terms of the computational effort needed to solve the problem.     

A heuristic approach for single-machine scheduling with due dates and class setups

The single-machine sequence-independent class setup scheduling problem is examined in this paper. It is assumed that jobs are classified into classes and a setup is required between jobs of different classes, but not of the same class. Furthermore, this setup time is fixed and depends only on the current job. Since the problem is NP-hard, a heuristic algorithm is proposed to find an approximate schedule that minimizes the maximum lateness on a set of jobs. The algorithm can easily be modified to solve the maximum tardiness problems as well. The accuracy of the heuristic algorithm in generating near optimal solutions is empirically evaluated.Scope and purposeFor batch manufacturing, it maybe desirable to produce many items of the same type, or class, at the same run in order to save the setup cost. However, committing facilities to long production runs for one product may inevitably make others tardy. Small batch size may conform urgent jobs to their delivery date, but one of the consequences would be the loss of productive efficiency due to numerous setups. Therefore, scheduling is basically a trade-off between the inherently conflicting efficiency measure and due-date compliance. This paper considers a single-machine scheduling problem in which jobs are classified into classes and a setup is required between jobs of different classes. The setup time is fixed and depends only on the current job. This problem is called a sequence-independent class setup problem and is NP-complete.     

Single-machine batch scheduling to minimize the total setup cost in the presence of deadlines

We address the single-machine batch scheduling problem with the objective of minimizing the total setup cost. This problem arises when there are n jobs that are partitioned into F families and when setup operations are required whenever the machine switches from processing a job of one family to processing a job of another family. We assume that setups do not require time but are associated with a fixed cost which is identical for all setup operations. Each job has a processing time and an associated deadline. The objective is to schedule all jobs such that they are on time with respect to their deadlines and the total setup cost is minimized. We show that the decision version of this problem is NP-complete in the strong sense. Furthermore, we present properties of optimal solutions and an \(O(n\log n+nF)\) algorithm that approximates the cost of an optimal schedule by a factor of F. The algorithm is analyzed in computational tests.     

Machine scheduling with job class setup and delivery considerations

We study machine scheduling problems in which the jobs belong to different job classes and they need to be delivered to customers after processing. A setup time is required for a job if it is the first job to be processed on a machine or its processing on a machine follows a job that belongs to another class. Processed jobs are delivered in batches to their respective customers. The batch size is limited by the capacity of the delivery vehicles and each shipment incurs a transport cost and takes a fixed amount of time. The objective is to minimize the weighted sum of the last arrival time of jobs to customers and the delivery (transportation) cost. For the problem of processing jobs on a single machine and delivering them to multiple customers, we develop a dynamic programming algorithm to solve the problem optimally. For the problem of processing jobs on parallel machines and delivering them to a single customer, we propose a heuristic and analyze its performance bound.     

A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines,due dates and sequence-dependent setup times

Consider the problem of scheduling a set of jobs to be processed exactly once, on any machine of a set of unrelated parallel machines, without preemption. Each job has a due date, weight, and, for each machine, an associated processing time and sequence-dependent setup time. The objective function considered is to minimize the total weighted tardiness of the jobs.This work proposes a non-delayed relax-and-cut algorithm, based on a Lagrangean relaxation of a time indexed formulation of the problem. A Lagrangean heuristic is also developed to obtain approximate solutions.Using the proposed methods, it is possible to obtain optimal solutions within reasonable time for some instances with up to 180 jobs and six machines. For the solutions for which it is not possible to prove optimality, interesting gaps are obtained.     

Scheduling problems with deteriorating jobs and learning effects including proportional setup times

Recently, interest in scheduling with deteriorating jobs and learning effects has kept growing. However, research in this area has seldom considered setup times. We introduce a new scheduling model in which job deterioration and learning, and setup times are considered simultaneously. In the proposed model, the actual processing time of a job is defined as a function of the setup and processing times of the jobs already processed and the job’s own scheduled position in a sequence. In addition, the setup times are assumed to be proportional to the actual processing times of the already scheduled jobs. We derive polynomial-time optimal solutions for some single-machine problems with or without the presence of certain conditions.     

A Stronger Complexity Result for the Single Machine Multi-Operation Jobs Scheduling Problem to Minimize the Number of Tardy Jobs

We consider the single machine multi-operation jobs scheduling problem to minimize the number of tardy jobs. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a setup time. A job completes when all of its operations have been processed. The objective is to minimize the number of tardy jobs. In the literature, this problem has been proved to be strongly NP-hard for arbitrary due-dates. We show in this paper that the problem remains strongly NP-hard even when the due-dates are common and all jobs have the same processing time.     

A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine

This paper introduces a tabu search heuristic for a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The problem consists in scheduling a set of dependent jobs, where the transition between two jobs comprises an unrestricted setup that can be performed at any time, and a restricted setup that must be performed outside of a given time interval which repeats daily in the same position. The setup time between two jobs is thus a function of the completion time of the first job. The tabu search heuristic relies on shift and swap moves, and a surrogate objective function is used to speed-up the neighborhood evaluation. Computational experiments show that the proposed heuristic consistently finds better solutions in less computation time than a recent branch-and-cut algorithm. Furthermore, on instances where the branch-and-cut algorithm cannot find the optimal solution, the heuristic always identifies a better solution.     

A robust hybrid approach based on particle swarm optimization and genetic algorithm to minimize the total machine load on unrelated parallel machines

This paper dealt with an unrelated parallel machines scheduling problem with past-sequence-dependent setup times, release dates, deteriorating jobs and learning effects, in which the actual processing time of a job on each machine is given as a function of its starting time, release time and position on the corresponding machine. In addition, the setup time of a job on each machine is proportional to the actual processing times of the already processed jobs on the corresponding machine, i.e., the setup times are past-sequence-dependent (p-s-d). The objective is to determine jointly the jobs assigned to each machine and the order of jobs such that the total machine load is minimized. Since the problem is NP-hard, optimal solution for the instances of realistic size cannot be obtained within a reasonable amount of computational time using exact solution approaches. Hence, an efficient method based on the hybrid particle swarm optimization (PSO) and genetic algorithm (GA), denoted by HPSOGA, is proposed to solve the given problem. In view of the fact that efficiency of the meta-heuristic algorithms is significantly depends on the appropriate design of parameters, the Taguchi method is employed to calibrate and select the optimal levels of parameters. The performance of the proposed method is appraised by comparing its results with GA and PSO with and without local search through computational experiments. The computational results for small sized problems show that the mentioned algorithms are fully effective and viable to generate optimal/near optimal solutions, but when the size of the problem is increased, the HPSOGA obtains better results in comparison with other algorithms.