Maximizing production rate and workload smoothing in assembly lines using particle swarm optimization

Particle swarm optimization (PSO) one of the latest developed population heuristics has rarely been applied in production and operations management (POM) optimization problems. A possible reason for this absence is that, PSO was introduced as global optimizer over continuous spaces, while a large set of POM problems are of combinatorial nature with discrete decision variables. PSO evolves floating-point vectors (called particles) and thus, its application to POM problems whose solutions are usually presented by permutations of integers is not straightforward. This paper presents a novel method based on PSO for the simple assembly line balancing problem (SALBP), a well-known NP-hard POM problem. Two criteria are simultaneously considered for optimization: to maximize the production rate of the line (equivalently to minimize the cycle time), and to maximize the workload smoothing (i.e. to distribute the workload evenly as possible to the workstations of the assembly line). Emphasis is given on seeking a set of diverse Pareto optimal solutions for the bi-criteria SALBP. Extensive experiments carried out on multiple test-beds problems taken from the open literature are reported and discussed. Comparisons between the proposed PSO algorithm and two existing multi-objective population heuristics show a quite promising higher performance for the proposed approach.     

A class of chance constrained multiobjective linear programming with birandom coefficients and its application to vendors selection

In this paper, a class of chance constrained multiobjective linear programming model with birandom coefficients is considered for vendor selection problem. Firstly we present a crisp equivalent model for a special case and give a traditional method for crisp model. Then, the technique of birandom simulation is applied to deal with general birandom objective functions and birandom constraints which are usually difficult to be converted into their crisp equivalents. Furthermore, a genetic algorithm based on birandom simulation is designed for solving a birandom multiobjective vendor selection problem. Finally, a real numbers example is given. The paper makes certain contribution in both theoretical and application research related to multiobjective chance constrained programming, as well as in the study of vendor selection problem under uncertain environment.     

A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search

The job-shop scheduling problem is one of the most arduous combinatorial optimization problems. Flexible job-shop problem is an extension of the job-shop problem that allows an operation to be processed by any machine from a given set along different routes. This paper present a new approach based on a hybridization of the particle swarm and local search algorithm to solve the multi-objective flexible job-shop scheduling problem. The particle swarm optimization is a highly efficient and a new evolutionary computation technique inspired by birds’ flight and communication behaviors. The multi-objective particle swarm algorithm is applied to the flexible job-shop scheduling problem based on priority. Also the presented approach will be evaluated for their efficiency against the results reported for similar algorithms (weighted summation of objectives and Pareto approaches). The results indicate that the proposed algorithm satisfactorily captures the multi-objective flexible job-shop problem and competes well with similar approaches.     

A modified artificial bee colony algorithm for order acceptance in two-machine flow shops

We consider a two-stage make-to-order production system characterized by limited production capacity and tight order due dates. We want to make joint decisions on order acceptance and scheduling to maximize the total net revenue. The problem is computationally intractable. In view of the fact that artificial bee colony algorithm has been shown to be an effective evolutionary algorithm to handle combinatorial optimization problems, we first conduct a pilot study of applying the basic artificial bee colony algorithm to treat our problem. Based on the results of the pilot study and the problem characteristics, we develop a modified artificial bee colony algorithm. The experimental results show that the modified artificial bee colony algorithm is able to generate good solutions for large-scale problem instances.     

A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system

We analyze a two-machine flow-shop scheduling problem in which the job processing times are controllable by the allocation of resources to the job operations and the resources can be used in discrete quantities. We provide a bicriteria analysis of the problem where the first criterion is to maximize the weighted number of just-in-time jobs and the second criterion is to minimize the total resource consumption cost. We prove that although the problem is known to be NP-hard even for constant processing times, a pseudo-polynomial time algorithm for its solution exists. In addition, we show how the pseudo-polynomial time algorithm can be converted into a two-dimensional fully polynomial approximation scheme for finding an approximate Pareto solution.     

Metaheuristics for drilling operation scheduling in Taiwan PCB industries

