Search

This article studies a distributed heterogeneous hybrid flow shop scheduling problem under nonidentical time-of-use electricity tariffs (DHHFSP-NTOU). The makespan and the total electricity charge are considered as the optimization objectives from the view of production and management. The DHHFSP-NTOU considers different processing capabilitie and time-of-use electricity tariffs for each factory. The mixed-integer linear programming (MILP) model of DHHFSP-NTOU is established. To solve the DHHFSP-NTOU, this article proposes an ant colony optimization behavior-based multiobjective evolutionary algorithm based on decomposition (ACO_MOEA/D). A problem-specific ant colony behavior is presented to construct offspring individuals. Eight neighborhoods within the factory and between factories are adopted to improve the quality of the individuals in the archive set. A right-shift movement is used to reduce the electricity charge. A large number of numerical experiments and comprehensive investigations are carried out to test the efficiency and effectiveness of ACO_MOEA/D. The experimental results show that each component (e.g., ant colony behavior, neighborhoods move operators, right-shift movement) contributes to the performance of ACO_MOEA/D. The comparisons with several related algorithms show the superiority of ACO_MOEA/D for solving the DHHFSP-NTOU. Note to Practitioners—From the managers’ insights, the electricity charge is a large cost in the production. The scheduling is an economical approach to reduce the electricity charge. For the time-of-use (TOU) tariffs, the managers can adjust the schedule to reduce the idle time or move some operations to the interval period with a lower electric price. This article studies a distributed heterogeneous hybrid flow shop scheduling problem under nonidentical TOU (UTOU) electricity. This model can be used in many manufacturing enterprises that have several heterogeneous factories. This article proposes an ant colony optimization behavior-based multiobjective evolutionary algorithm based on decomposition (ACO_MOEA/D) to minimize the makespan and the total electricity charge. The ACO_MOEA/D can provide the economy and high-efficiency schedules for practitioners. The computational results confirm its effectiveness and efficiency. [ABSTRACT FROM AUTHOR]

Job shop scheduling problem (JSSP) is a typical NP-hard problem. In order to improve the solving efficiency for JSSP, a hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search is proposed in this paper, which combines the merits of Estimation of distribution algorithm and Differential evolution (DE). Meanwhile, to strengthen the searching ability of the proposed algorithm, a chaotic strategy is introduced to update the parameters of DE. Two mutation operators are adopted. A neighbourhood search (NS) algorithm based on blocks on critical path is used to further improve the solution quality. Finally, the parametric sensitivity of the proposed algorithm has been analysed based on the Taguchi method of design of experiment. The proposed algorithm was tested through a set of typical benchmark problems of JSSP. The results demonstrated the effectiveness of the proposed algorithm for solving JSSP. [ABSTRACT FROM PUBLISHER]

Influenced by the economic globalization, the distributed manufacturing has been a common production mode. This paper considers a multiobjective distributed no-wait flow-shop scheduling problem with sequence-dependent setup time (MDNWFSP-SDST). This scheduling problem exists in many real productions such as baker production, parallel computer system, and surgery scheduling. The performance criteria are the makespan and the total weight tardiness. In the MDNWFSP-SDST, several identical factories are considered with the related flow-shop scheduling problem with no-wait constraints. For solving the MDNWFSP-SDST, a Pareto-based estimation of distribution algorithm (PEDA) is presented. Three probabilistic models including the probability of jobs in empty factory, two jobs in the same factory, and the adjacent jobs are constructed. The PWQ heuristic is extended to the distributed environment to generate initial individuals. A sampling method with the referenced template is presented to generate offspring individuals. Several multiobjective neighborhood search methods are developed to optimize the quality of solutions. The comparison results show that the PEDA obviously outperforms other considered multiobjective optimization algorithms for addressing MDNWFSP-SDST. Note to Practitioners—This paper is motivated by the process cycles in multiproduction factories (or lines) of baker production, surgery scheduling, and parallel computer systems. In these process cycles, jobs are assigned to multiproduction factories (or lines), and no interruption exists between consecutive operations. This paper models this process as a multiobjective distributed no-wait flow-shop scheduling with SDST. Scheduling becomes more challenging when facing distributed factories. This paper provides an estimation of distributed algorithm with Pareto dominate concept which uses a probabilistic model to generate offspring. Experiment results suggest that the proposed algorithm can find superior solutions of large-scale instances. This scheduling model can be extended to practical problems by considering other constraints, such as assembly process, mixed no-wait, and transporting times. Besides, the proposed algorithm can be applied to solve other distributed scheduling problems and industrial cases, once their constraints are known, i.e., the processing time of operations, the setup time of machines. [ABSTRACT FROM AUTHOR]

