More MILP models for hybrid flow shop scheduling problem and its extended problems

With the rapid development of computer technology and related softwares for mathematical models, mathematical modelling of scheduling problems is receiving growing attention from researchers. In this work, the hybrid flow shop scheduling problem with unrelated parallel machines (HFSP-UPM) with the objective aimed to minimise the makespan is studied. According to the characteristics of the HFSP-UPM, eight mixed integer linear programming (MILP) models are formulated in order to obtain optimal solutions based on different modelling ideas. Then, these models are extended to solve HFSP-UPM with sequence-dependent setup times (HFSP-UPM-SDST), no-wait HFSP-UPM (HFSP-UPM-NW) and HFSP-UPM with blocking (HFSP-UPM-B). All the proposed models and the existing model are detailedly compared and evaluated under three aspects namely modelling process, size complexity and computational complexity. Numerical experiments show that MILP models dependent on diverse modelling ideas perform very differently. The model developed based on stage precedence is the best one and should be given preference in future applications. In addition, the proposed models of HFSP-UPM-NW and HFSP-UPM-B improve several best known solutions for the test instances in the existing literature.     

Mathematical modelling and a meta-heuristic for flexible job shop scheduling

This study develops new solution methodologies for the flexible job shop scheduling problem (F-JSSP). As a first step towards dealing with this complex problem, mathematical modellings have been used; two novel effective position- and sequence-based mixed integer linear programming (MILP) models have been developed to fully characterise operations of the shop floor. The developed MILP models are capable of solving both partially and totally F-JSSPs. Size complexities, solution effectiveness and computational efficiencies of the developed MILPs are numerically explored and comprehensively compared vis-à-vis the makespan optimisation criterion. The acquired results demonstrate that the proposed MILPs, by virtue of its structural efficiencies, outperform the state-of-the-art MILPs in literature. The F-JSSP is strongly NP-hard; hence, it renders even the developed enhanced MILPs inefficient in generating schedules with the desired quality for industrial scale problems. Thus, a meta-heuristic that is a hybrid of Artificial Immune and Simulated Annealing (AISA) Algorithms has been proposed and developed for larger instances of the F-JSSP. Optimality gap is measured through comparison of AISA’s suboptimal solutions with its MILP exact optimal counterparts obtained for small- to medium-size benchmarks of F-JSSP. The AISA’s results were examined further by comparing them with seven of the best-performing meta-heuristics applied to the same benchmark. The performed comparative analysis demonstrated the superiority of the developed AISA algorithm. An industrial problem in a mould- and die-making shop was used for verification.     

Minimising interference for scheduling two parallel machines with a single server

In this paper, we consider the problem of scheduling a set of jobs on two parallel machines with set-up times. The set-up has to be performed by a single server. The objective is to minimise the forced idle time. The problem of minimising the forced idle time (interference problem) is known to be unary NP-hard for the case of two machines and equal set-up and arbitrary processing times. We propose a mixed integer linear programming model, which describes a special class of schedules where the jobs from a list are scheduled alternatively on the machines, and a heuristic algorithm is tested on instances with up to 100,000 jobs. The computational results indicate that the algorithm has an excellent performance even for very large instances, where mostly an optimal solution is obtained within a very small computational time.     

包装废弃物回收车辆路径问题的改进遗传算法

目的采用优化传统遗传算法(GA)研究包装废弃物回收车辆路径问题(VRP)的性能。方法提出改进遗传算法(IGA)。首先,设计基于贪婪算法的初始种群生成算子,提高初始种群质量;其次,设计根据适应度值大小、进化代数等自适应调整的交叉和变异概率;然后,设计最大保留交叉算子,保证种群的多样性;最后,对企业实例和标准算例进行仿真测试。结果采用IGA算法、蚁群算法(ACO)能求得算例最优解,且IGA算法运行速度快于ACO算法,分支界定算法(BBM)、传统GA算法无法求得算例最优解。结论与BBM算法、传统GA算法和ACO算法相比,IGA算法求解包装废弃物回收VRP问题的整体性能更优。     

Scenario-based approach for flexible resource loading under uncertainty

