A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling

Finding feasible scheduling that optimize all objective functions for flexible job shop scheduling problem (FJSP) is considered by many researchers. In this paper, the novel hybrid genetic algorithm and simulated annealing (NHGASA) is introduced to solve FJSP. The NHGASA is a combination of genetic algorithm and simulated annealing to propose the algorithm that is more efficient than others. The three objective functions in this paper are: minimize the maximum completion time of all the operations (makespan), minimize the workload of the most loaded machine and minimize the total workload of all machines. Pareto optimal solution approach is used in NHGASA for solving FJSP. Contrary to the other methods that assign weights to all objective functions to reduce them to one objective function, in the NHGASA and during all steps, problems are solved by three objectives. Experimental results prove that the NHGASA that uses Pareto optimal solutions for solving multi-objective FJSP overcome previous methods for solving the same benchmarks in the shorter computational time and higher quality.     

An improved artificial bee colony algorithm for flexible job-shop scheduling problem with fuzzy processing time

This study addresses flexible job-shop scheduling problem (FJSP) with fuzzy processing time. An improved artificial bee colony (IABC) algorithm is proposed for FJSP cases defined in existing literature and realistic instances in remanufacturing where the uncertainty of the processing time is modeled as fuzzy processing time. The objectives are to minimize the maximum fuzzy completion time and the maximum fuzzy machine workload, respectively. The goal is to make the scheduling algorithm as part of expert and intelligent scheduling system for remanufacturing decision support. A simple and effective heuristic rule is developed to initialize population. Extensive computational experiments are carried out using five benchmark cases and eight realistic instances in remanufacturing. The proposed heuristic rule is evaluated using five benchmark cases for minimizing the maximum fuzzy completion time and the maximum fuzzy machine workload objectives, respectively. IABC algorithm is compared to six meta-heuristics for maximum fuzzy completion time criterion. For maximum fuzzy machine workload, IABC algorithm is compared to six heuristics. The results and comparisons show that IABC algorithm can solve FJSP with fuzzy processing time effectively, both benchmark cases and real-life remanufacturing instances. For practical remanufacturing problem, the schedules by IABC algorithm can satisfy the requirement in real-life shop floor. The IABC algorithm can be as part of expert and intelligent scheduling system to supply decision support for remanufacturing scheduling and management.     

Greedy randomized adaptive search for dynamic flexible job-shop scheduling

Dynamic flexible job shop scheduling problem is studied under the events such as new order arrivals, changes in due dates, machine breakdowns, order cancellations, and appearance of urgent orders. This paper presents a constructive algorithm which can solve FJSP and DFJSP with machine capacity constraints and sequence-dependent setup times, and employs greedy randomized adaptive search procedure (GRASP). Besides, Order Review Release (ORR) mechanism and order acceptance/rejection decisions are also incorporated into the proposed method in order to adjust capacity execution considering customer due date requirements. The lexicographic method is utilized to assess the objectives: schedule instability, makespan, mean tardiness and mean flow time. A group of experiments is also carried out in order to verify the suitability of the GRASP in solving the flexible job shop scheduling problem. Benchmark problems are formed for different problem scales with dynamic events. The event-driven rescheduling strategy is also compared with periodical rescheduling strategy. Results of the extensive computational experiment presents that proposed approach is very effective and can provide reasonable schedules under event-driven and periodic scheduling scenarios.     

Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives

Flexible job-shop scheduling problem (FJSP) is a practically useful extension of the classical job shop scheduling problem. This paper proposes an effective discrete harmony search (DHS) algorithm to solve FJSP. The objectives are the weighted combination of two minimization criteria namely, the maximum of the completion time (Makespan) and the mean of earliness and tardiness. Firstly, we develop a new method for the initial machine assignment task. Some existing heuristics are also employed for initializing the harmony memory with discrete machine permutation for machine assignment and job permutation for operation sequencing. Secondly, we develop a new rule for the improvisation to produce a new harmony for FJSP incorporating machine assignment and operation sequencing. Thirdly, several local search methods are embedded to enhance the algorithm’s local exploitation ability. Finally, extensive computational experiments are carried out using well-known benchmark instances. Computational results and comparisons show the efficiency and effectiveness of the proposed DHS algorithm for solving the FJSP with weighted combination of two objectives.     