Due to the complexity of a real-practice manufacturing process, various complex constraints should be considered to make the conventional model more suitable for the realistic production. This paper proposes a distributed assembly no-idle flow shop scheduling problem (DANIFSP) with the objective of minimizing the makespan at the assembly stage. The DANIFSP consists of two stages, i.e., production and assembly. The production stage contains several identical flow shops working in parallel, in which all jobs with series of operations that should be allocated to one of these factories and all operations of jobs should be performed in the allocated factories. To satisfy the no-idle constraint, each machine must process jobs without any interruption from the start of processing the job to the completion of processing the last job. In the second assembly stage, the processed jobs are assembled by a single machine. For addressing the DANIFSP, this paper extends three constructive heuristics based on a new job assignment rule and proposes two simple meta-heuristics including iterated local search (ILS) and variable neighborhood search (VNS). A comprehensive calibration and analysis for the proposed algorithms through a design of experiments are carried out. The comparison with recently published algorithms demonstrates the high effectiveness of the proposed ILS and VNS. [ABSTRACT FROM AUTHOR]

Abstract The blocking flow-shop scheduling problem (BFSP) has been aroused general attention due to its broad industrial applications. However, most researches about it mainly focus on optimization of single objective. Multiple objectives are less considered simultaneously. Actually, in the practical production, the consideration of multiple objectives simultaneously could give more realistic solutions to the decision maker. Therefore, in this paper, we propose a novel multi-objective discrete water wave optimization (MODWWO) algorithm to solve a multi-objective BFSP (MOBFSP) that minimizes both makespan and total flow time. In the proposed algorithm, a decomposition-based initialization strategy is developed to generate a population with high quality and diversity. Then, a ranking-based propagation operator is designed to guide the global exploration and local exploitation of algorithm. Afterwards, a local intensification-based breaking operator is applied to improve the quality of the new created waves. Furthermore, a problem-specific refraction operator is incorporated to avoid being trapped in local optimum. The proposed algorithm is evaluated based on the benchmark instances, and compared with several state-of-the-art multi-objective scheduling optimization approaches. The comparison results show that the proposed MODWWO is a high-performing method for the considered MOBFSP. Highlights • Propose a multi-objective discrete WWO for MOBFSP. • Minimize the makespan and the total flowtime simultaneously. • Each operator of WWO is newly customized according to the features of problem. • Effectiveness of the proposed algorithm is demonstrated by numerical experiments and comparisons. [ABSTRACT FROM AUTHOR]

This article presents an effective estimation of distribution algorithm, named P-EDA, to solve the blocking flow-shop scheduling problem (BFSP) with the makespan criterion. In the P-EDA, a Nawaz-Enscore-Ham (NEH)-based heuristic and the random method are combined to generate the initial population. Based on several superior individuals provided by a modified linear rank selection, a probabilistic model is constructed to describe the probabilistic distribution of the promising solution space. The path relinking technique is incorporated into EDA to avoid blindness of the search and improve the convergence property. A modified referenced local search is designed to enhance the local exploitation. Moreover, a diversity-maintaining scheme is introduced into EDA to avoid deterioration of the population. Finally, the parameters of the proposed P-EDA are calibrated using a design of experiments approach. Simulation results and comparisons with some well-performing algorithms demonstrate the effectiveness of the P-EDA for solving BFSP. [ABSTRACT FROM AUTHOR]

This article proposes an extended continuous estimation of distribution algorithm (ECEDA) to solve the permutation flow-shop scheduling problem (PFSP). In ECEDA, to make a continuous estimation of distribution algorithm (EDA) suitable for the PFSP, the largest order value rule is applied to convert continuous vectors to discrete job permutations. A probabilistic model based on a mixed Gaussian and Cauchy distribution is built to maintain the exploration ability of the EDA. Two effective local search methods,i.e.revolver-based variable neighbourhood search and Hénon chaotic-based local search, are designed and incorporated into the EDA to enhance the local exploitation. The parameters of the proposed ECEDA are calibrated by means of a design of experiments approach. Simulation results and comparisons based on some benchmark instances show the efficiency of the proposed algorithm for solving the PFSP. [ABSTRACT FROM PUBLISHER]