Order acceptance decisions in manufacture-to-order environments are often made based on incomplete or uncertain information. To quote reliable due dates in order processing, manage resource capacity adequately and take into account uncertainty, the paper presents and analyses models and tools for more robust resource loading. We refer to the problem as flexible resource loading under uncertainty. We propose a scenario-based solution approach that can deal with a wide range of uncertainty types. The approach is based on an MILP to find a plan with minimum expected costs over all relevant scenarios. To solve this MILP, we propose an exact branch-and-price algorithm. Further, we propose a much faster improvement heuristic based on an LP (linear programming) approximation. A disadvantage of the scenario-based MILP, is that a large number of scenarios may make the model intractable. We therefore propose an approximate approach that uses the aforementioned solution techniques and only a sample of all scenarios. Computational experiments show that, especially for instances with sufficient slack, solutions obtained with deterministic techniques that only use the expected scenario can be significantly improved with respect to their expected costs (i.e. robustness). We also show that for large instances, our heuristics outperform the exact approach given a maximum computation time as a stopping criterion. Moreover, it turns out that using a small sample of selected scenarios generally yields better results than using all scenarios.     

Improved genetic algorithm for mixed-discrete-continuous design optimization problems

An improved genetic algorithm (IGA) is presented to solve the mixed-discrete-continuous design optimization problems. The IGA approach combines the traditional genetic algorithm with the experimental design method. The experimental design method is incorporated in the crossover operations to systematically select better genes to tailor the crossover operations in order to find the representative chromosomes to be the new potential offspring, so that the IGA approach possesses the merit of global exploration and obtains better solutions. The presented IGA approach is effectively applied to solve one structural and five mechanical engineering problems. The computational results show that the presented IGA approach can obtain better solutions than both the GA-based and the particle-swarm-optimizer-based methods reported recently.     

Scheduling commercial advertisements for television

The problem of scheduling the commercial advertisements in the television industry is investigated. Each advertiser client demands that the multiple airings of the same brand advertisement should be as spaced as possible over a given time period. Moreover, audience rating requests have to be taken into account in the scheduling. This is the first time this hard decision problem is dealt with in the literature. We design two mixed integer linear programming (MILP) models. Two constructive heuristics, local search procedures and simulated annealing (SA) approaches are also proposed. Extensive computational experiments, using several instances of various sizes, are performed. The results show that the proposed MILP model which represents the problem as a network flow obtains a larger number of optimal solutions and the best non-exact procedure is one that uses SA.     

Scheduling flexible manufacturing cells using Tabu Search

Scheduling is an important aspect in the overall control of a flexible manufacturing system. The research presented focuses on production scheduling of jobs within a flexible manufacturing cell (FMC)–one type of flexible manufacturing system. Due to the complexity of the FMC scheduling problem, a 0–1 mixed-integer linear programming (MILP) model is formulated for M machines and N jobs with alternative routings. Although small instances of the problem can be solved optimally with MILP models, a two-stage Tabu Search (TS² ) algorithm that minimises the manufacturing makespan (MS) is proposed to solve medium-to-large-scale problems more efficiently. During Stage I (construction phase), two heuristics are utilised to generate an initial feasible sequence and an initial MS solution. In Stage II (improvement phase), the acquired initial solutions from Stage I are combined with a Tabu Search meta-heuristic procedure that provides improved MS solutions. The TS² algorithm provides tremendous savings in computational time for medium/large-sized multi-machine FMC problems.     

Modelling and a tabu search solution for the slab reallocation problem in the steel industry

This paper considers a slab reallocation problem arising from operations planning in the steel industry. The problem involves reallocating steel slabs to customer orders to improve the utilisation of slabs and the level of customer satisfaction. It can be viewed as an extension of a multiple knapsack problem. We firstly formulate the problem as an integer nonlinear programming (INLP) model. With variable replacement, the INLP model is then transformed into a mixed integer linear programming (MILP) model, which can be solved to optimality by MILP optimisers for very small instances. To obtain satisfactory solutions efficiently for practical-sized instances, a heuristic algorithm based on tabu search (TS) is proposed. The algorithm employs multiple neighbourhoods including swap, insertion and ejection chain in local search, and adopts solution space decomposition to speed up computation. In the ejection chain neighbourhood, a new and more effective search method is also proposed to take advantage of the structural properties of the problem. Computational experiments on real data from an advanced iron and steel company in China show that the algorithm generates very good results within a short time. Based on the model and solution approach, a decision support system has been developed and implemented in the company.     

Global optimization for the three-dimensional open-dimension rectangular packing problem

