A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date

Although the concept of just-in-time (JIT) production systems has been proposed for over two decades, it is still important in real-world production systems. In this paper, we consider minimizing the total weighted earliness and tardiness with a restrictive common due date in a single machine environment, which has been proved as an NP-hard problem. Due to the complexity of the problem, metaheuristics, including simulated annealing, genetic algorithm, tabu search, among others, have been proposed for searching good solutions in reasonable computation times. In this paper, we propose a hybrid metaheuristic that uses tabu search within variable neighborhood search (VNS/TS). There are several distinctive features in the VNS/TS algorithm, including different ratio of the two neighborhoods, generating five points simultaneously in a neighborhood, implementation of the B/F local search, and combination of TS with VNS. By examining the 280 benchmark problem instances, the algorithm shows an excellent performance in not only the solution quality but also the computation time. The results obtained are better than those reported previously in the literature.     

Scheduling in a two-machine flowshop for the minimization of the mean absolute deviation from a common due date

This paper addresses the minimization of the mean absolute deviation from a common due date in a two-machine flowshop scheduling problem. We present heuristics that use an algorithm, based on proposed properties, which obtains an optimal schedule for a given job sequence. A new set of benchmark problems is presented with the purpose of evaluating the heuristics. Computational experiments show that the developed heuristics outperform results found in the literature for problems up to 500 jobs.     

A hybridisation of adaptive variable neighbourhood search and large neighbourhood search: Application to the vehicle routing problem

In this paper, an adaptive variable neighbourhood search (AVNS) algorithm that incorporates large neighbourhood search (LNS) as a diversification strategy is proposed and applied to the capacitated vehicle routing problem. The AVNS consists of two stages: a learning phase and a multi-level VNS with guided local search. The adaptive aspect is integrated in the local search where a set of highly successful local searches is selected based on the intelligent selection mechanism. In addition, the hybridisation of LNS with the AVNS enables the solution to escape from the local minimum effectively. To make the algorithm more competitive in terms of the computing time, a simple and flexible data structure and a neighbourhood reduction scheme are embedded. Finally, we adapt a new local search move and an effective removal strategy for the LNS. The proposed AVNS was tested on the benchmark data sets from the literature and produced very competitive results.     

A multi-phase oscillated variable neighbourhood search algorithm for a real-world open vehicle routing problem

The aim of this study is to solve the newspaper delivery optimization problem for a media delivery company in Turkey by reducing the total cost of carriers. The problem is modelled as an open vehicle routing problem (OVRP), which is a variant of the vehicle routing problem. A variable neighbourhood search-based algorithm is proposed to solve a real-world OVRP. The proposed algorithm is tested with varieties of small and large-scale benchmark suites and a very large-scale real-world problem instance. The results of the proposed algorithm provide either the best known solution or a competitive solution for each of the benchmark instances. The algorithm also improves the real-world company’s solutions by more than 10%.     

MaxMinMin p-dispersion problem: A variable neighborhood search approach

In this work we have developed a Variable Neighborhood Search (VNS) method in order to solve the MaxMinMin p-dispersion problem, which adds a new type of plateau search mechanism to the classical VNS metaheuristic framework. Besides, several other contributions have been made to the basic VNS heuristic in terms of the ascent and perturbation functions. To the best of our knowledge this is the first application of the VNS to the MaxMinMin problem and our approach, compared to previous methods, finds or improves the results for all of the large-sized benchmarks with low computational efforts. Finding most of the proven optimal solutions in a fraction of a second, the robustness and quality of the solutions and the low complexity of the methods demonstrate the strength of the proposed heuristic solution procedures.     

A differential evolution approach for the common due date early/tardy job scheduling problem

