Bi-objective optimisation model for installation scheduling in offshore wind farms

A bi-objective optimisation using a compromise programming approach is proposed for installation scheduling of an offshore wind farm. As the installation cost and the completion period of the installation are important aspects in the construction of an offshore wind farm, the proposed method is used to deal with those conflicting objectives. We develop a mathematical model using integer linear programming (ILP) to determine the optimal installation schedule considering several constraints such as weather condition and the availability of vessels. We suggest two approaches to deal with the multi-objective installation scheduling problem, namely compromise programming with exact method and with metaheuristic techniques. In the exact method the problem is solved by CPLEX whereas in the metaheuristic approach we propose Variable Neighbourhood Search (VNS) and Simulated Annealing (SA). Moreover, greedy algorithms and a local search for solving the scheduling problem are introduced. Two generated datasets are used for testing our approaches. The computational experiments show that the proposed metaheuristic approaches produce interesting results as the optimal solution for some cases is obtained.     

Utility-based QoS optimisation strategy for multi-criteria scheduling on the grid

The paper presents quality of service (QoS) optimisation strategy for multi-criteria scheduling on the grid, based on a mathematical QoS model and a distributed iterative algorithm. Three QoS criteria are considered, namely payment, deadline and reliability, which are formulated as utility function. The optimisation problem is split into two parts: task optimisation performed on behalf of the user and resource optimisation performed on behalf of the grid. The strategy employs three types of agents: task agents responsible for task optimisation, computation resource and network resource agents responsible for resource optimisation. The agents apply economic models for optimisation purposes. Dynamic programming is used to optimise the total system utility function in terms of an iterative algorithm. The objective of multi-criteria scheduling is to maximise the global utility of the system. This paper proposes an iterative scheduling algorithm that is used to perform QoS optimisation-based multi-criteria scheduling. The proposed QoS optimisation-based multi-criteria scheduling problem solution has been practically examined by simulation experiments.     

A linear programming-based method for job shop scheduling

We present a decomposition heuristic for a large class of job shop scheduling problems. This heuristic utilizes information from the linear programming formulation of the associated optimal timing problem to solve subproblems, can be used for any objective function whose associated optimal timing problem can be expressed as a linear program (LP), and is particularly effective for objectives that include a component that is a function of individual operation completion times. Using the proposed heuristic framework, we address job shop scheduling problems with a variety of objectives where intermediate holding costs need to be explicitly considered. In computational testing, we demonstrate the performance of our proposed solution approach.     

Multi-objective optimisation and decision-making of space station logistics strategies

Space station logistics strategy optimisation is a complex engineering problem with multiple objectives. Finding a decision-maker-preferred compromise solution becomes more significant when solving such a problem. However, the designer-preferred solution is not easy to determine using the traditional method. Thus, a hybrid approach that combines the multi-objective evolutionary algorithm, physical programming, and differential evolution (DE) algorithm is proposed to deal with the optimisation and decision-making of space station logistics strategies. A multi-objective evolutionary algorithm is used to acquire a Pareto frontier and help determine the range parameters of the physical programming. Physical programming is employed to convert the four-objective problem into a single-objective problem, and a DE algorithm is applied to solve the resulting physical programming-based optimisation problem. Five kinds of objective preference are simulated and compared. The simulation results indicate that the proposed approach can produce good compromise solutions corresponding to different decision-makers’ preferences.     

A genetic algorithm/mathematical programming approach to solve a two-level soft drink production problem

This study applies a genetic algorithm embedded with mathematical programming techniques to solve a synchronized and integrated two-level lot sizing and scheduling problem motivated by a real-world problem that arises in soft drink production. The problem considers a production process compounded by raw material preparation/storage and soft drink bottling. The lot sizing and scheduling decisions should be made simultaneously for raw material preparation/storage in tanks and soft drink bottling in several production lines minimizing inventory, shortage and setup costs. The literature provides mixed-integer programming models for this problem, as well as solution methods based on evolutionary algorithms and relax-and-fix approaches. The method applied by this paper uses a new approach which combines a genetic algorithm (GA) with mathematical programming techniques. The GA deals with sequencing decisions for production lots, so that an exact method can solve a simplified linear programming model, responsible for lot sizing decisions. The computational results show that this evolutionary/mathematical programming approach outperforms the literature methods in terms of production costs and run times when applied to a set of real-world problem instances provided by a soft drink company.     