This article addresses the three-dimensional open-dimension rectangular packing problem (3D-ODRPP), which aims to pack a given set of unequal-size rectangular boxes within an enveloping rectangular space such that the volume of the occupied space is minimized. Even though the studied 3D-ODRPP is NP hard, the development of sophisticated global optimization methods has been stimulated. The mathematical programming formulation for the 3D-ODRPP has evolved into an effective and efficient mixed-integer linear programming (MILP) model. This study proposes an advanced exact scheme yielding a guaranteed global optimal solution given that all the instance data are non-negative rational numbers. The developed MILP retains not only fewer variables but also fewer constraints than the state-of-the-art models. The superior effectiveness and efficiency of the developed scheme are demonstrated with numerical experiments, where two sets of benchmark instances from references, real-world instances and instances with rational data are included.     

Two-machine flow shop problem with unit-time operations and conflict graph

This paper addresses the problem of scheduling, on a two-machine flow shop, a set of unit-time operations subject to the constraints that some conflicting jobs cannot be scheduled simultaneously on different machines. In the context of our study, these conflicts are modelled by general graphs. The problem of minimising the maximum completion time (makespan) is known to be NP-hard in the strong sense. We propose a mixed-integer linear programming (MILP) model. Then, we develop a branch and bound algorithm based on new lower and upper bound procedures. We further provide a computer simulation to measure the performance of the proposed approaches. The computational results show that the branch and bound algorithm outperforms the MILP model and can solve instances of size up to 20,000 jobs.     

智能化遗传算法

针对遗传算法的收敛速度慢、收敛早熟和概率稳定性差等问题提出一种智能化遗传算法(IGA)。首先，建立描述种群进化的统计特征量，为IGA的算法策略提供决策依据。其次，建立种群的自学习算法、种群的自组织算法与遗传算子操作概率的自适应算法，并将这些算法嵌入最优保存简单遗传算法(OMSGA)，从而构成IGA。最后，从理论上对算法收敛性及效率进行了分析。通过遗传算法标准测试函数的仿真结果证明了算法的实用性和有效性。     

Two MILP models for the N × M SDST flowshop sequencing problem

This paper presents the derivation and evaluation of two new MILP models for the SDST flowshop sequencing problem. The first model, TS1, was derived directly from the assignment-problem-based MILP model for the regular flowshop that Stafford modified from the original Wagner three-machine all-integer model. The second model, TS2, combined the properties of model TS1 with the looser constraints approach of Srikar and Ghosh, as modified by Stafford and Tseng (model SG*). Three experiments were used to compare both new models to the SG* model. Both new models were found to use significantly less computation time than the SG* model, especially for problem sizes of 6 or more jobs and 5 or more machines. The TS1 model used significantly less computation time than the TS2 model, making it the current best MILP model in the SDST flowshop literature.     

Flexible job-shop scheduling problems with ‘AND’/‘OR’ precedence constraints

The purpose of this research is to solve flexible job-shop scheduling problems with ‘AND’/‘OR’ precedence constraints in the operations. We first formulate the problem as a Mixed-Integer Linear Program (MILP). The MILP can be used to compute optimal solutions for small-sized problems. We also developed a heuristic algorithm that can obtain a good solution for the problem regardless of its size. Moreover, we have developed a representation and schedule builder that always produces a legal and feasible solution for the problem, and developed genetic and tabu search algorithms based on the proposed schedule builder. The results of the computational experiments show that the developed meta-heuristics are very effective.     

Efficient global optimization for high-dimensional constrained problems by using the Kriging models combined with the partial least squares method

In many engineering optimization problems, the number of function evaluations is often very limited because of the computational cost to run one high-fidelity numerical simulation. Using a classic optimization algorithm, such as a derivative-based algorithm or an evolutionary algorithm, directly on a computational model is not suitable in this case. A common approach to addressing this challenge is to use black-box surrogate modelling techniques. The most popular surrogate-based optimization algorithm is the efficient global optimization (EGO) algorithm, which is an iterative sampling algorithm that adds one (or many) point(s) per iteration. This algorithm is often based on an infill sampling criterion, called expected improvement, which represents a trade-off between promising and uncertain areas. Many studies have shown the efficiency of EGO, particularly when the number of input variables is relatively low. However, its performance on high-dimensional problems is still poor since the Kriging models used are time-consuming to build. To deal with this issue, this article introduces a surrogate-based optimization method that is suited to high-dimensional problems. The method first uses the ‘locating the regional extreme’ criterion, which incorporates minimizing the surrogate model while also maximizing the expected improvement criterion. Then, it replaces the Kriging models by the KPLS(+K) models (Kriging combined with the partial least squares method), which are more suitable for high-dimensional problems. Finally, the proposed approach is validated by a comparison with alternative methods existing in the literature on some analytical functions and on 12-dimensional and 50-dimensional instances of the benchmark automotive problem ‘MOPTA08’.     