An integrated search heuristic for large-scale flexible job shop scheduling problems

The flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop scheduling problem (JSP), where each operation is allowed to be processed by any machine from a given set, rather than one specified machine. In this paper, two algorithm modules, namely hybrid harmony search (HHS) and large neighborhood search (LNS), are developed for the FJSP with makespan criterion. The HHS is an evolutionary-based algorithm with the memetic paradigm, while the LNS is typical of constraint-based approaches. To form a stronger search mechanism, an integrated search heuristic, denoted as HHS/LNS, is proposed for the FJSP based on the two algorithms, which starts with the HHS, and then the solution is further improved by the LNS. Computational simulations and comparisons demonstrate that the proposed HHS/LNS shows competitive performance with state-of-the-art algorithms on large-scale FJSP problems, and some new upper bounds among the unsolved benchmark instances have even been found.     

A Pareto-based two-stage evolutionary algorithm for flexible job shop scheduling problem with worker cooperation flexibility

The previous studies on the flexible job shop scheduling problems (FJSP) with machine flexibility and worker flexibility normally assume that each machine is operated by one worker at any time. However, it is not accurate in many cases because many workers may be required for machines in processing complex operations. Hence, this paper studies a universal version, i.e., FJSP with worker cooperation flexibility (FJSPWC), which defines that each machine can be used only if their required workers are prepared. A mixed-integer linear programming model tuned by CPLEX is established for the problem aiming to collaboratively minimize the makespan, maximum workload of machines and maximum workload of workers. To solve the problem efficiently, a Pareto-based two-stage evolutionary algorithm (PTEA) is proposed. In the PTEA, a well-tailored initialization operator and the NSGA-II structure are designed for global exploration in the first stage, and a competitive objective-based local search operator is developed to improve its local search ability and accelerate the convergence in the second stage. Extensive experiments based on fifty-eight newly formulated benchmarks are carried out to validate the effectiveness of the well-designed initialization operator and two-stage architecture. Comprehensive experiments are performed to evaluate the proposed PTEA, and the results reveal that the PTEA is superior to four comparison algorithms concerning the distribution, convergence, and overall performance.     

On the identical parallel-machine rescheduling with job rework disruption

This paper investigates an issue of rescheduling on identical parallel machines where the original jobs have already been scheduled to minimize the total completion time, when a single set of jobs to be reworked re-arrives and creates a job rework disruption. Two conflicting rescheduling criteria are considered: the total completion time, as the measure of scheduling cost (efficiency); and the number of jobs assigned to different machines in the original schedule and newly generated schedule, as the measure of disruption cost (stability). Further, the rescheduling problem is defined as a bi-criteria scheduling problem. Two polynomial time algorithms are proposed to lexicographically optimize the two criteria. Besides, the set of all efficient schedules with respect to the two criteria can be also generated in polynomial time.     

Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times

This research analyzes the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization of the identical parallel processing machines and is closer to real-world production systems. Each machine can accommodate and process several jobs simultaneously as a batch as long as the machine capacity is not exceeded. The batch processing time and the batch ready time are respectively equal to the largest processing time and the largest ready time among all the jobs in the batch. Motivated by the computational complexity and the practical relevance of the problem, we present several heuristics based on first-fit and best-fit earliest job ready time rules. We also present a mixed integer programming model for the problem and a lower bound to evaluate the quality of the heuristics. The small computational effort of deterministic heuristics, which is valuable in some practical applications, is also one of the reasons that motivates this study. The results show that the heuristic proposed in this paper has a superior performance compared to the heuristics based on ideas proposed in the literature.     

Multi-objective scheduling of dynamic job shop using variable neighborhood search

Dynamic job shop scheduling that considers random job arrivals and machine breakdowns is studied in this paper. Considering an event driven policy rescheduling, is triggered in response to dynamic events by variable neighborhood search (VNS). A trained artificial neural network (ANN) updates parameters of VNS at any rescheduling point. Also, a multi-objective performance measure is applied as objective function that consists of makespan and tardiness. The proposed method is compared with some common dispatching rules that have widely used in the literature for dynamic job shop scheduling problem. Results illustrate the high effectiveness and efficiency of the proposed method in a variety of shop floor conditions.     

多阶段人机协同求解动态柔性作业车间调度问题

