Search

This paper focuses on the blocking flow shop scheduling problem with the objective of total flowtime minimisation. This problem assumes that there are no buffers between machines and, due to its application to many manufacturing sectors, it is receiving a growing attention by researchers during the last years. Since the problem is NP-hard, a large number of heuristics have been proposed to provide good solutions with reasonable computational times. In this paper, we conduct a comprehensive evaluation of the available heuristics for the problem and for related problems, resulting in the implementation and testing of a total of 35 heuristics. Furthermore, we propose an efficient constructive heuristic which successfully combines a pool of partial sequences in parallel, using a beam-search-based approach. The computational experiments show the excellent performance of the proposed heuristic as compared to the best-so-far algorithms for the problem, both in terms of quality of the solutions and of computational requirements. In fact, despite being a relative fast constructive heuristic, new best upper bounds have been found for more than 27% of Taillard’s instances. [ABSTRACT FROM AUTHOR]

• Mathematical notations and constraints of DHHFSP with blocking constraints is formulated. • NEH-Increase heuristic strategy is designed to allocate the jobs to heterogeneous factories. • The neighborhood search strategies cooperatively optimize the scheduling sequence. • A local intensification strategy is presented to reinforce the exploration ability. The hybrid flow shop and distributed flow shop problems have been extensively studied due to their wide industrial applications. However, the distributed heterogeneous hybrid flow shop problems (DHHFSP) with blocking constraints have not yet been well studied up to date. This paper considers how to arrange a variety of jobs to different heterogeneous factories, and each factory has a minimal makespan. The innovations of this paper lie in presenting a mathematical model of the DHHFSP with blocking constraints and designing a collaborative iterative greedy (CIG) algorithm. The CIG contains the problem-specific initialization strategy, the neighborhood search strategy, the destruction-reconstruction strategy, and the local intensification strategy. The cross-factory and inner-factory neighborhood search strategies based on two swap operators are adopted to reduce the blocking time. The local intensification strategy is developed to optimize the scheduling sequence of each factory. The proposed algorithm is empirically compared with five state-of-the-art algorithms on 60 different instance sets. The experimental results show that the proposed algorithm significantly outperforms the compared ones in terms of objective values and relative percentage deviation values. [ABSTRACT FROM AUTHOR]

• The general speed-density diagram of bidirectional pedestrian flow is proposed. • The speed-density diagram of bidirectional pedestrian flow is calibrated by the experimental data. • The pedestrian counter flow is simulated by using the collection of ordinary differential equations. • A pedestrian counter flow control model is proposed to avoid blocking in bidirectional corridors. In this paper, we develop a control model for pedestrian counter flow to avoid blocking in bidirectional corridors. Considering the conflict between two streams, we formulate a general speed-density diagram of bidirectional pedestrian flow based on the previous models in the literature. To accommodate a possible inhomogeneous pedestrian density along the corridor and inflows from various directions, the corridor is divided into several sections. A pedestrian counter flow model is developed to simulate the pedestrian flow between sections by using a collection of ordinary differential equations. The control objective is proposed based on user equilibrium and a capacity-oriented principle, and a linear feedback control model is developed to achieve a controlled inflow that reduces the density of each section to an acceptable level. The level of service of the corridor is improved, and blocking is eliminated by the proposed control model. Finally, sensitivity analysis suggests that the model performance can be improved if the conflict level is reduced. [ABSTRACT FROM AUTHOR]

Abstract: This paper focuses on the study of cyclic job-shop problems with transportation and blocking. Within this domain, there are many real world problems like large scale productions, robotic cells, software pipelining or hoist scheduling. The aim in general is to find, for each machine, a feasible order of all the operations processed on this machine, so that an objective function is optimised. In this paper, we consider the problem of minimising the cycle time (maximising the throughput) in a job-shop environment, where the jobs are transported by a single robot between the machines. Additionally to the problem description, we will give some explanations and interpretation possibilities of the problem height, which is often omitted in the literature. As the main contribution, we will present a new integer programming formulation and show that it outperforms an existing model from the literature. [Copyright &y& Elsevier]