Dispatching multi-load AGVs in highly automated seaport container terminals

This paper is concerned with AGV dispatching in seaport container terminals. Special attention is given to multi-load vehicles which can carry more than one container at a time. The characteristics of this complex application environment and the impact on the AGV dispatching problem are analyzed and various solution techniques considered. For practical application within an online logistics control system, a flexible priority rule based approach is developed, making use of an extended concept of the availability of vehicles. For evaluation reasons, this approach is complemented by an alternative MILP formulation. Finally, the performance of the priority rule based approach and the MILP model are analysed for different scenarios with respect to total lateness of the AGVs. The main focus of the numerical investigation is on evaluating the priority rule based approach for single and dual-load vehicles as well as comparing its performance against the MILP modelling approach.     

基于批量划分的无等待流水车间订单接受问题研究

在无等待流水车间环境下,考虑订单分批量加工策略的订单接受问题,建立问题的数学模型。由于问题的NP难特性,提出改进的遗传算法对模型进行求解。改进的算法采用正向和反向NEH算法与随机方法产生初始种群,在算法更新过程中将禁忌搜索算法嵌入到遗传算法中来实现局部搜索,避免算法陷入局部最优。最后,算例表明批量划分策略能够有效减少订单的完成时间,实现订单总收益的最大化。通过算法对比,说明了改进遗传算法具有较好的求解效果。     

A tabu search algorithm for simultaneous machine/AGV scheduling problem

Machines and automated guided vehicles (AGVs) scheduling problems are two essential issues that need to be addressed for the efficiency of the overall production system. The purpose of this paper is to study the simultaneous scheduling problem of machines and AGVs in a flexible manufacturing system (FMS) since the global optimum cannot be reached by considering each of them individually. In this paper, a mixed integer linear programming (MILP) model is developed with the objective of makespan minimisation. The MILP model consists of the following two constraint sets: machines and AGVs scheduling sub-problems. As both sub-problems are known to be NP-hard, a heuristic algorithm based on tabu search (TS) is proposed to get optimal or near to optimal solution for large-size problems within reasonable computation time. The proposed algorithm includes a novel two-dimensional solution representation and the generation of two neighbour solutions, which are alternately and iteratively applied to improve solutions. Moreover, an improved lower bound calculation method is introduced for the large-size problems. Computational results show the superior performance of the TS algorithm for the simultaneous scheduling problem.     

LP-based heuristics for scheduling chemical batch processes

A mixed-integer linear programming (MILP) model for scheduling chemical batch processes is presented. Since computational times are prohibitive for most problems of realistic size, a two-stage solution procedure is suggested. In the first stage, an initial solution is derived by use of a LP-based heuristic. The proposed heuristic defines a time grid that includes only a limited number of feasible periods in which a processing task is allowed to start. Thus, the size of the original multi-period MILP model is reduced in a controlled manner and optimal solutions to the relaxed model are obtained within reasonable computational time. The second stage consists of an improvement step that aims to compress the initial schedule by left-shifting operations over the time-axis. In order to evaluate the applicability of the heuristics a number of numerical experiments were performed. It is shown that near-optimal solutions are obtained for largesize problems with only modest computational effort.     

Viscowave – a new solution for viscoelastic wave propagation of layered structures subjected to an impact load

The forward models frequently adopted for use in the dynamic backcalculation of the falling weight deflectometer (FWD) data are based on the solutions that utilise discrete transforms. In this paper, a new computational algorithm, namely ViscoWave, has been developed and implemented for modelling the pavement dynamics under the FWD impact load. The primary advantage of the proposed solution over some of the existing solutions is that it uses continuous integral transforms (Laplace and Hankel transforms) that are more appropriate for the FWD time histories whose signal characteristics are transient, non-periodic and truncated. Sample runs of the ViscoWave and the validation efforts presented in this paper showed that the proposed algorithm is capable of modelling the dynamics of a layered structure with elastic or viscoelastic material with or without a halfspace, indicating the potential of ViscoWave as a forward model for dynamic backcalculation of flexible pavement properties.