The problem of scheduling multiple jobs on a single machine so that they are completed by a common specified date is addressed in this paper. This type of scheduling set costs depend on whether a job is finished before (earliness) or after (tardiness) the specified due date. The objective is to minimize a summation of earliness and tardiness penalty costs. Minimizing these costs pushes the completion time of each job as close as possible to the due date. The use of differential evolution as the optimization heuristic to solve this problem is investigated in this paper. Computational experiments over multiple (280 in total) public benchmark problems with up to 1000 jobs to be scheduled show the effectiveness of the proposed approach. The results obtained are of high quality putting new upper bounds to 60% of the benchmark instances.     

Hybrid flowshop scheduling with sequence‐dependent setup times by hybridizing max–min ant system,simulated annealing and variable neighbourhood search

This paper deals with the hybrid flowshop scheduling problems with sequence‐dependent setup times. To minimize the makespan, we propose hybrid metaheuristic approach, which integrates several features from ant colony optimization, simulated annealing and variable neighbourhood search in a new configurable scheduling algorithm. Our proposed algorithms are tuned by means of design of experiments approach. We present computational experiments on standard test problems and compare the results with the several algorithms presented previously. The results illustrate that the hybrid metaheuristic outperforms the other algorithms.     

Optimizing frequent time-window selection for association rules mining in a temporal database using a variable neighbourhood search

In this study, we investigate the problem of maximum frequent time-window selection (MFTWS) that appears in the process of discovering association rules time-windows (ARTW). We formulate the problem as a mathematical model using integer programming that is a typical combination problem with a solution space exponentially related to the problem size. A variable neighbourhood search (VNS) algorithm is developed to solve the problem with near-optimal solutions. Computational experiments are performed to test the VNS algorithm against a benchmark problem set. The results show that the VNS algorithm is an effective approach for solving the MTFWS problem, capable of discovering many large-one frequent itemset with time-windows (FITW) with a larger time-coverage rate than the lower bounds, thus laying a good foundation for mining ARTW.     

A variable neighbourhood search for fast train scheduling and routing during disturbed railway traffic situations

This paper focuses on the development of metaheuristic algorithms for the real-time traffic management problem of scheduling and routing trains in complex and busy railway networks. This key optimization problem can be formulated as a mixed integer linear program. However, since the problem is strongly NP-hard, heuristic algorithms are typically adopted in practice to compute good quality solutions in a short computation time. This paper presents a number of algorithmic improvements implemented in the AGLIBRARY optimization solver in order to improve the possibility of finding good quality solutions quickly. The optimization solver manages trains at the microscopic level of block sections and at a precision of seconds. The solver outcome is a detailed conflict-free train schedule, being able to avoid deadlock situations and to minimize train delays. The proposed algorithmic framework starts from a good initial solution for the train scheduling problem with fixed routes, obtained via a truncated branch-and-bound algorithm. Variable neighbourhood search or tabu search algorithms are then applied to improve the solution by re-routing some trains. The neighbourhood of a solution is characterized by the set of candidate trains to be re-routed and the available routes. Computational experiments are performed on railway networks from different countries and various sources of disturbance. The new algorithms often outperform a state-of-the-art tabu search algorithm and a commercial solver in terms of reduced computation times and/or train delays.     

Relocation problems of maximizing new capacities under a common due date

Given a set of h buildings to be torn down and rebuilt, each building B_i , demands n_i units of temporary vacancies for reconstruction (i.e. the reconstruction of B_i can be started only if there are at least n_i temporary vacancies available) and returns a_i units of vacancies when it is rebuilt. The reconstruction time of each building is assumed to be unitary. Under the initial provision of V _o units of vacancies and a specified due date d, Σ_BiεSa _i , where S is a feasible sequence such that |S| ≤ d, is the objective function to be maximized. We show that the problem is NP-complete. Based on a dominance heuristics, we further propose a branch-and-bound algorithm. Experimental results are included to elucidate the effectiveness of our algorithm. Two further restricted versions are also polynomially solvable.     

Minimization of squared deviation of completion times about a common due date

