Minimisation of total tardiness for identical parallel machine scheduling using genetic algorithm

In recent years research on parallel machine scheduling has received an increased attention. This paper considers minimisation of total tardiness for scheduling of n jobs on a set of m parallel machines. A spread-sheet-based genetic algorithm (GA) approach is proposed for the problem. The proposed approach is a domain-independent general purpose approach, which has been effectively used to solve this class of problem. The performance of GA is compared with branch and bound and particle swarm optimisation approaches. Two set of problems having 20 and 25 jobs with number of parallel machines equal to 2, 4, 6, 8 and 10 are solved with the proposed approach. Each combination of number of jobs and machines consists of 125 benchmark problems; thus a total for 2250 problems are solved. The results obtained by the proposed approach are comparable with two earlier approaches. It is also demonstrated that a simple GA can be used to produce results that are comparable with problem-specific approach. The proposed approach can also be used to optimise any objective function without changing the basic GA routine.     

Genetic algorithm for job-shop scheduling with machine unavailability and breakdowns

The job-shop scheduling problem (JSSP) is considered to be one of the most complex combinatorial optimisation problems. In our previous attempt, we hybridised a Genetic Algorithm (GA) with a local search technique to solve JSSPs. In this research, we propose an improved local search technique, Shifted Gap-Reduction (SGR), which improves the performance of GAs when solving relatively difficult test problems. We also modify the new algorithm for JSSPs with machine unavailability and breakdowns. We consider two scenarios of machine unavailability. First, where the unavailability information is available in advance (predictive) and, secondly, where the information is known after a real breakdown (reactive). We show that the revised schedule is mostly able to recover if the interruptions occur during the early stages of the schedules.     

Mixed Self-adapting GA Optimal Scheduling Algorithm for a Multiple Resource Job-shop

With an aim at the job-shop scheduling problem of multiple resource constraints, this paper presents mixed self-adapting Genetic Algorithm （ GA ） , and establishes a job-shop optimal scheduling model of multiple resource constraints based on the effect of priority scheduling rules in the heuristic algorithm upon the scheduling target. New coding regulations or rules are designed. The sinusoidal function is adopted as the self-adapting factor, thus making cross probability and variable probability automatically change with group adaptability in such a way as to overcome the shortcoming in the heuristic algorithm and common GA, so that the operation efficiency is improved. The results from real example simulation and comparison with other algorithms indicate that the mixed self-adapting GA algorithm can well solve the job-shop optimal scheduling problem under the constraints of various kinds of production resources such as machine-tools and cutting tools.     

Applied column generation-based approach to solve supply chain scheduling problems

More and more enterprises have chosen to adopt a made-to-order business model in order to satisfy diverse and rapidly changing customer demand. In such a business model, enterprises are devoted to reducing inventory levels in order to upgrade the competitiveness of the products. However, reductions in inventory levels and short lead times force the operation between production and distribution to cooperate closely, thus increasing the practicability of integrating the production and distribution stages. The complexity of supply chain scheduling problems (integrated production and distribution scheduling) is known to be NP-hard. To address the issues above, an efficient algorithm to solve the supply chain scheduling problem is needed. This paper studies a supply chain scheduling problem in which the production stage is modelled by an identical parallel machine scheduling problem and the distribution stage is modelled by a capacitated vehicle routing problem. Given a set of customer orders (jobs), the problem is to find a supply chain schedule such that the weighted summation of total job weighted completion time and total job delivering cost are minimised. The studied problem was first formulated as an integer programme and then solved by using column generation techniques in conjunction with a branch-and-bound approach to optimality. The results of the computational experiments indicate that the proposed approach can solve the test problems to optimality. Moreover, the average gap between the optimal solutions and the lower bounds is no more than 1.32% for these test problems.     

基于密度峰值聚类的VRPTW问题研究

提出一种密度峰值聚类 (density peak clustering, DPC)与遗传算法(genetic algorithm, GA)相结合的新型混合算法(density peak clustering with genetic algorithm, DGA),求解带时间窗的车辆路径问题。首先应用DPC对客户进行聚类以缩减问题规模,再将聚类后的客户用GA进行线路优化。结果表明：DGA在9个数据集上的平均值比模拟退火(simulated annealing, SA)和禁忌搜索(Tabu)分别提高了13.41%和4.7%,单个数据集最大提高了26.4%。这证明了该算法是求解车辆调度问题的高效算法。     