Among all types of production environment, identical parallel machines are frequently used to increase the manufacturing capacity of the drilling operation in Taiwan printed circuit board (PCB) industries. Additionally, multiple but conflicting objectives are usually considered when a manager plans the production scheduling. Compared to the single objective problem, the multiple-objective version no longer looks for an individual optimal solution, but a Pareto front consisting of a set of non-dominated solutions will be needed and established. The manager then can select one of the alternatives from the set. This research aims at employing a variable neighborhood search (VNS) algorithm and a multiple ant colony optimization (MACO) algorithm to solve the identical parallel-machine scheduling problem with two conflicting objectives: makespan and total tardiness. In VNS, two neighborhoods are defined—insert a job to a different position or swap two jobs in the sequence. To save the computational expense, one of the neighborhoods is randomly selected for the target solution which is also arbitrarily chosen from the current Pareto front. In MACO, a two-phase construction procedure where three colonies are employed in each phase is proposed. These two algorithms are tested on a set of real data collected from a leading PCB factory in Taiwan and their performances are compared. The computational results show that VNS outperforms all competing algorithms—SPGA, MOGA, NSGA-II, SPEA-II, and MACO in terms of solution quality and computational time.     

基于帕累托最优配置的碳排放许可证拍卖机制

兑现2020年碳减排目标的承诺为我国碳交易市场的建立提供了新的契机,同时使得"如何以最小化经济增长冲击降低二氧化碳排放量"成为一个焦点问题。本文针对"如何有效配置碳排放许可证"做一个前瞻性研究,把帕累托最优概念引入碳排放许可证拍卖—交易框架,设计一个新的碳排放许可证拍卖机制,其规则相对简单,仅有四步构成,易于被市场参与者理解和接受,而且在有限时间内此机制收敛于一个帕累托最优配置,从而实现了碳排放许可证资源的有效利用,在没有平局出现的约束下,最终的均衡配置是唯一的。此外,文中的拍卖机制不仅能最大化卖方的收益,而且买方还拥有占优竞标策略,这些优点决定了此机制在将来的商业应用中能被买卖双方所青睐。最后,用一个具体案例解释新机制的操作过程及其在实践中的可行性,为环境交易所提供一个备选的交易方案。     

Multi-objective ant colony optimisation: A meta-heuristic approach to supply chain design

This paper proposes a new approach to determining the Supply Chain (SC) design for a family of products comprising complex hierarchies of subassemblies and components. For a supply chain, there may be multiple suppliers that could supply the same components as well as optional manufacturing plants that could assemble the subassemblies and the products. Each of these options is differentiated by a lead-time and cost. Given all the possible options, the supply chain design problem is to select the options that minimise the total supply chain cost while keeping the total lead-times within required delivery due dates. This work proposes an algorithm based on Pareto Ant Colony Optimisation as an effective meta-heuristic method for solving multi-objective supply chain design problems. An experimental example and a number of variations of the example are used to test the algorithm and the results reported using a number of comparative metrics. Parameters affecting the performance of the algorithm are investigated.     

Scheduling a multi-stage fabrication shop for efficient subsequent assembly operations

Consideration is given to scheduling the operation of a multi-stage fabrication shop producing the component parts of a major commercial refrigerators producer. The objective of this scheduling problem is the determination of both production sequences and lot quantities at each stage so as to meet production targets and ensure continuous operation of subsequent assembly stations. After describing the problem within its natural context, we present an algorithm for the dynamic scheduling of the fabrication shop. This applies general planning principles adapted to the needs of the environment under consideration and makes use of existing heuristic rules for arriving at sequencing decisions. Although in no sense optimal, the algorithm can provide good feasible solutions to a previously not formally analysed problem. After being incorporated into a systematic computer-aided scheduling procedure, the algorithm has been actually implemented, demonstrating considerable improvements over previous fabrication shop scheduling practice.     

A hybrid heuristic algorithm adopting both Boltzmann function and mutation operator for manufacturing cell formation problems

This study proposes a hybrid heuristic algorithm employing both the Boltzmann function from simulated annealing and the mutation operator from the genetic algorithm to explore the unvisited solution region and expedite the solution searching process for the cell formation problem, so that grouping efficacy is maximized. Test problems drawn from the literature are used to test the performance of the proposed heuristic algorithm. The comparative study shows that the proposed algorithm improves the best results found in the literature for 36% of the test problems in the case when singletons solutions are allowed.     

The maximum capture per unit cost location problem

This paper considers the problem of siting p new facilities of an entering firm to a competitive market so as to maximize the market share captured from competitors per unit cost. We first formulate the problem as a mixed 0-1 fractional programming model, in which we incorporate the fixed cost and transportation cost. The model can deal with the case where some demand nodes have two or more possible closest servers. We then re-formulate the problem as a 0-1 mixed integer linear program. We use a one-opt heuristic algorithm based on the Teitz-Bart method to obtain feasible solutions and compare them with the optimal solutions obtained by a branch-and-bound algorithm. We conduct computational experiments to evaluate the two algorithms. The results show that both algorithms can solve the model efficiently and the model is integer-friendly. We discuss other computational results and provide managerial insights.     

