Parallel machine scheduling with fuzzy processing times using a robust genetic algorithm and simulation

This paper addresses parallel machine scheduling problems with fuzzy processing times. A robust genetic algorithm (GA) approach embedded in a simulation model is proposed to minimize the maximum completion time (makespan). The results are compared with those obtained by using the “longest processing time” rule (LPT), which is known as the most appropriate dispatching rule for such problems. This application illustrates the need for efficient and effective heuristics to solve such fuzzy parallel machine scheduling problems (FPMSPs). The proposed GA approach yields good results quickly and several times in one run. Moreover, because it is a search algorithm, it can explore alternative schedules providing the same results. Thanks to the simulation model, several robustness tests are conducted using different random number sets, and the robustness of the proposed approach is demonstrated.     

A linguistic approach to non-identical parallel processor scheduling with fuzzy processing times

This study presents an application of non-identical parallel processor scheduling under uncertain operation times. We have been motivated from a real case scheduling problem that contains some uncommon welding operations to be processed by workers in an automotive subcontract company. Here each operator may weld each job but in different processing times depending on learning effect because of operator’s ability and experience, and batch sizes. To determine the crisp operation times in such a fuzzy environment, a linguistic reasoning approach (with a 75-“If- Then” rules) considering the learning effect is proposed in the study. Since the fuzzy linguistic approach allows the representation of expert information more directly and adequately, it can be more possible to make realistic schedules under uncertainty. With the objective to balance the workload among all operators, the longest processing time heuristic algorithm is been used and measured average makespan. For evaluating the effectiveness of this approach, it is compared with the scheduling method that use the random operation times generated from a uniform distribution. Results showed that the proposed fuzzy linguistic scheduling approach has balanced the workload of operators with a standard deviation of 0.37 and improved the Cmax value as 16%. A general conclusion can be drawn the proposed approach is able to generate realistic schedules and especially useful to solve non-identical parallel processor scheduling problem under uncertainty. An important contribution of this study is that Mamdani inference method with learning effect is the first time used to obtain the crisp processing times of non-identical processors by the help of a rule base with expert knowledge.     

解并行机模糊调度问题的自适应遗传算法

针对家纺企业车间调度的实际情况,建立了一种产品优先级约束的模糊车间调度模型。在模型中,完工时间和交货期都是模糊的,交货期平均满意度最大为调度目标。基于此模型,提出了一种自适应的遗传算法,该算法通过比例选择及局部搜索保证种群的优良特性,并通过自动调节变异率和交叉率的方式保证种群的多样性,有效跳出局部收敛。仿真结果表明,自适应遗传算法能有效求解,并优于免疫遗传算法。     

基于自适应遗传算法的Job Shop调度问题研究

求解Job Shop调度问题是个NP完全问题,为了提高遗传算法的性能,提出一种新的自适应遗传算法(NSGA)以解决Job Shop调度问题.采用活动调度解码方法、过滤个体适应度相同的筛选策略、改进自适应交叉变异概率等改进策略来提高算法性能,最后通过仿真比较分析证明该算法的先进性.     

Two branch-and-bound algorithms for the robust parallel machine scheduling problem

Uncertainty is an inevitable element in many practical production planning and scheduling environments. When a due date is predetermined for performing a set of jobs for a customer, production managers are often concerned with establishing a schedule with the highest possible confidence of meeting the due date. In this paper, we study the problem of scheduling a given number of jobs on a specified number of identical parallel machines when the processing time of each job is stochastic. Our goal is to find a robust schedule that maximizes the customer service level, which is the probability of the makespan not exceeding the due date. We develop two branch-and-bound algorithms for finding an optimal solution; the two algorithms differ mainly in their branching scheme. We generate a set of benchmark instances and compare the performance of the algorithms based on this dataset.     

Ant colony optimization algorithm for scheduling jobs with fuzzy processing time on parallel batch machines with different capacities