针对柔性作业车间生产环境中机器故障的动态调度问题, 以最小最大完工时间和最小偏差为目标, 结合车间调度人员的经验建立多阶段人机协同动态调度策略. 在不同阶段该策略的调度人员可参与优化过程, 提高方案的可行性和稳定性. 设计外部精英库中最优解的更新方法, 依据海明距离保留具有相同目标值的多种调度方案. 最后通过实例仿真验证了该模型和算法的有效性、可行性和稳定性, 更便于有效地指导生产实践.

     

基于新型帝国竞争算法的高维多目标柔性作业车间调度

针对高维多目标柔性作业车间调度问题(MaOFJSP),提出了一种新型帝国竞争算法(ICA)以同时最小化最大完成时间、最大拖期、最大机器负荷和总能耗,该算法采用新方法构建初始帝国使得大多数殖民国家分配数量相近的殖民地,引入殖民国家的同化,并应用新的革命策略和帝国竞争方法以获得高质量解.最后通过大量实验测试ICA新策略对其性能的影响并将ICA与其他算法对比,实验结果表明新型ICA在求解MaOFJSP方面具有较强的优势.     

基于新型蛙跳算法的低碳柔性作业车间调度

针对低碳柔性作业车间调度问题(flexible job shop scheduling problem,FJSP),提出一种新型蛙跳算法(shuffled frog leaping algorithm,SFLA)以总碳排放最小化,该算法运用记忆保留搜索所得一定数量的最优解,并采取基于种群和记忆的种群划分方法,应用新的搜索策略如全局搜索与局部搜索的协调优化以实现模因组内的搜索,取消种群重组使算法得到简化.采用混合遗传算法和教–学优化算法作为对比算法,大量仿真对比实验验证了SFLA对于求解低碳FJSP具有较强的搜索能力和竞争力.     

Multihybrid job scheduling for fault-tolerant distributed computing in policy-constrained resource networks

Unpredictable fluctuations in resource availability often lead to rescheduling decisions that sacrifice a success rate of job completion in batch job scheduling. To overcome this limitation, we consider the problem of assigning a set of sequential batch jobs with demands to a set of resources with constraints such as heterogeneous rescheduling policies and capabilities. The ultimate goal is to find an optimal allocation such that performance benefits in terms of makespan and utilization are maximized according to the principle of Pareto optimality, while maintaining the job failure rate close to an acceptably low bound. To this end, we formulate a multihybrid policy decision problem (MPDP) on the primary-backup fault tolerance model and theoretically show its NP-completeness. The main contribution is to prove that our multihybrid job scheduling (MJS) scheme confidently guarantees the fault-tolerant performance by adaptively combining jobs and resources with different rescheduling policies in MPDP. Furthermore, we demonstrate that the proposed MJS scheme outperforms the five rescheduling heuristics in solution quality, searching adaptability and time efficiency by conducting a set of extensive simulations under various scheduling conditions.     

Flexible job shop scheduling using hybrid differential evolution algorithms

This paper proposes hybrid differential evolution (HDE) algorithms for solving the flexible job shop scheduling problem (FJSP) with the criterion to minimize the makespan. Firstly, a novel conversion mechanism is developed to make the differential evolution (DE) algorithm that works on the continuous domain adaptive to explore the problem space of the discrete FJSP. Secondly, a local search algorithm based on the critical path is embedded in the DE framework to balance the exploration and exploitation by enhancing the local searching ability. In addition, in the local search phase, the speed-up method to find an acceptable schedule within the neighborhood structure is presented to improve the efficiency of whole algorithms. Extensive computational results and comparisons show that the proposed algorithms are very competitive with the state of the art, some new best known solutions for well known benchmark instances have even been found.     

Discrepancy search for the flexible job shop scheduling problem

The flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop problem in which each operation must be processed on a given machine chosen among a finite subset of candidate machines. The aim is to find an allocation for each operation and to define the sequence of operations on each machine, so that the resulting schedule has a minimal completion time. We propose a variant of the climbing discrepancy search approach for solving this problem. We also present various neighborhood structures related to assignment and sequencing problems. We report the results of extensive computational experiments carried out on well-known benchmarks for flexible job shop scheduling. The results demonstrate that the proposed approach outperforms the best-known algorithms for the FJSP on some types of benchmarks and remains comparable with them on other ones.     

