A hybrid genetic algorithm and tabu search for a multi-objective dynamic job shop scheduling problem

In most real manufacturing environments, schedules are usually inevitable with the presence of various unexpected disruptions. In this paper, a rescheduling method based on the hybrid genetic algorithm and tabu search is introduced to address the dynamic job shop scheduling problem with random job arrivals and machine breakdowns. Because the real-time events are difficult to express and take into account in the mathematical model, a simulator is proposed to tackle the complexity of the problem. A hybrid policy is selected to deal with the dynamic feature of the problem. Two objectives, which are the schedule efficiency and the schedule stability, are considered simultaneously to improve the robustness and the performance of the schedule system. Numerical experiments have been designed to test and evaluate the performance of the proposed method. This proposed method has been compared with some common dispatching rules and meta-heuristic algorithms that have been widely used in the literature. The experimental results illustrate that the proposed method is very effective in various shop-floor conditions.     

Integrated optimisation on flow-shop production with cutting stock

This paper addresses the integrated scheduling optimisation on flow-shop production with one-dimensional cutting stock in make-to-order environments. The upstream cutting-stock process provides the items for the downstream production, while the flow-shop production can be executed only when the required items are released. The efficient schedules on cutting plan and the production sequence should be determined in a coordinated manner to improve the overall efficiency. This study aims to find an integrated schedule to minimise the makespan of the entire manufacturing process. We develop a hybrid algorithm by integrating a local search method and some efficient strategies under the nested partitions framework. Numerical experiments show that the proposed approach is capable of achieving high-quality solutions within a reasonable time.     

Variable neighborhood search for the pharmacy duty scheduling problem

In this paper, we study on the Pharmacy Duty Scheduling (PDS) problem, where a subset of pharmacies should be on duty on national holidays, at weekends and at nights in order to be able to satisfy the emergency drug needs of the society. PDS problem is a multi-period p-median problem with special side constraints and it is an NP-Hard problem. We propose four Variable Neighborhood Search (VNS) heuristics. The first one is the basic version, BVNS. The latter two, Variable Neighborhood Decomposition Search (VNDS) and Variable Neighborhood Restricted Search (VNRS), aim to obtain better results in less computing time by decomposing or restricting the search space. The last one, Reduced VNS (RVNS), is for obtaining good initial solutions rapidly for BVNS, VNDS and VNRS. We test BVNS, VNRS and VNDS heuristics on randomly generated instances and report the computational test results. We also use VNS heuristics on real data for the pharmacies in central İzmir and obtain significant improvements.     

Combined empty and loaded train scheduling for dedicated freight railway corridors

The efficient utilization of expensive rolling-stock has become imperative for all railroads. In this paper, we study the combined empty and loaded train-scheduling problem for the upcoming dedicated freight corridors in India. Existing optimization models either do not consider the simultaneous optimization of the loaded and empty flows or are not solvable for large railroads. Our model is the first of its kind to incorporate link capacity constraints in an IP formulation for this operational level problem. A simulated annealing algorithm hybridized with a constructive heuristic is proposed as the solution method. The computational experiments show that the proposed heuristic performs well both in terms of runtime and solution quality.     

Two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times

Two-machine no-wait flowshop scheduling problems in which the processing time of a job is a function of its position in the sequence and its resource allocation are considered in the study. The primary objective is to find the optimal sequence of jobs and the optimal resource allocation separately. Here we propose two separate models: minimizing a cost function of makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function of makespan, total waiting time, total absolute differences in waiting times and total resource cost. Since each model is strongly NP-hard, we solve both models by breaking them down to two sub-problems, the optimal resource allocation problem for any job sequence and the optimal sequence problem with its optimal resource allocation. Specially, we transform the second sub-problem into the minimum of the bipartite graph optimal matching problem (NP-hard), and solve it by using the classic KM (Kuhn–Munkres) algorithm. The solutions of the two sub-problems demonstrate that the target problems remain polynomial solvable under the proposed model.     

Path-relinking Tabu search for the multi-objective flexible job shop scheduling problem