We study the problem of scheduling on parallel batch processing machines with different capacities under a fuzzy environment to minimize the makespan. The jobs have non-identical sizes and fuzzy processing times. After constructing a mathematical model of the problem, we propose a fuzzy ant colony optimization (FACO) algorithm. Based on the machine capacity constraint, two candidate job lists are adopted to select the jobs for building the batches. Moreover, based on the unoccupied space of the solution, heuristic information is designed for each candidate list to guide the ants. In addition, a fuzzy local optimization algorithm is incorporated to improve the solution quality. Finally, the proposed algorithm is compared with several state-of-the-art algorithms through extensive simulated experiments and statistical tests. The comparative results indicate that the proposed algorithm can find better solutions within reasonable time than all the other compared algorithms.     

模糊环境下的差异作业单机批调度优化问题的研究*

针对现实生产制造系统中存在的时间参数模糊化问题,本文用梯形模糊数表征时间参数,给出了一种具有模糊加工时间和模糊批次间隔的、以最小化制造跨度为目标的模糊差异作业单机批调度问题模型。在对模糊差异作业单机批调度问题进行有效求解方面,针对基本粒子群算法容易陷入局部最优的问题,本文给出了一种基于遗传操作的混合粒子群算法,利用遗传算法思想对粒子进行交叉、变异操作,增强了算法跳出局部最优的能力。仿真实验验证了该算法具有可行性和有效性。     

Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints

This paper presents a novel, two-level mixed-integer programming model of scheduling N jobs on M parallel machines that minimizes bi-objectives, namely the number of tardy jobs and the total completion time of all the jobs. The proposed model considers unrelated parallel machines. The jobs have non-identical due dates and ready times, and there are some precedence relations between them. Furthermore, sequence-dependent setup times, which are included in the proposed model, may be different for each machine depending on their characteristics. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches or optimization tools is extremely difficult. This paper proposes an efficient genetic algorithm (GA) to solve the bi-objective parallel machine scheduling problem. The performance of the presented model and the proposed GA is verified by a number of numerical experiments. The related results show the effectiveness of the proposed model and GA for small and large-sized problems.     

A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times

This paper presents a hybrid approach based on the integration between a genetic algorithm (GA) and concepts from constraint programming, multi-objective evolutionary algorithms and ant colony optimization for solving a scheduling problem. The main contributions are the integration of these concepts in a GA crossover operator. The proposed methodology is applied to a single machine scheduling problem with sequence-dependent setup times for the objective of minimizing the total tardiness. A sensitivity analysis of the hybrid approach is carried out to compare the performance of the GA and the hybrid genetic algorithm (HGA) approaches on different benchmarks from the literature. The numerical experiments demonstrate the HGA efficiency and effectiveness which generates solutions that approach those of the known reference sets and improves several lower bounds.     

Adaptive crossover,mutation and selection using fuzzy system for genetic algorithms

Genetic algorithms use a tournament selection or a roulette selection to choice better population. But these selections couldn’t use heuristic information for specific problem. Fuzzy selection system by heuristic rule base help to find optimal solution efficiently. And adaptive crossover and mutation probabilistic rate is faster than using fixed value. In this paper, we want fuzzy selection system for genetic algorithms and adaptive crossover and mutation rate fuzzy system. This work was presented in part and awarded as Young Author Award at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

解不同交货期并行机调度问题的并行遗传算法

为有效地解决不同交货期窗口下的非等同并行多机提前/拖后调度问题,设计了一种分段编码的混合遗传算法。此编码方式能反映工件的分配序列,并利用调度优先级规则和最好适应值规则相结合的启发式算法对其顺序进行了调整,加快了收敛速度。同时为了更好地适应调度实时性和解大规模此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,此算法是有效的,优于遗传算法,有着较高的并行性,并能适用于大规模不同交货期窗口下非等同并行多机提前/拖后调度问题。     

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

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

基于NSGA2算法的并行机多目标调度问题研究

针对并行机多目标调度问题,以完工时间和总延迟时间最小为目标函数建立了数学模型,从而将具有解决复杂组合优化问题的非劣排序遗传算法NSGA2应用于求解多目标并行机调度问题。文中详细描述了用NSGA2算法求解并行机调度问题的步骤,并通过Matlab仿真,表明YhqNSGA2算法求解多目标并行机调度问题的可行性和有效性。     

Soft computing for scheduling with batch setup times and earliness-tardiness penalties on parallel machines