Highlights • An iterated greedy algorithm for the total tardiness parallel blocking flow shop problem. • Constructive heuristics which considers the characteristics of the problem. • Design of experiments to calibrate and select the best variant. Abstract This paper proposes an iterated greedy algorithm for scheduling jobs in F parallel flow shops (lines), each consisting of a series of m machines without storage capacity between machines. This constraint can provoke the blockage of machines if a job has finished its operation and the next machine is not available. The criterion considered is the minimization of the sum of tardiness of all the jobs to schedule, i.e., minimization of the total tardiness of jobs. Notice that the proposed method is also valid for solving the Distributed Permutation Blocking Flow Shop Scheduling Problem (DBFSP), which allows modelling the scheduling process in companies with more than one factory when each factory has an identical flow shop configuration. Firstly, several constructive procedures have been implemented and tested to provide an efficient solution in terms of quality and CPU time. This initial solution is later improved upon with an iterated greedy algorithm that includes a variable neighbourhood search for interchanging or reassigning jobs from the critical line to other lines. Next, two strategies have been tested for selecting the critical line; the one with a higher total tardiness of jobs and the one with a job that has the highest tardiness. The experimental design chooses the best combination of initial solution and critical line selection. Finally, we compare the performance of the proposed algorithm against other benchmark algorithms proposed for the DPFSP, which have been adapted to the problem being considered here since, to the best of our knowledge, this is the first attempt to solve either the Parallel Blocking Flow Shop problem or the Distributed Blocking Flow Shop problem with the goal of minimizing total tardiness. This comparison has allowed us to confirm the good performance of the proposed method. [ABSTRACT FROM AUTHOR]

Record linkage, referred to also as entity resolution, is the process of identifying pairs of records representing the same real world entity (e.g. a person) within a dataset or across multiple datasets. In order to reduce the number of record comparisons, record linkage frameworks initially perform a process referred to as blocking, which involves splitting records into a set of blocks using a partition (or blocking) scheme. This restricts comparisons among records that belong to the same block during the linkage process. Existing blocking methods are often evaluated using different metrics and independently of the choice of the subsequent linkage method, which makes the choice of an optimal approach very subjective. In this paper we demonstrate that existing evaluation metrics fail to provide strong evidence to support the selection of an optimal blocking method. We conduct an extensive evaluation of different blocking methods using multiple datasets and some commonly applied linkage techniques to show that evaluation of a blocking method must take into consideration the subsequent linkage phase. We propose a novel evaluation technique that takes into consideration multiple factors including the end-to-end running time of the combined blocking and linkage phases as well as the linkage technique used. We empirically demonstrate using multiple datasets that according to this novel evaluation technique some blocking methods can be fairly considered superior to others, while some should be deemed incomparable according to those factors. Finally, we propose a novel blocking method selection procedure that takes into consideration the linkage proficiency and end-to-end time of different blocking methods combined with a given linkage technique. We show that this technique is able to select the best or near best blocking method for unseen data. [ABSTRACT FROM AUTHOR]

This paper presents an efficient, exact and sustainable schedulability analysis for hierarchical scheduling when a hybrid scheduling strategy is applied to a uniprocessor real-time system. We concentrate on the situation in which each application is to run on a server with an earliest deadline first (EDF) scheduler, and the tasks of each application are required to meet their given hard real-time constraints. We show how blocking can be considered in a hierarchical system to let the applications and the tasks share non-preemptable resources at global and local levels. This hierarchical system model is easy to implement, and the proposed analysis does not require making any online scheduling decisions, hence no extra scheduling overhead is required. Through extensive experiments, we show that our schedulability analysis has a very high acceptance ratio for the application tasks and that the proposed analysis is also highly efficient; in nearly all cases, less than 12 times the calculations of the response time on average is required to complete an analysis for a set of tasks within an application. Therefore, the proposed schedulability analysis significantly reduces the required computations and increases the acceptance ratio. Furthermore, the proposed approach is quite general and there are no restrictions on the task parameters, each task could be periodic or sporadic, and they can have arbitrary relative deadlines. [ABSTRACT FROM AUTHOR]