An iterative approach to robust and integrated aircraft routing and crew scheduling

In airline scheduling a variety of planning and operational decision problems have to be solved. We consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights in a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved later. Also, when minimal cost solutions are used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day. We generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We solve the two original problems iteratively. Starting from a minimal cost solution, we produce a series of solutions which are increasingly robust. Using data from domestic airline schedules we evaluate the benefits of the approach as well as the trade-off between cost and robustness. We extend our approach considering the aircraft routing problem together with two crew pairing problems, one for technical crew and one for flight attendants.     

An integrated and dynamic optimisation model for the multi-level emergency logistics network in anti-bioterrorism system

Demand for emergency resources is usually uncertain and varies quickly in anti-bioterrorism system. Besides, emergency resources which had been allocated to the epidemic areas in the early rescue cycle will affect the demand later. In this article, an integrated and dynamic optimisation model with time-varying demand based on the epidemic diffusion rule is constructed. The heuristic algorithm coupled with the MATLAB mathematical programming solver is adopted to solve the optimisation model. In what follows, the application of the optimisation model as well as a short sensitivity analysis of the key parameters in the time-varying demand forecast model is presented. The results show that both the model and the solution algorithm are useful in practice, and both objectives of inventory level and emergency rescue cost can be controlled effectively. Thus, it can provide some guidelines for decision makers when coping with emergency rescue problem with uncertain demand, and offers an excellent reference when issues pertain to bioterrorism.     

Solving the bi‐objective capacitated p‐median problem with multilevel capacities using compromise programming and VNS

A bi‐objective optimisation using a compromise programming (CP) approach is proposed for the capacitated p‐median problem (CPMP) in the presence of the fixed cost of opening facility and several possible capacities that can be used by potential facilities. As the sum of distances between customers and their facilities and the total fixed cost for opening facilities are important aspects, the model is proposed to deal with those conflicting objectives. We develop a mathematical model using integer linear programming (ILP) to determine the optimal location of open facilities with their optimal capacity. Two approaches are designed to deal with the bi‐objective CPMP, namely CP with an exact method and with a variable neighbourhood search (VNS) based matheuristic. New sets of generated instances are used to evaluate the performance of the proposed approaches. The computational experiments show that the proposed approaches produce interesting results.     

A multi objective volleyball premier league algorithm for green scheduling identical parallel machines with splitting jobs

Parallel machine scheduling is one of the most common studied problems in recent years, however, this classic optimization problem has to achieve two conflicting objectives, i.e. minimizing the total tardiness and minimizing the total wastes, if the scheduling is done in the context of plastic injection industry where jobs are splitting and molds are important constraints. This paper proposes a mathematical model for scheduling parallel machines with splitting jobs and resource constraints. Two minimization objectives - the total tardiness and the number of waste - are considered, simultaneously. The obtained model is a bi-objective integer linear programming model that is shown to be of NP-hard class optimization problems. In this paper, a novel Multi-Objective Volleyball Premier League (MOVPL) algorithm is presented for solving the aforementioned problem. This algorithm uses the crowding distance concept used in NSGA-II as an extension of the Volleyball Premier League (VPL) that we recently introduced. Furthermore, the results are compared with six multi-objective metaheuristic algorithms of MOPSO, NSGA-II, MOGWO, MOALO, MOEA/D, and SPEA2. Using five standard metrics and ten test problems, the performance of the Pareto-based algorithms was investigated. The results demonstrate that in general, the proposed algorithm has supremacy than the other four algorithms.

     

A new Lagrangian Relaxation Algorithm for scheduling dissimilar parallel machines with release dates