A model for scheduling grouped jobs on identical parallel machines is addressed in this paper. The model assumes that a set-up time is incurred when a machine changes from processing one type of component to a different type of component, and the objective is to minimize the total earliness-tardiness penalties. In this paper, the algorithm of soft computing, which is a fuzzy logic embedded Genetic Algorithm is developed to solve the problem. The efficiency of this approach is tested on several groups of random problems and shows that the soft computing algorithm has potential for practical applications in larger scale production systems.     

解优先级约束并行机调度问题的人工免疫算法

针对家纺企业车间调度的实际情况,建立了优先级特殊工艺约束下并行多机拖后调度模型,并提出一种新颖的人工免疫算法对其求解。该算法是依据生物的免疫机理,将目标函数作为抗原,将问题的解作为抗体,对抗体采用向量组编码的方式进行编码,通过克隆、变异及一种新颖的基于浓度的种群多样性更新选择方法,提高了种群多样性,并通过局部搜索改善了种群质量,加快了收敛速度。仿真结果表明,与遗传算法相比较,该算法能更快更准确地收敛到全局最优解。     

A new hybrid genetic algorithm for job shop scheduling problem

Job shop scheduling problem is a typical NP-hard problem. To solve the job shop scheduling problem more effectively, some genetic operators were designed in this paper. In order to increase the diversity of the population, a mixed selection operator based on the fitness value and the concentration value was given. To make full use of the characteristics of the problem itself, new crossover operator based on the machine and mutation operator based on the critical path were specifically designed. To find the critical path, a new algorithm to find the critical path from schedule was presented. Furthermore, a local search operator was designed, which can improve the local search ability of GA greatly. Based on all these, a hybrid genetic algorithm was proposed and its convergence was proved. The computer simulations were made on a set of benchmark problems and the results demonstrated the effectiveness of the proposed algorithm.     

求解异构并行机调度问题的混合多目标教-学优化算法

以异构并行机调度问题为研究对象,考虑了一类以优化总加权完工时间和加权延误总和的调度问题。首先,基于问题描述构建了该问题的混合整数规划模型。其次,提出了混合多目标教-学优化算法。在算法设计中,结合问题的特点设计序列编码方法,并采用分解技术来实现多目标调度问题的求解。此外,该算法通过融合多种交叉算子来定义个体进化过程,并通过与变邻域搜索算法的混合来提升其优化效果。最后,给出了仿真实验与分析,测试结果验证了多目标教-学优化算法求解该调度问题的优越性。     

A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families

We consider the problem of minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals. We propose a family of iterative improvement heuristics based on previous work by Potts [Analysis of a heuristic for one machine sequencing with release dates and delivery times. Operations Research 1980;28:1436–41] and Uzsoy [Scheduling batch processing machines with incompatible job families. International Journal for Production Research 1995;33(10):2685–708] and combine them with a genetic algorithm (GA) based on the random keys encoding of Bean [Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing 1994;6(2):154–60]. Extensive computational experiments show that one of the proposed GAs runs significantly faster than the other, providing a good tradeoff between solution time and quality. The combination of iterative heuristics with GAs consistently outperforms the iterative heuristics on their own.     

改进遗传算法的并行任务调度

并行任务调度是一个NP完全问题,它关注资源的分配和并行任务调度,要求具有高性能的调度算法,且能求解出高质量的解。提出了一种基于改进遗传算法的并行任务调度算法,在算法初始化种群产生时引入任务向量矩阵来表示任务、资源以及调度的关系,并采用启发式方法得到初始化种群,提高种群质量;采用规则约束的交叉和变异操作,提高个体的质量;提出了加速进化策略,有效地避免了早熟。仿真实验结果表明,该改进算法能更有效地求解并行任务调度问题。     

A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes

This paper investigates the scheduling problem of parallel identical batch processing machines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and processing time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Based on developing heuristic approaches, we proposed a hybrid genetic heuristic (HGH) to minimize makespan objective. To verify the performance of our algorithm, comparisons are made through using a simulated annealing (SA) approach addressed in the literature as a comparator algorithm. Computational experiments reveal that affording the knowledge of problem through using heuristic procedures, gives HGH the ability of finding optimal or near optimal solutions in a reasonable time.