The multi-objective flexible job shop scheduling problem is solved using a novel path-relinking algorithm based on the state-of-the-art Tabu search algorithm with back-jump tracking. A routing solution is identified by problem-specific neighborhood search, and is then further refined by the Tabu search algorithm with back-jump tracking for a sequencing decision. The resultant solution is used to maintain the medium-term memory where the best solutions are stored. A path-relinking heuristics is designed to generate diverse solutions in the most promising areas. An improved version of the algorithm is then developed by incorporating an effective dimension-oriented intensification search to find solutions that are located near extreme solutions. The proposed algorithms are tested on benchmark instances and its experimental performance is compared with that of algorithms in the literature. Comparison results show that the proposed algorithms are competitive in terms of its computation performance and solution quality.     

Optimal operation of cogeneration system coordinated by aggregator for providing the demand and supply regulation capacity

Recent growth of renewable energy generations with natural variability, such as photovoltaic generation and wind turbine generation, would make the demand and supply control in a whole power system more difficult, and therefore, alternatives for demand and supply regulation resources would be required. The authors focus on cogeneration system (CGS) as one of regulation resources. In order to procure adequate volume of regulation capability, an aggregator coordinates a number of CGSs efficiently and flexibly considering the wide variety of electricity/thermal demands of CGS owners. This paper proposes a novel optimal operation strategy of CGS coordinated by the aggregator considering the energy balance and operation cost of individual CGS owner. This paper also demonstrates the availability of CGSs for regulation capability by numerical case studies in which the actual consumption profile is employed.     

An Ant Colony Algorithm (ACA) for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs

This paper concerns with the Job Shop Scheduling Problem (JSSP) considering the transportation times of the jobs from one machine to another. The goal of a basic JSSP is to determine starting and ending times for each job in which the objective function can be optimized. In here, several Automated Guided Vehicles (AGVs) have been employed to transfer the jobs between machines and warehouse located at the production environment. Unlike the advantages of implemented automatic transportation system, if they are not controlled along the routes, it is possible that the production system encounters breakdown. Therefore, the Conflict-Free Routing Problem (CFRP) for AGVs is considered as well as the basic JSSP. Hence, we proposed a mathematical model which is composed of JSSP and CFRP, simultaneously and since the problem under study is NP-hard, a two stage Ant Colony Algorithm (ACA) is also proposed. The objective function is to minimize the total completion time (make-span). Eventually, in order to show the model and algorithm’s efficiency, the computational results of 13 test problems and sensitivity analysis are exhibited. The obtained results show that ACA is an efficient meta-heuristic for this problem, especially for the large-sized problems. In addition, the optimal number of both AGVs and rail-ways in the production environment is determined by economic analysis.     

Resource-constrained scheduling with optional recycling operations

This paper introduces a scheduling problem with a variant of resource constraint that stems from a relocation project. We also propose the concept of optional recycling operations, in which recycling operations are separated from the processing of jobs and recycling operations are exercised only when necessary. An integer program is proposed to formulate the problem and facilitate complexity classification. We propose a pseudo-polynomial time dynamic program, and then classify the complexity status of several restricted cases.     

An improved scatter search algorithm for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times

In this paper, a scatter search algorithm with improved component modules is proposed to solve the single machine total weighted tardiness problem with sequence-dependent setup times. For diversification generation module, both random strategy based heuristics and construction heuristic are adopted to generate the diversified population. For improvement module, variable neighborhood search based local searches are embedded into the algorithm to improve the trial solutions and the combined solutions. For reference set update module, the number of edges by which the two solutions differ from each other is counted to measure the diversification value between two solutions. We also propose a new strategy in which the length of the reference set could be adjusted adaptively to balance the computing time and solving ability. In addition, a discrete differential evolution operator is proposed with another two operators constitute the combination module to generate the new trial solutions with the solutions in the subsets. The proposed algorithm is tested on the 120 benchmark instances from the literature. Computational results indicate that the average relative percentage deviations of the improved algorithm from the ACO_AP, DPSO, DDE and GVNS are −5.16%, −3.33%, −1.81% and −0.08%, respectively. Comparing with the state-of-the-art and exact algorithms, the proposed algorithm can obtain 78 optimal solutions out of 120 instances within a reasonable computational time.