With the increase in production levels, a pattern of industrial production has shifted from a single factory to multiple factories, resulting in a distributed production model. The distributed flowshop scheduling problem (DPFSP) is of great research significance as a frequent pattern in real production activities. In this paper, according to real-world scenarios, we have added blocking constraints and sequence-dependent setup times (SDST) to the DFSP and proposed a distributed blocking flowshop scheduling problem with sequence-dependent setup times (DBFSP_SDST). In a distributed environment, the allocation of resources and utilization have become an urgent problem to be solved. In addition, scheduling problems related to resource conservation have also attracted increasing attention. Therefore, we study DBFSP_SDST and consider minimizing the energy consumption cost of the critical factory (critical factory is the factory with maximum energy consumption cost) under resource balance. To tackle this problem, an effective iterated greedy algorithm based on a learning-based variable neighborhood search algorithm (VNIG) is proposed. In VNIG, an efficient construction heuristic is well designed. Two different local searches based on the characteristics of the proposed problem are developed to enhance the local exploitation by neighborhood searching. A learning-based selection variable neighborhood search strategy is designed to avoid the solution trapping in local optima. By conducting extensive simulation experiments, the proposed VNIG shows superior performance compared with artificial chemical reaction optimization (CRO, 2017), the discrete artificial bee colony algorithm (DABC, 2018), the iterative greedy algorithm with a variable neighborhood search scheme (IGR, 2021), and the evolution strategy approach (ES, 2022). • A mathematical model of an energy-balance DBFSP_SDST is formulated. • An efficient heuristic is presented to generate a high-quality initial solution. • Two different local searches based on the characteristics of the proposed problem are developed. • A learning-based selection variable neighborhood search is designed. • The VNIG shows superior performance compared with four algorithms on 90 instances. [ABSTRACT FROM AUTHOR]

This paper presents a high performing Discrete Artificial Bee Colony algorithm for the blocking flow shop problem with flow time criterion. To develop the proposed algorithm, we considered four strategies for the food source phase and two strategies for each of the three remaining phases (employed bees, onlookers and scouts). One of the strategies tested in the food source phase and one implemented in the employed bees phase are new. Both have been proved to be very effective for the problem at hand. The initialization scheme named HPF2( λ , μ ) in particular, which is used to construct the initial food sources, is shown in the computational evaluation to be one of the main procedures that allow the DABC_RCT to obtain good solutions for this problem. To find the best configuration of the algorithm, we used design of experiments (DOE). This technique has been used extensively in the literature to calibrate the parameters of the algorithms but not to select its configuration. Comparing it with other algorithms proposed for this problem in the literature demonstrates the effectiveness and superiority of the DABC_RCT. [ABSTRACT FROM AUTHOR]

In this paper, we develop an approximation method for throughput in tandem queues with multiple independent reliable servers at each stage and finite buffers between service stations. We consider the blocking after service (BAS) blocking protocol of each service stage. The service time distribution of each server is exponential. The approximation is based on the decomposition of the system into a set of coupled subsystems which are modeled by two-stage tandem queue with two buffers and are analyzed by using the level dependent quasi-birth-and-death (LDQBD) process. [ABSTRACT FROM AUTHOR]

The blocking job shop (BJS) problem is an extension of a job shop problem with no buffer constraints. It means that after a job is completed on the current machine, it remains on that machine until the next machine becomes available. This paper addresses an extension of the BJS problem, which takes into account transferring jobs between different machines using a limited number of automated guided vehicles (AGV), called a BJS–AGV problem. Two integer non-linear programming (INLP) models are proposed. A two-stage heuristic algorithm that combines an improving timetabling method and a local search is proposed to solve the BJS–AGV problem. A neighborhood structure in the local search is proposed based on a disjunctive graph model. According to the characteristics of the BJS–AGV problem, four principles are proposed to guarantee the feasibility of the search neighborhood. Computation results are presented for a set of benchmarking tests, some of which are enlarged by transportation times between different machines. The numerical results show the effectiveness of the proposed two-stage algorithm. [ABSTRACT FROM AUTHOR]

Abstract: This paper proposes a discrete particle swarm optimization (DPSO) algorithm for the m-machine permutation flowshop scheduling problem with blocking to minimize the makespan, which has a strong industrial background, e.g., many production processes of chemicals and pharmaceuticals in chemical industry can be reduced to this problem. To prevent the DPSO from premature convergence, a self-adaptive diversity control strategy is adopted to diversify the population when necessary by adding a random perturbation to the velocity of each particle according to a probability controlled by the diversity of the current population. In addition, a stochastic variable neighborhood search is used as the local search to improve the search intensification. Computational results using benchmark problems show that the proposed DPSO algorithm outperforms previous algorithms proposed in the literature and that it can obtain 111 new best known upper bounds for the 120 benchmark problems. [Copyright &y& Elsevier]