In this article we investigate the parallel machine scheduling problem with job release dates, focusing on the case that machines are dissimilar with each other. The goal of scheduling is to find an assignment and sequence for a set of jobs so that the total weighted completion time is minimised. This type of production environment is frequently encountered in process industry, such as chemical and steel industries, where the scheduling of jobs with different purposes is an important goal. This article formulates the problem as an integer linear programming model. Because of the dissimilarity of machines, the ordinary job-based decomposition method is no longer applicable, a novel machine-based Lagrangian relaxation algorithm is therefore proposed. Penalty terms associated with violations of coupling constraints are introduced to the objective function by Lagrangian multipliers, which are updated using subgradient optimisation method. For each machine-level subproblem after decomposition, a forward dynamic programming algorithm is designed together with the weighted shortest processing time rule to provide an optimal solution. A heuristics is developed to obtain a feasible schedule from the solution of subproblems to provide an upper bound. Numerical results show that the new approach is computationally effective to handle the addressed problem and provide high quality schedules.     

Investigating the use of genetic programming for a classic one-machine scheduling problem

Genetic programming has rarely been applied to manufacturing optimisation problems. In this paper the potential use of genetic programming for the solution of the one-machine total tardiness problem is investigated. Genetic programming is utilised for the evolution of scheduling policies in the form of dispatching rules. These rules are trained to cope with different levels of tardiness and tightness of due dates.     

Multiple- and single-objective approaches to laminate optimization with genetic algorithms

In this paper an application of a genetic algorithm to a material- and sizing-optimization problem of a plate is described. This approach has obvious advantages: it does not require any derivative information and it does not impose any restriction, in terms of convexity, on the solution space. The plate optimization problem is firstly formulated as a constrained mixed-integer programming problem with a single objective function. An alternative multiobjective formulation of the problem in which some constraints are included as additional objectives is also presented. Some numerical results are included that show the appropriateness of the algorithm and of the mathematical model for the solution of this optimization problem, as well as the superiority of the multiobjective approach.     

A new optimal approach for multiple optimisation objectives grid resource allocation and scheduling

The article considers the resource allocation and scheduling problem in a grid computing environment. The article proposes system optimisation scheduling (SOS) that provides a potential solution of joint optimisation of objectives for both the resource and application layer, which combine both application-oriented and resource-oriented scheduling benefits. Grid systems will strive to find an optimal relation between user satisfaction and resource utilisation. Utility functions are used to express grid user's Quality of Service requirement, resource provider's benefit function and system's objectives. In order to verify the efficiency of the proposed scheduling algorithm, we compare the performance of application optimisation scheduling, resource optimisation scheduling, SOS with a traditional Round-Robin algorithm. The simulations study the effect of the request rate and task-to-resource ratio on the different scheduling algorithm.     

Dynamic supply chain scheduling

Based on a combination of fundamental results of modern optimal program control theory and operations research, an original approach to supply chain scheduling is developed in order to answer the challenges of dynamics, uncertainty, and adaptivity. Both supply chain schedule generation and execution control are represented as an optimal program control problem in combination with mathematical programming and interpreted as a dynamic process of operations control within an adaptive framework. Hence, the problems and models of planning, scheduling, and adaptation can be consistently integrated on a unified mathematical axiomatic of modern control theory. In addition, operations control and flow control models are integrated and applicable for both discrete and continuous processes. The application of optimal control for supply chain scheduling becomes possible by formulating the scheduling model as a linear non-stationary finite-dimensional controlled differential system with the convex area of admissible control and a reconfigurable structure. For this model class, theorems of optimal control existence can be used regarding supply chain scheduling. The essential structural property of this model are the linear right parts of differential equations. This allows applying methods of discrete optimization for optimal control calculation. The calculation procedure is based on applying Pontryagin’s maximum principle and the resulting essential reduction of problem dimensionality that is under solution at each instant of time. The gained insights contribute to supply chain scheduling theory, providing advanced insights into dynamics of the whole supply chains (and not any dyadic relations in them) and transition from a partial “one-way” schedule optimization to the feedback loop-based dynamic and adaptive supply chain planning and scheduling.     

Sequencing optimisation for makespan improvement at wet-etch tools