A multiple ant colony optimization algorithm for the capacitated location routing problem

The success of a logistics system may depend on the decisions of the depot locations and vehicle routings. The location routing problem (LRP) simultaneously tackles both location and routing decisions to minimize the total system cost. In this paper a multiple ant colony optimization algorithm (MACO) is developed to solve the LRP with capacity constraints (CLRP) on depots and routes. We decompose the CLRP into facility location problem (FLP) and multiple depot vehicle routing problem (MDVRP), where the latter one is treated as a sub problem within the first problem. The MACO algorithm applies a hierarchical ant colony structure that is designed to optimize different subproblems: location selection, customer assignment, and vehicle routing problem, in which the last two are the decisions for the MDVRP. Cooperation between colonies is performed by exchanging information through pheromone updating between the location selection and customer assignment. The proposed algorithm is evaluated on four different sets of benchmark instances and compared with other algorithms from the literature. The computational results indicate that MACO is competitive with other well-known algorithms, being able to obtain numerous new best solutions.     

Scheduling a single batch processing machine with arbitrary job sizes and incompatible job families

Motivated by a bottleneck operation in a multi-layer ceramic capacitor production line, we study a scheduling problem of batch processing machine in which a number of jobs are processed simultaneously as a batch. The performance measures considered include makespan, total completion time, and total weighted completion time. We first present a new simple integer programming formulation for the problem, and using this formulation, one can easily find optimal solutions for small problems. However, since the problem is NP-hard and the size of a real problem is very large, we propose a number of heuristic algorithms and design a hybrid genetic algorithm to solve practical big-size problems in a reasonable computational time. To verify performance of the algorithms, we compare them with lower bounds for the problems. From the results of these computational experiments the heuristic algorithms including the genetic algorithm show different performances for the three problems.     

Minimizing mean absolute deviation of completion time about a common due window subject to maximum tardiness for a single machine

This study deals with the problem of scheduling jobs on a single machine to minimize the mean absolute deviation of the job completion time about a large common due window subject to the maximum tardiness constraint. Using the well-known three-field notation, the problem is identified as MAD/large DueWindow/T_max. The common due window is set to be large enough to allow idle time prior to the beginning of a schedule to investigate the effect of the T_max constraint. Penalties arise if a job is completed outside the due window. A branch and bound algorithm and a heuristic are proposed. Many properties of the solutions and precedence relationships are identified. Our computational results reveal that the branch and bound algorithm is capable of solving problems of up to 50 jobs and the heuristic algorithm yields approximate solutions that are very close to the exact solution.     

Hybrid heuristics for planning job rotation schedules in assembly lines with heterogeneous workers

We investigate the problem of balancing assembly lines with heterogeneous workers while considering job rotation schedules. This problem typically occurs in assembly lines in sheltered work centers for disabled. We propose a hybrid algorithm that uses a Mixed Integer Programming (MIP) to select appropriate schedules from a pool of heuristically constructed solutions. A local search based on MIP neighborhoods is used as a post-optimization method. Our results show that this approach is fast, flexible and accurate when compared with current available methods.     

A novel differential evolution algorithm for joint replenishment problem under interdependence and its application

In this paper, we propose a new differential evolution (DE) algorithm for joint replenishment of inventory using both direct grouping and indirect grouping which allows for the interdependence of minor ordering costs. Since solutions to the joint replenishment problem (JRP) can be represented by integer decision variables, this makes the JRP a good candidate for the DE algorithm. The results of testing randomly generated problems in contrastive numerical examples and two extended experiments show that the DE algorithm provides close to optimal results for some problems than the evolutionary algorithm (EA), which has been proved to be an efficient algorithm. Moreover, the DE algorithm is faster than the EA for most problems. We also conducted a case study and application results suggest that the proposed model is successful in decreasing total costs of maintenance materials inventories significantly in two power companies.     

Algorithm portfolios for logistics optimization considering stochastic demands and mobility allowance