This paper focuses on the scheduling problem of flexible assembly systems (FASs) without intermediate buffers. The main characteristic of the problem is that as no intermediate buffer exists between consecutive machines, blocking and deadlock constraints must be considered. Petri nets are used to model the considered FASs, and a novel hybrid particle swarm optimization (HPSO) algorithm is proposed to minimize the makespan. The proposed algorithm is the combination of the discrete PSO, particle repairing algorithm, particle improvement strategy, and local search method. First, each candidate solution for the problem is encoded as a permutation with repetition of part numbers, and can be uniquely decoded into a sequence of transitions. To ensure the feasibility of solutions, a repairing algorithm is developed, in which a deadlock avoidance policy is used. Then, a particle improvement policy is proposed to improve the performance of particles. Meanwhile, a local search method is designed and incorporated into HPSO to improve its search ability. Experiments are conducted to verify the effectiveness of the particle improvement policy and local search method. Comparisons between HPSO and ten other algorithms are performed. The comparison results and analysis show that our proposed algorithm can find feasible solutions for all tested instances, and is superior to other scheduling algorithms in terms of finding better solutions and performance stability. [ABSTRACT FROM AUTHOR]

We consider the distributed blocking flowshop scheduling problem (DBFSP) which is a meaningful generalization of the blocking flowshop scheduling problem in the distributed production environment. The objective of minimizing the total flowtime is relevant and important in the current dynamic manufacturing environment, but, as far as we know, it has not been investigated in the DBFSP previously. In this paper, a population-based iterated greedy (PBIG) algorithm is proposed to solve the DBFSP with the total flowtime criterion, which takes the advantage of both the population-based search approach and the iterated greedy algorithm. First, an effective constructive heuristic is proposed by integrating two existing constructive approaches to initialize the population with a high level of quality and diversity. Second, three different procedures to generate the offspring solutions are tested for the effective exploration capability, each of which rationally combines the destruction, reconstruction and selection operator. Third, the insertion neighborhood and swap neighborhood are investigated to enhance the local exploitation ability and a hybrid local search procedure that utilizes simultaneously both the two neighborhoods are proposed. The comprehensive experimental evaluation based on a total of 720 well-known instances shows that the proposed algorithms outperform the existing effective algorithms at a significant margin. • We study the distributed blocking flowshop scheduling problem for total flowtime. • We propose a novel population-based iterated greedy algorithm. • We propose a constructive heuristic to obtain good initial solutions. • We propose three local search methods and three selection operators. • We compare the proposed algorithms with effective algorithms in the literature. [ABSTRACT FROM AUTHOR]

The hybrid flow shop scheduling problem is one of the most relevant optimization problem in manufacturing industry. In this paper, we investigate the blocking hybrid flow shop scheduling problem under the constraint of sequence dependent setup time. The objective is to minimize the total tardiness and earliness with uniform parallel machines under the constraint of sequence dependent setup time. To solve this kind of problems, significant developments of new meta-heuristic algorithms make it possible to implement new metaheuristics inspired by the behavior of living beings or natural phenomena. In this context, we suggest six algorithms based on the migratory bird optimization and the water wave optimization algorithms. We give three new versions for each meta-heuristic in order to solve this optimization problem. The main improvement of the suggested algorithms concerns the exploration phase of the neighborhood system. The enhancement approaches are based on the iterated greedy algorithm, the greedy randomized adaptive search procedure, the path relinking technique and the local search procedures. These modifications in the two nature inspired meta-heuristics make it possible to develop a new neighborhood generation structure constituting hybrid optimization algorithms. A comparative study between the different proposed methods is carried out on a variety of problems ranging from small to relatively large size instances. The simulations show good performances recorded by the water wave optimization algorithm in term of quality and convergence speed towards the best solution. • Blocking hybrid flow shop scheduling problem is studied. • Uniform parallel machines with setup time is considered. • Enhanced migratory bird algorithm is used to solve the problem. • Water wave optimization algorithm is considered. • Several benchmarks are used to evaluate the performance of algorithms. [ABSTRACT FROM AUTHOR]