A branch-and-bound algorithm for the single-row equidistant facility layout problem

In this paper, we deal with the single-row equidistant facility layout problem (SREFLP), which asks to find a one-to-one assignment of n facilities to n locations equally spaced along a straight line so as to minimize the sum of the products of the flows and distances between facilities. We develop a branch-and-bound algorithm for solving this problem. The lower bound is computed first by performing transformation of the flow matrix and then applying the well-known Gilmore–Lawler bounding technique. The algorithm also incorporates a dominance test which allows to drastically reduce redundancy in the search process. The test is based on the use of a tabu search procedure designed to solve the SREFLP. We provide computational results for problem instances of size up to 35 facilities. For a number of instances, the optimal value of the objective function appeared to be smaller than the best value reported in the literature.     

An improved memetic algorithm based on a dynamic neighbourhood for the permutation flowshop scheduling problem

The permutation flowshop scheduling problem (PFSP) has been extensively studied in the scheduling literature. In this paper, we present an improved memetic algorithm (MA) to solve the PFSP to minimise the total flowtime. In the proposed MA, we develop a stochastic local search based on a dynamic neighbourhood derived from the NEH method. During the evolution process, the size of the neighbourhood is dynamically adjusted to change the search focus from exploration to exploitation. In addition, we introduce a new population generation mechanism to guarantee both the quality and diversity of the new populations. We also design a diversity index for the population to monitor the diversity of the current population. If the diversity index is less than a given threshold value, the current population will be replaced by a new one with good diversity so that the proposed MA has good ability to overcome local optima. We conduct computational experiments to test the effectiveness of the proposed algorithm. The computational results on randomly generated problem instances and benchmark problem instances show that the proposed MA is effective and superior or comparable to other algorithms in the literature.     

Multi-level supply chain network design with routing

Recently, the multi-level and multi-facility industrial problem in supply chain management (SCM) has been widely investigated. One of the key issues, central to this problem in the current SCM research area is the interdependence among the location of facilities, the allocation of facilities, and the vehicle routing for the supply of raw materials and products. This paper studies the supply chain network design problem, which involves the location of facilities, allocation of facilities, and routing decisions. The proposed problem has some practical applications. For example, it is necessary for third party logistics (3PL) companies to manage the design of the network and to operate vehicle transportation. The purpose of this study is to determine the optimal location, allocation, and routing with minimum cost to the supply chain network. The study proposes two mixed integer programming models, one without routing and one with routing, and a heuristic algorithm based on LP-relaxation in order to solve the model with routing. The results show that a developed heuristic algorithm is able to find a good solution in a reasonable time.     

An adaptive multi-population genetic algorithm for job-shop scheduling problem

Job-shop scheduling problem (JSP) is a typical NP-hard combinatorial optimization problem and has a broad background for engineering application. Nowadays, the effective approach for JSP is a hot topic in related research area of manufacturing system. However, some JSPs, even for moderate size instances, are very difficult to find an optimal solution within a reasonable time because of the process constraints and the complex large solution space. In this paper, an adaptive multi-population genetic algorithm (AMGA) has been proposed to solve this problem. Firstly, using multi-populations and adaptive crossover probability can enlarge search scope and improve search performance. Secondly, using adaptive mutation probability and elite replacing mechanism can accelerate convergence speed. The approach is tested for some classical benchmark JSPs taken from the literature and compared with some other approaches. The computational results show that the proposed AMGA can produce optimal or near-optimal values on almost all tested benchmark instances. Therefore, we can believe that AMGA can be considered as an effective method for solving JSP.     

基于谱聚类下采样失衡数据下SVM故障检测

在故障诊断领域中,对传统支持向量机（SVM）算法在数据失衡情况下无法有效实现故障检测的不足,提出一种基于谱聚类下采样失衡数据下SVM故障检测算法。该算法在核空间中对多数类进行谱聚类,然后选择具有代表意义的信息点,最终实现样本均衡。将该算法应用在轴承故障检测领域,并同其他算法进行比较,试验结果表明本文建议的算法在失衡数据情况下较其他算法具有较强的故障检测性能。     