We discuss a non-preemptive single-machine job sequencing problem where the objective is to minimize the sum of squared deviation of completion times of jobs from a common due date. There are three versions of the problem—tightly restricted, restricted and unrestricted. Separate dynamic programming formulations have already been suggested for each of these versions, but no unified approach is available. We have proposed a pseudo-polynomial DP solution and a polynomial heuristic for general instance. Computational results show that tightly restricted instances of up to 600 jobs can be solved in less than 6 s. General instances of up to 80 jobs take less than 2 s.Statement of scope and purposeIn this paper, we have considered an NP-complete single-machine scheduling problem arising in JIT environment, a field of great importance in manufacturing industry. The objective of the problem is to schedule a set of given jobs to minimize the sum of squared deviation of their completion times from a common due date. This paper presents a number of precedence rules, a polynomial heuristic and more importantly a unified pseudo-polynomial dynamic programming formulation. Empirical results show that the dynamic programming formulation performs better than the existing approaches.     

Adaptive data reduction with neighbourhood search approach in coordinate measurement of planar surfaces

The computational tasks required in the coordinate metrology of manufactured surfaces including Point Measurement Planning (PMP), Substitute Geometry Estimation (SGE), and Deviation Zone Evaluation (DZE) are typically conducted sequentially. This paper represents a methodology to integrate PMP, SGE, and DZE in order to reduce the inherent sources of computational uncertainties in coordinate measurement of planar surfaces. The methodology is developed based on a closed-loop of three tasks, where the results of SGE and DZE are used to properly revise the set of sample points. The goal of this study is to find a PMP approach that uses a minimal number of sampled points to represent the inspected surface efficiently. Several different sampling strategies are presented and are employed for the inspection of the manufactured surfaces with various patterns of distribution of geometric deviations. A comprehensive experimental study is conducted and statistically analyzed to detect the most reliable sampling strategy to be used as the PMP engine of the loop. It is shown that the developed methodology effectively finds the minimum deviation zone of the surfaces using a small number of sample points. The adaptive computational coordinate metrology method developed in this work can potentially be utilized in the inspection of other geometric features and freeform surfaces.     

A variable neighborhood search based approach for uncapacitated multilevel lot-sizing problems

In this paper, an effective approach based on the variable neighborhood search (VNS) algorithm is presented to solve the uncapacitated multilevel lot-sizing (MLLS) problems with component commonality and multiple end-items. A neighborhood structure for the MLLS problem is defined, and two kinds of solution move policies, i.e., move at first improvement (MAFI) and move at best improvement (MABI), are used in the algorithm. A new rule called Setup shifting is developed to conduct a more efficient neighborhood search for the MLLS problems. Computational studies are carried out on two sets of benchmark problems. The experimental results show that the VNS algorithm is capable of solving MLLS problems with good optimality and high computational efficiency as well, outperforming most of the existing algorithms in comparison.     

The double traveling salesman problem with multiple stacks: A variable neighborhood search approach

The double traveling salesman problem with multiple stacks (DTSPMS) is a vehicle routing problem that consists on finding the minimum total length tours in two separated networks, one for pickups and one for deliveries. A set of orders is given, each one consisting of a pickup location and a delivery location, and it is required to send an item from the former location to the latter one. Repacking is not allowed, but collected items can be packed in several rows in such a way that each row must obey the LIFO principle. In this paper, a variable neighborhood search approach using four new neighborhood structures is presented to solve the problem.     

A neural network to enhance local search in the permutation flowshop

This paper considers the n-job, m-machine permutation flowshop with the objective of minimizing the mean flowtime. Initial sequences that are structured to enhance the performance of local search techniques are constructed from job rankings delivered by a trained neural network. The network's training is done by using data collected from optimal sequences obtained from solved examples of flowshop problems. Once trained, the neural network provides rankable measures that can be used to construct a sequence in which jobs are located as close as possible to the positions they would occupy in an optimal sequence. The contribution of these ‘neural’ sequences in improving the performance of some common local search techniques, such as adjacent pairwise interchange and tabu search, is examined. Tests using initial sequences generated by different heuristics show that the sequences suggested by the neural networks are more effective in directing neighborhood search methods to lower local optima.     