Parallel flowshop scheduling using Tabu search

Production scheduling problems in manufacturing systems with parallel machine flowshops are discussed. A mathematical programming model for combined part assignment and job scheduling is developed. The objective of solving the scheduling problem is to minimize a weighted sum of production cost and the cost incurred from late product delivery. The solution of the model is NP-hard. To solve the problem efficiently, a heuristic algorithm combining Tabu search and Johnson's method was proposed. Several numerical examples are presented to illustrate the developed model and the algorithm. Computational results from these example problems are very encouraging.     

A two-stage AIS approach for grid scheduling problems

Grid workflow scheduling problem has been a research focus in grid computing in recent years. Various deterministic or meta-heuristic scheduling approaches have been proposed to solve this NP-complete problem. A perusal of published papers on the artificial immune system (AIS) reveals that most researchers use the clonal selection of B cells during the evolving processes and the affinity function of B cells to solve various optimisation problems. This research takes a different approach to the subject – firstly by applying a modified algorithm (Hu, T.C., 1961. Parallel sequencing and assembly line problem. Operations Research, 9 (6), 841–848) to sequence the job and this sequence is applied for further application. Secondly, the derived sequence is then used for machine allocations using the AIS approach. The proposed AIS apply B cells to reduce the antigens and then combining T helper cells and T suppressor cells to solve the grid scheduling problems. Our proposed methodology differs from other earlier approaches as follows: 1. A two-stage approach is applied using a fixed sequence derived from heuristic to allocate machine. 2. AIS apply B cells as bases and then T cells are employed next. T helper cells are used to help improve the solution and then T suppressor cells are generated to increase the diversity of the population. A new formula is proposed to calculate the affinity of the antibody with the antigen. The total difference of completion time of each job is applied instead of the difference of makespan of the schedule. This new AIS method can supplement the flaw of genetic algorithms (GA) using fitness as the basis and a new lifespan which will keep good diversified chromosomes within the population to extend the searching spaces. The experimental tests show that this novel AIS method is very effective when compared with other meta-heuristics such as GA, simulated annealing (SA), and ant colony optimisation (ACO).     

A variable neighbourhood search algorithm for the flexible job-shop scheduling problem

The flexible job-shop scheduling problem (FJSP) is a generalisation of the classical job-shop scheduling problem which allows an operation of each job to be executed by any machine out of a set of available machines. FJSP consists of two sub-problems which are assigning each operation to a machine out of a set of capable machines (routing sub-problem) and sequencing the assigned operations on the machines (sequencing sub-problem). This paper proposes a variable neighbourhood search (VNS) algorithm that solves the FJSP to minimise makespan. In the process of the presented algorithm, various neighbourhood structures related to assignment and sequencing problems are used for generating neighbouring solutions. To compare our algorithm with previous ones, an extensive computational study on 181 benchmark problems has been conducted. The results obtained from the presented algorithm are quite comparable to those obtained by the best-known algorithms for FJSP.     

供应链中生产和运输协调调度问题初探

提出了解决供应链中生产和航空运输协调调度问题的理论框架.基于对生产调度和航空运输调度彼此制约关系的分析,协调调度问题被分解为两个子调度问题.建立了航空运输子调度问题的整数规划模型,并证明了该问题为NP完全问题.提出了基于倒排调度方法(backward scheduling method)的调度算法解单机生产调度子问题.     

基于遗传算法的平行流水作业计划方法

提出了平行机作业方式和流水作业方式的综合的作业方式,属于NP难问题.应用网络理论构造了平行流水作业的非连接图模型,可实现全局随机寻优的实基因编码遗传算法求解平行流水作业计划问题.选取各种规模的10余个标准算例,以加工流程时间为目标函数进行仿真.对每个算例进行10次随机计算,所得最优值与平均值差异率小于1.8%.对于reC39等大规模问题,10次随机计算的平均花费时间少于260s.     

Scenario-based heuristic to two-stage stochastic program for the parallel machine ScheLoc problem