Modified Differential Evolution Algorithm for Solving Dynamic Optimization with Existence of Infeasible Environments

Dynamic constrained optimization is a challenging research topic in which the objective function and/or constraints change over time. In such problems, it is commonly assumed that all problem instances are feasible. In reality some instances can be infeasible due to various practical issues, such as a sudden change in resource requirements or a big change in the availability of resources. Decision-makers have to determine whether a particular instance is feasible or not, as infeasible instances cannot be solved as there are no solutions to implement. In this case, locating the nearest feasible solution would be valuable information for the decision-makers. In this paper, a differential evolution algorithm is proposed for solving dynamic constrained problems that learns from past environments and transfers important knowledge from them to use in solving the current instance and includes a mechanism for suggesting a good feasible solution when an instance is infeasible. To judge the performance of the proposed algorithm, 13 well-known dynamic test problems were solved. The results indicate that the proposed algorithm outperforms existing recent algorithms with a margin of 79.40% over all the environments and it can also find a good, but infeasible solution, when an instance is infeasible.     

Simultaneous order-lot pegging and wafer release planning for semiconductor wafer fabrication facilities

In semiconductor wafer fabrication facilities, order-lot pegging is the process of assigning wafer lots to orders and meeting the due dates of orders is considered one of the most important operational issues. In many cases of order-lot pegging, some orders cannot be fulfilled with the current wafers in the lots being processed, necessitating the release of additional new wafer lots into the wafer fabrication facility. In this paper, we propose a simultaneous decision model for order-lot pegging and wafer release planning in semiconductor wafer fabrication facilities, and develop a Lagrangian heuristic for solving the model. The results of computational experiments conducted using randomly generated problem instances that mimic actual field data from a Korea semiconductor wafer fabrication facility indicate that the performance of the Lagrangian heuristic is superior to that of a practical greedy algorithm for practical-sized problem instances. The results also point to how sensitivity analysis can be used to answer important managerial questions for effective management of the semiconductor wafer fabrication process.     

Single machine scheduling problem with batch setups involving positional deterioration effects and multiple rate-modifying activities

This article considers a single machine scheduling problem with batch setups, positional deterioration effects, and multiple optional rate-modifying activities to minimize the total completion time. This problem is formulated as an integer quadratic programming problem. In view of the complexity of optimally solving this problem, a two-phase heuristic algorithm is proposed where an optimal but non-integer solution is obtained in the first phase by solving a continuous relaxed version of the problem. This solution serves as a lower bound for the optimal value of the total completion time. The second phase of the algorithm generates an integer solution using a simple rounding scheme that is optimum or very close to optimum for this problem. Empirical evaluation and comparison with an existing heuristic algorithm show that the proposed heuristic algorithm is substantially more effective in solving large-size problem instances.     

The equipment maintenance scheduling problem in a coal production system

This paper addresses an equipment maintenance scheduling problem in a coal production system which includes three consecutive stages: the coal mining stage, the coal washing stage and the coal loading stage. Each stage is composed of different equipment that needs maintenance each day. There exists intermediate storage with finite capacities and the finished products are transported by train. Moreover, some equipment has a different preference for (aversion to) the start time of maintenance (STOM). The objective is to minimise the weighted sum of aversion about STOM, changeover times and train waiting time. We first formulate this problem into a mixed integer linear programming (MILP) model, then a hybrid genetic algorithm (HGA) is proposed to solve it. The proposed method has been tested on a practical coal enterprise in China and some randomly generated instances. Computational results indicate that our algorithm can produce near-optimal solutions efficiently.     

A genetic algorithm for solving the economic lot scheduling problem in flow shops

In this study, we propose a hybrid genetic algorithm (HGA) to solve the economic lot scheduling problem in flow shops. The proposed HGA utilizes a so-called Proc PLM heuristic that tests feasibility for the candidate solutions obtained in the evolutionary process of genetic algorithm. When a candidate solution is infeasible, we propose to use a binary search heuristic to ‘fix’ the candidate solution so as to obtain a feasible solution with the minimal objective value. To evaluate the performance of the proposed HGA, we randomly generate a total of 2100 instances from seven levels of utilization rate ranged from 0.45 to 0.80. We solve each of those 2100 instances by the proposed HGA and the other solution approaches in the literature. Our experiments show that the proposed HGA outperforms traditional methods for solving the economic lot scheduling problem in flow shops.     