Mathematical modeling and heuristic approaches to flexible job shop scheduling problems

Scheduling for the flexible job shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem in medium and actual size problem with traditional optimization approaches owing to the high computational complexity. For solving the realistic case with more than two jobs, two types of approaches have been used: hierarchical approaches and integrated approaches. In hierarchical approaches assignment of operations to machines and the sequencing of operations on the resources or machines are treated separately, i.e., assignment and sequencing are considered independently, where in integrated approaches, assignment and sequencing are not differentiated. In this paper, a mathematical model and heuristic approaches for flexible job shop scheduling problems (FJSP) are considered. Mathematical model is used to achieve optimal solution for small size problems. Since FJSP is NP-hard problem, two heuristics approaches involve of integrated and hierarchical approaches are developed to solve the real size problems. Six different hybrid searching structures depending on used searching approach and heuristics are presented in this paper. Numerical experiments are used to evaluate the performance of the developed algorithms. It is concluded that, the hierarchical algorithms have better performance than integrated algorithms and the algorithm which use tabu search and simulated annealing heuristics for assignment and sequencing problems consecutively is more suitable than the other algorithms. Also the numerical experiments validate the quality of the proposed algorithms.     

Scheduling job classes on uniform machines

We study a scheduling problem with job classes on parallel uniform machines. All the jobs of a given class share a common due-date. General, non-decreasing and class-dependent earliness and tardiness cost functions are assumed. Two objectives are considered: (i) minmax, where the scheduler is required to minimize the maximum earliness/tardiness cost among all the jobs and (ii) minmax-minsum, where the scheduler minimizes the sum of the maximum earliness/tardiness cost in all job classes. The problem is easily shown to be NP-hard, and we focus here on the introduction of simple heuristics. We introduce LPT (Largest Processing Time first)-based heuristics for the allocation of jobs to machines within each class, followed by a solution of an appropriate non-linear program, which produces for this job allocation an optimal schedule of the classes. We also propose a lower bound, based on balancing the load on the machines. Our numerical tests indicate that the heuristics result in very small optimality gaps.     

求解柔性作业车间调度的GATOC混合方法

柔性作业车间调度问题是经典作业车间调度问题的扩展,它允许工序在可选加工机器集中任意一台上加工,加工时间随加工机器不同而不同。针对柔性作业车间调度问题的特点,提出一种基于约束理论的局部搜索方法,对关键路径上的机器的负荷率进行比较,寻找瓶颈机器,以保证各机器之间的负荷平衡。为了克服传统遗传算法早熟和收敛慢的缺点,设计多种变异操作,增加种群多样性。为了更好保留每代中的优良解,设计了基于海明距离的精英解保留策略。运用提出的算法求解基准测试问题,验证了算法的可行性和有效性。     

Parallel hybrid metaheuristics for the flexible job shop problem

A parallel approach to flexible job shop scheduling problem is presented in this paper. We propose two double-level parallel metaheuristic algorithms based on the new method of the neighborhood determination. Algorithms proposed here include two major modules: the machine selection module refer to executed sequentially, and the operation scheduling module executed in parallel. On each level a metaheuristic algorithm is used, therefore we call this method meta²heuristics. We carry out a computational experiment using Graphics Processing Units (GPU). It was possible to obtain the new best known solutions for the benchmark instances from the literature.     

Improving schedule stability in single-machine rescheduling for new operation insertion

The problem studied here entails inserting a new operation into an existing predictive schedule (preschedule) on a (non-preemptive) single machine by rescheduling its operations, so that the resultant schedule is the most stable one among schedules with minimal maximum tardiness. Stability is measured by the sum of absolute deviations of post-rescheduling start times from the pre-rescheduling start times. In addition to several simple heuristics, this study investigates a hybrid branch-and-bound/local-search algorithm. A large set of instances that include cases with inserted idle times allows for tests of the performance of the heuristics for preschedules with varying degrees of robustness. The results show that algorithms can be developed that significantly improve the stability of schedules with no degradation in T_max. In addition, new insights emerge into the robustness characteristics of a preschedule. Specifically, the number of gaps in the schedule, equal distribution of total slack among these gaps, and the slack introduced beyond the amount enforced by release times all have effects on schedule robustness and stability.