Scheduling-Location (ScheLoc) problem is a new and interesting topic in manufacturing, considering location and scheduling decisions simultaneously. Most existing works focus on the deterministic problems. In practice, however, job-processing times are usually uncertain due to some factors. This paper investigates the stochastic parallel machine ScheLoc problem to minimise the weighted sum of the location cost and the expectation of the total completion time. A two-stage stochastic programming formulation is proposed, then the sample average approximation (SAA) method is adapted to solve the small-size problems. To efficiently address the large-scale problems, a genetic algorithm (GA) and a scenario-based heuristic are designed. Numerical experiments on 450 instances are conducted. Computational results show that the scenario-based heuristic outperforms SAA method and GA in terms of solution quality and computational time.     

A re-entrant hybrid flow shop scheduling problem with machine eligibility constraints

A production scheduling problem originating from a real rotor workshop is addressed in the paper. Given its specific characteristics, the problem is formulated as a re-entrant hybrid flow shop scheduling problem with machine eligibility constraints. A mixed integer linear programming model of the problem is provided and solved by the Cplex solver. In order to solve larger sized problems, a discrete differential evolution (DDE) algorithm with a modified crossover operator is proposed. More importantly, a new decoder addressing the machine eligibility constraints is developed and embedded to the algorithm. To validate the performance of the proposed DDE algorithm, various test problems are examined. The efficiency of the proposed algorithm is compared with two other algorithms modified from the existing ones in the literatures. A one-way ANOVA analysis and a sensitivity analysis are applied to intensify the superiority of the new decoder. Tightness of due dates and different levels of scarcity of machines subject to machine eligibility restrictions are discussed in the sensitivity analysis. The results indicate the pre-eminence of the new decoder and the proposed DDE algorithm.     

Energy-Aware Production Scheduling in Flow Shop and Job Shop Environments Using a Multi-Objective Genetic Algorithm

Abstract

The energy-aware scheduling problem is a multi-objective optimization problem where the main goal is to achieve energy savings without affecting productivity in a manufacturing system. In this work, we present an approach for energy-aware flow shop scheduling problem and energy-aware job shop scheduling problem considering the process speed as the main energy-related decision variable. This approach allows one to set the appropriate process speed for every considered operation in the corresponding machine. When the speed is high, the processing time is short but the energy demand increases, and vice versa. Therefore, two objectives are worked together: a production objective, paired with an energy efficiency objective. A generic elitist multi-objective genetic algorithm was implemented to solve both problems. Results from a simple comparative design of experiments and a nonparametric test show that it is possible to smooth the energy demand profile and obtain reductions that average 19.8% in energy consumption. This helps to reduce peak loads and drops on applied energy sources demand, stabilizing the conversion units operational efficiency across the entire operational time with a minimum effect on the production maximum completion time (makespan).     

A simulation-based multi-objective genetic algorithm (SMOGA) procedure for BOT network design problem

Solving optimization problems with multiple objectives under uncertainty is generally a very difficult task. Evolutionary algorithms, particularly genetic algorithms, have shown to be effective in solving this type of complex problems. In this paper, we develop a simulation-based multi-objective genetic algorithm (SMOGA) procedure to solve the build-operate-transfer (BOT) network design problem with multiple objectives under demand uncertainty. The SMOGA procedure integrates stochastic simulation, a traffic assignment algorithm, a distance-based method, and a genetic algorithm (GA) to solve a multi-objective BOT network design problem formulated as a stochastic bi-level mathematical program. To demonstrate the feasibility of SMOGA procedure, we solve two mean-variance models for determining the optimal toll and capacity in a BOT roadway project subject to demand uncertainty. Using the inter-city expressway in the Pearl River Delta Region of South China as a case study, numerical results show that the SMOGA procedure is robust in generating ‘good’ non-dominated solutions with respect to a number of parameters used in the GA, and performs better than the weighted-sum method in terms of the quality of non-dominated solutions.     

Scheduling trucks in container terminals using a genetic algorithm