A cooperative dispatching approach for minimizing mean tardiness in a dynamic flowshop

Cooperative Dispatching is a real-time scheduling methodology, which consults downstream machines before making a job dispatching decision on any given machine. This paper proposes such an approach for minimizing the mean tardiness in a dynamic flowshop where new jobs arrive continuously, at random points in time, throughout the production cycle. Cooperative Dispatching is based on the idea that individual machines act self-interestedly, with the objective of optimizing their local performance criteria. A consulted machine attempts to influence upstream dispatching decisions in a manner that promotes its ability to minimize its total local tardiness. A machine's influence in the dispatching decision depends on current congestion and due-date tightness levels in the shop. A multiple regression model is proposed to help determine the weight a consulted machine's preferences will carry in the dispatching decision. Conflicting demands from the different machines are resolved by a minimum regret decision procedure, which aims to minimize the aggregate deviation from the consulted machines' preferences. The winning candidate that ultimately emerges from this procedure is the job that is dispatched. A comparative analysis to evaluate the performance of cooperative dispatching, compared to six other dispatching rules that are commonly favoured for tardiness-based criteria, is performed by means of simulation, using randomly generated test problems. Computational results indicate that Cooperative Dispatching outperforms the other dispatching rules, across a broad range of flowshop congestion and due-date tightness levels.     

Assessing the changing flowering date of the common lilac in North America: a random coefficient model approach

A data set consisting of Volunteered geographical information (VGI) and data provided by expert researchers monitoring the first bloom dates of lilacs from 1956 to 2003 is used to investigate changes in the onset of the North American spring. It is argued that care must be taken when analysing data of this kind, with particular focus on the issues of lack of experimental design, and Simpson’s paradox. Approaches used to overcome this issue make use of random coefficient modelling, and bootstrapping approaches. Once the suggested methods have been employed, a gradual advance in the onset of spring is suggested by the results of the analysis. A key lesson learned is that the appropriateness of the model calibration technique used given the process of data collection needs careful consideration.     

Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date

This paper considers a scheduling problem for parallel burn-in ovens in the semiconductor manufacturing industry. An oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs. We suggest three decomposition heuristics. The first heuristic applies the exact algorithm due to Emmons and Hall (for the nonbatching problem) in order to assign the jobs to separate early and tardy job sets for each of the parallel burn-in ovens. Then, we use job sequencing rules and dynamic programming in order to form batches for the early and tardy job sets and sequence them optimally. The second proposed heuristic is based on genetic algorithms. We use a genetic algorithm in order to assign jobs to each single burn-in oven. Then, after forming early and tardy job sets for each oven we apply again sequencing rules and dynamic programming techniques to the early and tardy jobs sets on each single machine in order to form batches. The third heuristic assigns jobs to the m early job sets and m tardy jobs sets in case of m burn-in ovens in parallel via a genetic algorithm and applies again dynamic programming and sequencing rules. We report on computational experiments based on generated test data and compare the results of the heuristics with known exact solution for small size test instances obtained from a branch and bound scheme.     

A parallel variable neighborhood search approach for the obnoxious p‐median problem

The obnoxious p‐median problem consists of selecting p locations, considered facilities, in a way that the sum of the distances from each nonfacility location, called customers, to its nearest facility is maximized. This is an ‐hard problem that can be formulated as an integer linear program. In this paper, we propose the application of a variable neighborhood search (VNS) method to effectively tackle this problem. First, we develop new and fast local search procedures to be integrated into the basic VNS methodology. Then, some parameters of the algorithm are tuned in order to improve its performance. The best VNS variant is parallelized and compared with the best previous methods, namely branch and cut, tabu search, and GRASP over a wide set of instances. Experimental results show that the proposed VNS outperforms previous methods in the state of the art. This fact is finally confirmed by conducting nonparametric statistical tests.