A global-local neighborhood search algorithm and tabu search for flexible job shop scheduling problem

HSMVS: heuristic search for minimum vertex separator on massive graphs

In graph theory, the problem of finding minimum vertex separator (MVS) is a classic NP-hard problem, and it plays a key role in a number of important applications in practice. The real-world massive graphs are of very large size, which calls for effective approximate methods, especially heuristic search algorithms. In this article, we present a simple yet effective heuristic search algorithm dubbed HSMVS for solving MVS on real-world massive graphs. Our HSMVS algorithm is developed on the basis of an efficient construction procedure and a simple yet effective vertex-selection heuristic. Experimental results on a large number of real-world massive graphs present that HSMVS is able to find much smaller vertex separators than three effective heuristic search algorithms, indicating the effectiveness of HSMVS. Further empirical analyses confirm the effectiveness of the underlying components in our proposed algorithm.

Minimizing the total waste in the one-dimensional cutting stock problem with the African buffalo optimization algorithm

The one-dimensional cutting-stock problem (1D-CSP) consists of obtaining a set of items of different lengths from stocks of one or different lengths, where the minimization of waste is one of the main objectives to be achieved. This problem arises in several industries like wood, glass, and paper, among others similar. Different approaches have been designed to deal with this problem ranging from exact algorithms to hybrid methods of heuristics or metaheuristics. The African Buffalo Optimization (ABO) algorithm is used in this work to address the 1D-CSP. This algorithm has been recently introduced to solve combinatorial problems such as travel salesman and bin packing problems. A procedure was designed to improve the search by taking advantage of the location of the buffaloes just before it is needed to restart the herd, with the aim of not to losing the advance reached in the search. Different instances from the literature were used to test the algorithm. The results show that the developed method is competitive in waste minimization against other heuristics, metaheuristics, and hybrid approaches.

Melhim LK, Jemmali M, El Ayeb F, Alharbi H, Banjar A. Novel variable neighborhood search heuristics for truck management in distribution warehouses problem

Logistics and sourcing management are core in any supply chain operation and are among the critical challenges facing any economy. The specialists classify transport operations and warehouse management as two of the biggest and costliest challenges in logistics and supply chain operations. Therefore, an effective warehouse management system is a legend to the success of timely delivery of products and the reduction of operational costs. The proposed scheme aims to discuss truck unloading operations problems. It focuses on cases where the number of warehouses is limited, and the number of trucks and the truck unloading time need to be manageable or unknown. The contribution of this article is to present a solution that: (i) enhances the efficiency of the supply chain process by reducing the overall time for the truck unloading problem; (ii) presents an intelligent metaheuristic warehouse management solution that uses dispatching rules, randomization, permutation, and iteration methods; (iii) proposes four heuristics to deal with the proposed problem; and (iv) measures the performance of the proposed solution using two uniform distribution classes with 480 trucks' unloading times instances. Our result shows that the best algorithm is O I S ~ , as it has a percentage of 78.7% of the used cases, an average gap of 0.001, and an average running time of 0.0053 s.

A Self-Adjusting Search Domain Method-Based Genetic Algorithm for Solving Flexible Job Shop Scheduling Problem

As a nondeterministic polynomial (NP) problem, the flexible job shop scheduling problem (FJSP) is a difficult problem to be solved in terms of finding an acceptable solution. In last decades, genetic algorithm (GA) displays very promising performance in the field. In this article, a hybrid algorithm combining global and local search with reinitialization (GLRe)-based GA is proposed to minimize makespan for FJSP. The solution of FJSP is conveniently represented by a double-layer chromosome representation method, which is convenient for subsequent genetic operations, that is, sorting of operations and selection of machines. Two strategies of choosing the job with the most remaining operations (CRO) and 6-dimensional variable determined search position (6D-VSP) are proposed as two components for GA, which are applied to generate a population with superior quality and reduce the global search space during the initialization stage. At the same time, in order to prevent the loss of diversity during evolution, a reinitialization strategy is introduced in the later stage of evolution to adaptively adjust the search domain of the problem. Finally, two sets of benchmark data are tested. The experimental results demonstrate the accuracy and effectiveness of the GLRe proposed in this article for solving FJSP.