Trucks are the most popular transport equipment in most mega-terminals, and scheduling them to minimize makespan is a challenge that this article addresses and attempts to resolve. Specifically, the problem of scheduling a fleet of trucks to perform a set of transportation jobs with sequence-dependent processing times and different ready times is investigated, and the use of a genetic algorithm (GA) to address the scheduling problem is proposed. The scheduling problem is formulated as a mixed integer program. It is noted that the scheduling problem is NP-hard and the computational effort required to solve even small-scale test problems is prohibitively large. A crossover scheme has been developed for the proposed GA. Computational experiments are carried out to compare the performance of the proposed GA with that of GAs using six popular crossover schemes. Computational results show that the proposed GA performs best, with its solutions on average 4.05% better than the best solutions found by the other six GAs.     

Decision-making on multi-mould maintenance in production scheduling

The reliability of a critical tool like a mould on a machine affects the productivity seriously in many manufacturing firms. In fact, its breakdown frequency is even higher than machines. The decision-making on when mould maintenance should be started become a challenging issue. In the previous study, the mould maintenance plans were integrated with the traditional production schedules in a plastics production system. It was proven that considering machine and mould maintenance in production scheduling could improve the overall reliability and productivity of the production system. However, the previous model assumed that each job contained single operation. It is not workable in other manufacturing systems such as die stamping which may contain multiple operations with multiple moulds in each job. Thus, this study models a new problem for multi-mould production-maintenance scheduling. A genetic algorithm approach is applied to minimise the makespan of all jobs in 10 hypothetical problem sets. A joint scheduling (JS) approach is proposed to decide the start times of maintenance activities during scheduling. The numerical result shows that the JS approach has a good performance in the new problem and it is sensitive to the characteristic of the setup time defined.     

A new approach to the cell formation problem with alternative processing routes and operation sequence

Cellular manufacturing (CM) is an important application of group technology in manufacturing systems. One of the crucial steps in the design of CM is the identification of part families and manufacturing cells. This problem is referred to as cell formation problem (CFP) in the literature. In this article, a solution approach is proposed for CFP, which considers many parameters such as machine requirement, sequence of operations, alternative processing routes, processing time, production volume, budget limitation, cost of machines, etc. Due to the NP-hardness of CFP, it cannot be efficiently solved for medium- to large-sized problems. Thus, a genetic algorithm (GA) is proposed to solve the formulated model. Comparison of the results obtained from the proposed GA to the globally optimum solutions obtained by Lingo Software and those reported in the literature reveals the effectiveness and efficiency of the proposed approach.     

Optimisation of integrated process planning and scheduling using a particle swarm optimisation approach

Traditionally, process planning and scheduling are two independent essential functions in a job shop manufacturing environment. In this paper, a unified representation model for integrated process planning and scheduling (IPPS) has been developed. Based on this model, a modern evolutionary algorithm, i.e. the particle swarm optimisation (PSO) algorithm has been employed to optimise the IPPS problem. To explore the search space comprehensively, and to avoid being trapped into local optima, the PSO algorithm has been enhanced with new operators to improve its performance and different criteria, such as makespan, total job tardiness and balanced level of machine utilisation, have been used to evaluate the job performance. To improve the flexibility and agility, a re-planning method has been developed to address the conditions of machine breakdown and new order arrival. Case studies have been used to a verify the performance and efficiency of the modified PSO algorithm under different criteria. A comparison has been made between the result of the modified PSO algorithm and those of the genetic algorithm (GA) and the simulated annealing (SA) algorithm respectively, and different characteristics of the three algorithms are indicated. Case studies show that the developed PSO can generate satisfactory results in optimising the IPPS problem.     

Single machine scheduling problem with stochastic sequence-dependent setup times

In this study, we consider stochastic single machine scheduling problem. We assume that setup times are both sequence dependent and uncertain while processing times and due dates are deterministic. In the literature, most of the studies consider the uncertainty on processing times or due dates. However, in the real-world applications (i.e. plastic moulding industry, appliance assembly, etc.), it is common to see varying setup times due to labour or setup tools availability. In order to cover this fact in machine scheduling, we set our objective as to minimise the total expected tardiness under uncertain sequence-dependent setup times. For the solution of this NP-hard problem, several heuristics and some dynamic programming algorithms have been developed. However, none of these approaches provide an exact solution for the problem. In this study, a two-stage stochastic-programming method is utilised for the optimal solution of the problem. In addition, a Genetic Algorithm approach is proposed to solve the large-size problems approximately. Finally, the results of the stochastic approach are compared with the deterministic one to demonstrate the value of the stochastic solution.