The vehicle routing problem with stochastic demand (VRPSD) is a well known NP-hard problem. The uncharacteristic behaviour associated with the problem enhances the computational efforts required to obtain a feasible and near-optimal solution. This paper proposes an algorithm portfolio methodology based on evolutionary algorithms, which takes into account the stochastic nature of customer demand to solve this computationally complex problem. These problems are well known to have computationally complex objective functions, which make their solutions hard to find, particularly when problem instances of large dimensions are considered. Of particular importance in such situations is the timeliness of the solution. For example, Apple was forced to delay their shipments of iPads internationally due to unprecedented demand and issues with their delivery systems in Samsung Electronics and Seiko Epson. Such examples illustrate the importance of stochastic customer demands and the timing of delivery. Moreover, most of the evolutionary algorithms, known for providing computationally efficient solutions, are unable to always provide optimal or near optimal solutions to all the VRPSD instances within allocated time interval. This is due to the characteristic variations in the computational time taken by evolutionary algorithms for same or varying size of the VRPSD instances. Therefore, this paper presents portfolios of different evolutionary algorithms to reduce the computational time taken to resolve the VRPSD. Moreover, an innovative concept of the mobility allowance (MA) in landmoves based on the levy’s distribution function has been introduced to cope with real situations existing in vehicle routing problems. The proposed portfolio approach has been evaluated for the varying instances of the VRPSD. Four of the existing metaheuristics including Genetic Algorithm (GA), Simulated Annealing (SA), Artificial Immune System (AIS), TABU Search (TS) along with new neighbourhood search, are incorporated in the portfolios. Experiments have been performed on varying dimensions of the VRPSD instances to validate the different properties of the algorithm portfolio. An illustrative example is presented to show that the set of metaheuristics allocated to certain number of processors (i.e. algorithm portfolio) performed better than their individual metaheuristics.     

The selective pickup and delivery problem: Formulation and a memetic algorithm

The pickup and delivery problem addresses the real-world issues in logistic industry and establishes an important category of vehicle routing problems. The problem is to find the shortest route to collect and distribute commodities under the assumption that the total supply and the total demand are in equilibrium. This study presents a novel problem formulation, called the selective pickup and delivery problem (SPDP), by relaxing the constraint that all pickup nodes must be visited. Specifically, the SPDP aims to find the shortest route that can supply delivery nodes with required commodities from some pickup nodes. This problem can substantially reduce the transportation cost and fits real-world logistic scenarios. Furthermore, this study proves that the SPDP is NP-hard and proposes a memetic algorithm (MA) based on genetic algorithm and local search to resolve the problem. A novel representation of candidate solutions is designed for the selection of pickup nodes. The related operators are also devised for the MA; in particular, it adapts the 2-opt operator to the sub-routes of the SPDP for enhancement of visiting order. The experimental results on several SPDP instances validate that the proposed MA can significantly outperform genetic algorithm and tabu search in terms of solution quality and convergence speed. In addition, the reduced route lengths on the test instances and the real-world application to rental bikes distribution demonstrate the benefit of the SPDP in logistics.     

Particle swarm optimization with cocktail decoding method for hybrid flow shop scheduling problems with multiprocessor tasks

This paper addresses the problem of multiprocessor task-scheduling in a hybrid flow shop (HFS) problem to minimize the makespan. Due to the complex nature of an HFS problem, it is decomposed into the following two sequential decision problems: determining the job permutation in stage 1, followed by a decoding method to assign jobs into each machine in subsequent stages when designing a heuristic algorithm. The decoding method plays a pivotal role for improving the solution quality of any algorithm for the HFS problem. However, the majority of existing algorithms ignores the problem and is only concerned with the first decision problem. This study emphasizes the importance of the decoding method via a small test, and searches for a number of solid decoding methods that can be incorporated into the cocktail decoding method. Then, this study develops a particle swarm optimization (PSO) algorithm that can be combined with the cocktail decoding method. In the PSO, a variety of job sequences are generated using the PSO procedure in stage 1, and the cocktail decoding method is used to assign the jobs to machines in sequential stages. Moreover, a modified lower bound is introduced. Computational results show that the proposed lower bound is competitive, and with the help of the cocktail decoding method, the proposed PSO, and even the adoption of a standard PSO framework, significantly outperforms the majority of existing algorithms in terms of quality of solutions, especially for large problems.     

GAN-MP hybrid heuristic algorithm for non-convex portfolio optimization problem

Abstract

During recent decades, the traditional Markowitz model has been extended for asset cardinality, active share, and tracking-error constraints, which were introduced to overcome the drawbacks of the original Markowitz model. The resulting optimization problems, however, are often very difficult to solve, whereas those of the original Markowitz model are easily solvable. In order to resolve the portfolio optimization problem for the new extensions, we developed a novel heuristic algorithm that combines GAN (Generative Adversarial Networks) with mathematical programming: the GAN-MP hybrid heuristic algorithm. To the best of our knowledge, this is the first attempt to bridge neural networks (NN) and mathematical programming to tackle a real-world portfolio optimization problem. Computational experiments with real-life stock data show that our algorithm significantly outperforms the existing non-linear optimization solvers.