A very large scale neighborhood search algorithm for the q-mode problem

The q-mode problem is a combinatorial optimization problem that arises in the context of partitioning a given collection of data vectors with categorical attributes. A neighborhood search algorithm is proposed for solving the q-mode problem. This algorithm is based on a very large scale neighborhood that is implicitly searched using network flow techniques. The algorithm is evaluated through a computational experiment using randomly generated instances. The results show that in general this algorithm obtains very-good-quality local optima, and that in instances with strong natural clusters the algorithm consistently finds optimal or near-optimal solutions.     

A branch-and-bound algorithm for minimizing the sum of maximum earliness and tardiness with unequal release times

This article addresses the problem of minimizing the sum of maximum earliness and tardiness on a single machine with unequal release times. It is proven that this problem is NP-hard in the strong sense and a branch-and-bound algorithm is developed as an exact method. In the proposed algorithm, modified dispatching rules based on different release times are proposed as the upper bound, while a procedure considering preemption assumption is used to obtain a good lower bound. Also, dominance rules based on no unforced idle time, adjacent pairwise interchanges in the base problem, and job blocks are used to fathom the nodes. In order to evaluate the efficiency of the proposed algorithm, 4,860 instances were randomly generated, varying from 7 to 1,000 jobs. It is shown that the branch-and-bound algorithm was capable of optimally solving 94.1% of the instances, showing its efficiency in solving all problem sizes.     

A priority rule-based constructive heuristic and an improvement method for balancing assembly lines with parallel multi-manned workstations

Assembly lines of big-size products such as buses, trucks and helicopters are very different from the lines studied in the literature. These products’ manufacturing processes have a lot of tasks most of which have long task times. Since traditional assembly line models including only one worker in each station (i.e. simple assembly lines) or at most two workers (two-sided assembly lines) may not be suitable for manufacturing these type of products, they need much larger shop floor for a number of stations and long product flow times. In this study, an assembly line balancing problem (ALBP) with parallel multi-manned stations is considered. Following the problem definition, a mixed integer programming formulation is developed. A detailed study of priority rules for simple ALBPs is also presented, and a new efficient constructive heuristic algorithm based on priority rules is proposed. In order to improve solutions found by the constructive heuristic, a genetic algorithm-based solution procedure is also presented. Benchmark instances in the literature are solved by using the proposed mathematical programming formulation. It has been seen that only some of the small-size instances can be solved optimally by this way. So the efficiency of the proposed heuristic method is verified in small-size instances whose optimal solutions are found. For medium- and big-size instances, heuristics’ results and CPU times are demonstrated. A comparative evaluation with a branch and bound algorithm that can be found in the literature is also carried out, and results are presented.     

Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm

The distributed permutation flowshop scheduling problem (DPFSP) is a newly proposed topic in the shop scheduling field, which has important application in globalised and multi-plant environments. This study presents a modified iterated greedy (MIG) algorithm for this problem to minimise the maximum completion time among all the factories. Compared with previous approaches, the proposed algorithm is simpler yet more effective, more efficient, and more robust in solving the DPFSP. To validate the performance of the proposed MIG algorithm, computational experiments and comparisons are conducted on an extended benchmark problem set of Taillard. Despite its simplicity, the computational results show that the proposed MIG algorithm outperforms all existing algorithms, and the best-known solutions for almost half of instances are updated. This study can be offered as a contribution to the growing body of work on both theoretically and practically useful approaches to the DPFSP.     

A note on: A modified generalized extremal optimization algorithm for the quay crane scheduling problem with interference constraints