The permutation flow-shop scheduling problem (PFSP) is a typical combinational and non-deterministic polynomial-hard problem, with discrete solution space. In this paper, a novel bacterial foraging optimisation algorithm (BFO) has been proposed to solve the PFSP. Difficulties such as slow convergent speeds and entrapment in the local optimum were incurred by the original BFO algorithm in solving a high-dimensional combinatorial optimisation problem. In order to deal with these difficulties, a differential evolution operator and a chaotic search operator were each introduced into the original BFO algorithm to enhance the activity levels of the individual bacterium and to extend the local searching space. Theoretical analysis showed that the improved algorithm obtained more motility in chemotaxis and could converge to the global optimum with a probability of 1. Simulation results and comparisons to both continuous and combinatorial benchmark problems were used to demonstrate the effectiveness of this novel optimisation algorithm. [ABSTRACT FROM AUTHOR]

The distributed production lines widely exist in modern supply chains and manufacturing systems. This paper aims to address the distributed no-wait flow shop scheduling problem (DNWFSP) with the makespan criterion by using proposed iterated greedy (IG) algorithms. Firstly, several speed-up methods based on the problem properties of DNWFSP are investigated to reduce the evaluation time of neighborhood with O (1) complexity. Secondly, an improved NEH heuristic is proposed to generate a promising initial solution, where the iteration step of the insertion step of NEH is applied to the factory after inserting a new job. Thirdly, four neighborhood structures (i.e. Critical_swap_single, Critical_insert_single, Critical_swap_multi, Critical_insert_multi ) based on factory assignment and job sequence adjustment are employed to escape from local optima. Fourthly, four local search methods based on neighborhood moves are proposed to enhance local searching ability, which contains LS_insert_critical_factory 1, LS_insert_critical_factory 2, LS_swap , and LS_insert . Finally, to organize neighborhood moves and local search methods efficiently, we incorporate them into the framework of variable neighborhood search (VNS), variable neighborhood descent (VND) and random neighborhood structure (RNS). Furthermore, three variants of IG algorithms are presented based on the designed VNS, VND and RNS. The parameters of the proposed IG algorithms are tuned through a design of experiments on randomly generated benchmark instances. The effectiveness of the initialize phase and local search methods is shown by numerical comparison, and the comparisons with the recently published algorithms demonstrate the high effectiveness and searching ability of the proposed IG algorithms for solving the DNWFSP. Ultimately, the best solutions of 720 instances from the well-known benchmark set of Naderi and Ruiz for the DNWFSP are proposed. [ABSTRACT FROM AUTHOR]

Inspired by the phenomenon of teaching and learning introduced by the teaching-learning based optimization (TLBO) algorithm, this paper presents a hybrid discrete optimization algorithm based on teaching-probabilistic learning mechanism (HDTPL) to solve the no-wait flow shop scheduling (NWFSSP) with minimization of makespan. The HDTPL consists of four components, i.e. discrete teaching phase, discrete probabilistic learning phase, population reconstruction, neighborhood search. In the discrete teaching phase, Forward-insert and Backward-insert are adopted to imitate the teaching process. In the discrete probabilistic learning phase, an effective probabilistic model is established with consideration of both job orders in the sequence and similar job blocks of selected superior learners, and then each learner interacts with the probabilistic model by using the crossover operator to learn knowledge. The population reconstruction re-initializes the population every several generations to escape from a local optimum. Furthermore, three types of neighborhood search structures based on the speed-up methods, i.e. Referenced-insert-search, Insert-search and Swap-search , are designed to improve the quality of the current learner and the global best learner. Moreover, the main parameters of HDTPL are investigated by the Taguchi method to find appropriate values. The effectiveness of HDTPL components is analyzed by numerical comparisons, and the comparisons with some efficient algorithms demonstrate the effectiveness and robustness of the proposed HDTPL in solving the NWFSSP. [ABSTRACT FROM AUTHOR]