The complex nature of wet-etch tools and their peculiar scheduling constraints pose a relevant challenge for the development and implementation of makespan optimisation strategies, especially when rigid scheduling rules have to be considered. In this paper, an optimisation model is developed for sequencing of wafer batches outside a wet-etch tool and scheduling of tool-internal handler moves. The scheduling algorithm is inspired by the control logics governing wet-etch tools operating in a real semiconductor manufacturing plant and proves effective in generating efficient and detailed schedules in short computational times. The mathematical formulation developed for the scheduling problem is based on generic and realistic assumptions for both the job flow and the material handling system. The sequencing module combines an exact optimisation approach, based on an efficient permutation concept, and a heuristics optimisation approach, based on genetic algorithms. The results obtained show that significant makespan reductions can be obtained by means of a mere sequencing optimisation. Using this optimisation strategy, variations to the scheduling logics, that are generally more difficult and expensive to implement, are avoided. A sensitivity analysis on genetic algorithm operators is also conducted and considerations on the best performing selection, cross-over and mutation operators are presented.     

A fuzzy-mixed-integer goal programming model for a parallel-machine scheduling problem with sequence-dependent setup times and release dates

This paper presents a new mixed-integer goal programming (MIGP) model for a parallel-machine scheduling problem with sequence-dependent setup times and release dates. Two objectives are considered in the model to minimize the total weighted flow time and the total weighted tardiness simultaneously. Due to the complexity of the above model and uncertainty involved in real-world scheduling problems, it is sometimes unrealistic or even impossible to acquire exact input data. Hence, we consider the parallel-machine scheduling problem with sequence-dependent set-up times under the hypothesis of fuzzy processing time's knowledge and two fuzzy objectives as the MIGP model. In addition, a quite effective and applicable methodology for solving the above fuzzy model are presented. At the end, the effectiveness of the proposed model and the denoted methodology is demonstrated through some test problems.     

Parallel machine scheduling with flexible resources

Parallel machine flexible resource scheduling (PMFRS) problems consider an additional flexible resource (e.g. operators), which can be freely allocated to any jobs and/or any machines and may speed-up the process in proportion to its amount. If job–machine assignment is unspecified, the problem is referred to as unspecified PMFRS (UPMFRS). This paper reviews the mathematical models of both PMFRS and UPMFRS problems in the literature and not only gives some extensions to the model of dynamic PMFRS problem but also presents integer programming (IP) models for static and dynamic UPMFRS problems with the objective of minimizing makespan. To solve large-sized dynamic PMFRS and UPMFRS problems, a relaxed IP based constraint programming (CP) approach is also proposed. All IP models and the proposed IP/CP approach are tested with an extensive computational study. The results of the computational experiments are discussed with respect to the major parameters of the problem and conclusions are drawn.     

A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction

Manufacturing scheduling strategies have historically emphasized cycle time; in almost all cases, energy and environmental factors have not been considered in scheduling. This paper presents a new mathematical programming model of the flow shop scheduling problem that considers peak power load, energy consumption, and associated carbon footprint in addition to cycle time. The new model is demonstrated using a simple case study: a flow shop where two machines are employed to produce a variety of parts. In addition to the processing order of the jobs, the proposed scheduling problem considers the operation speed as an independent variable, which can be changed to affect the peak load and energy consumption. Even with a single objective, finding an optimal schedule is notoriously difficult, so directly applying commercial software to this multi-objective scheduling problem requires significant computation time. This paper calls for the development of more specialized algorithms for this new scheduling problem and examines computationally tractable approaches for finding near-optimal schedules.     

冷链物流越库调度的拉格朗日松弛算法

为了提高冷链物流的运输效率,解决越库在冷链物流中的应用问题,提出了基于拉格朗日松弛算法的冷链物流的越库调度方法.首先进行了问题域的描述并做出了具体假设,基于问题域以最小化卡车等待时间和越库内部运输成本为目标,建立越库调度的整数规划数学模型.然后,提出了针对越库调度模型的拉格朗日松弛算法,松弛复杂约束后根据决策变量将松弛问题分解为若干子问题,采用次梯度算法求解松弛模型.最后,对各种不同规模的越库模型进行仿真实验,并与传统的贪婪算法进行对比,结果表明,所提出的调度算法适用于问题的求解,并可以在较短时间内获得良好的近优解.