In a recent article, Guo, Cheng and Wang proposed a randomized search algorithm, called modified generalized extremal optimization (MGEO), to solve the quay crane scheduling problem for container groups under the assumption that schedules are unidirectional. The authors claim that the proposed algorithm is capable of finding new best solutions with respect to a well-known set of benchmark instances taken from the literature. However, as shown in this note, there are some errors in their work that can be detected by analysing the Gantt charts of two solutions provided by MGEO. In addition, some comments on the method used to evaluate the schedule corresponding to a task-to-quay crane assignment and on the search scheme of the proposed algorithm are provided. Finally, to assess the effectiveness of the proposed algorithm, the computational experiments are repeated and additional computational experiments are provided.     

Machine scheduling in underground mining: an application in the potash industry

In this paper, a scheduling problem that occurs in potash mining is introduced, where a block excavation sequence has to be found taking into account a limited number of underground machines as well as safety-related restrictions. The aim is to minimize the maximum completion time of excavations, i.e., the makespan. The resulting problem can be transformed into a hybrid flow shop scheduling problem with reentry, unrelated machines, and job-precedences. A mixed-integer linear model is presented and small-scale instances are solved with CPLEX. In order to tackle medium- and large-scale instances heuristically, a basic and an advanced multi-start algorithm are developed, based on a specific priority rule-based construction procedure. In addition, a modified version of the Giffler and Thompson procedure is applied. Computational experiments are conducted on problem instances derived from real-world data in order to evaluate the performances of the proposed solution procedures.     

An effective hybrid immune algorithm for solving the distributed permutation flow-shop scheduling problem

In this article, an effective hybrid immune algorithm (HIA) is presented to solve the distributed permutation flow-shop scheduling problem (DPFSP). First, a decoding method is proposed to transfer a job permutation sequence to a feasible schedule considering both factory dispatching and job sequencing. Secondly, a local search with four search operators is presented based on the characteristics of the problem. Thirdly, a special crossover operator is designed for the DPFSP, and mutation and vaccination operators are also applied within the framework of the HIA to perform an immune search. The influence of parameter setting on the HIA is investigated based on the Taguchi method of design of experiment. Extensive numerical testing results based on 420 small-sized instances and 720 large-sized instances are provided. The effectiveness of the HIA is demonstrated by comparison with some existing heuristic algorithms and the variable neighbourhood descent methods. New best known solutions are obtained by the HIA for 17 out of 420 small-sized instances and 585 out of 720 large-sized instances.     

An iterative rounding search-based algorithm for the disjunctively constrained knapsack problem

This article proposes an iterative rounding search-based algorithm for approximately solving the disjunctively constrained knapsack problem. The problem can be viewed as a variant of the well-known knapsack problem with some sets of incompatible items. The algorithm considers two key features: a rounding strategy applied to the fractional variables of a linear relaxation and a neighbouring strategy used for improving the quality of the solutions at hand. Both strategies are iterated into a process based on adding a series of (i) valid cardinality constraints and (ii) lower bounds used for bounding the objective function. The proposed algorithm is analysed computationally on a set of benchmark instances of the literature. The proposed algorithm outperforms the Cplex solver and the results obtained improve on most existing solutions.     

New block properties for flowshop scheduling with blocking and their application in an iterated greedy algorithm

This paper proposes new block properties for the flowshop scheduling problem with blocking to minimise makespan. A pruning procedure based on these proposed properties is used in the construction phase of an iterated greedy algorithm to decrease the total number of solutions to be examined to find an optimal schedule. Computational results using Taillard’s benchmark problem instances show that the new block properties help to eliminate more ‘unpromising’ solutions than the classic properties. In addition, the effectiveness of the proposed algorithm is verified by comparison with some high-performing algorithms for the considered problem.     

Ant colony optimisation algorithm for distribution-allocation problem in a two-stage supply chain with a fixed transportation charge

In a fixed charge transportation problem, each route is associated with a fixed charge (or a fixed cost) and a transportation cost per unit transported. The presence of the fixed cost makes the problem difficult to solve, thereby requiring the use of heuristic methods. In this paper, an algorithm based on ant colony optimisation is proposed to solve the distribution-allocation problem in a two-stage supply chain with a fixed transportation cost for a route. A numerical study on benchmark problem instances has been carried out. The results obtained for the proposed algorithm have been compared with that for the genetic algorithm-based heuristic currently available in the literature. It is statistically confirmed that the proposed algorithm provides significantly better solutions.