含不相关机的动态可重入柔性流水车间问题的混合DABC-GA算法

为了改善生产线的物流平衡和加强阶段间的时间衔接,扩展一般可重入柔性流水车间调度理论,以最小化总加权完工时间为目标,研究了每阶段含不相关并行机的动态可重入柔性流水车间问题,工件在各阶段的加工时间取决于加工它的机器。鉴于所研究问题为NP-hard问题,首先,建立整数规划模型;其次,设计元胞矩阵编码方案,提出融合离散人工蜂群算法和遗传算法的一种混合算法以获得问题的近优解;最后,为了评估混合算法的性能,将所提出算法和一些元启发式算法进行了不同规模问题的对比测试,实验结果说明了所提算法的有效性。     

求解混合流水线调度问题的离散人工蜂群算法

本文给出了一种离散的人工蜂群算法(HDABC)用于求解混合流水车间调度(HFS)问题。采用工件排序的编码方式,并设计了四种邻域结构。雇佣蜂依次分派到解集中每个解,采用结合问题特征的局部搜索策略完成挖掘搜索工作。跟随蜂随机选择两个解并挑选较优者作为当前解,完成进一步的探优过程。侦察蜂采用三种策略跳出局部极小。通过34个同构并行机HFS问题和2个异构并行机HFS实际调度问题的实验,并与当前文献中的典型算法对比,验证了本文提出的算法无论在算法时间还是在求解质量上,都具备良好的性能。     

A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem

This paper presents a biased random-key genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.     

A discrete bilevel brain storm algorithm for solving a sales territory design problem: a case study

A sales territory design problem faced by a manufacturing company that supplies products to a group of customers located in a service region is addressed in this paper. The planning process of designing the territories has the objective to minimizing the total dispersion of the customers without exceeding a limited budget assigned to each territory. Once territories have been determined, a salesperson has to define the day-by-day routes to satisfy the demand of customers. Currently, the company has established a service level policy that aims to minimize total waiting times during the distribution process. Also, each territory is served by a single salesperson. A novel discrete bilevel optimization model for the sales territory design problem is proposed. This problem can be seen as a bilevel problem with a single leader and multiple independent followers, in which the leader’s problem corresponds to the design of territories (manager of the company), and the routing decision for each territory corresponds to each follower. The hierarchical nature of the current company’s decision-making process triggers some particular characteristics of the bilevel model. A brain storm algorithm that exploits these characteristics is proposed to solve the discrete bilevel problem. The main features of the proposed algorithm are that the workload is used to verify the feasibility and to cluster the leader’s solutions. In addition, four discrete mechanisms are used to generate new solutions, and an elite set of solutions is considered to reduce computational cost. This algorithm is used to solve a real case study, and the results are compared against the current solution given by the company. Results show a reduction of more than 20% in the current costs with the solution obtained by the proposed algorithm. Furthermore, a sensitivity analysis is performed, providing interesting managerial insights to improve the current operations of the company.     

On the computation of all supported efficient solutions in multi-objective integer network flow problems

This paper presents a new algorithm for identifying all supported non-dominated vectors (or outcomes) in the objective space, as well as the corresponding efficient solutions in the decision space, for multi-objective integer network flow problems. Identifying the set of supported non-dominated vectors is of the utmost importance for obtaining a first approximation of the whole set of non-dominated vectors. This approximation is crucial, for example, in two-phase methods that first compute the supported non-dominated vectors and then the unsupported non-dominated ones. Our approach is based on a negative-cycle algorithm used in single objective minimum cost flow problems, applied to a sequence of parametric problems. The proposed approach uses the connectedness property of the set of supported non-dominated vectors/efficient solutions to find all integer solutions in maximal non-dominated/efficient facets.     

A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion

In this paper, we present a discrete artificial bee colony algorithm to solve the no-idle permutation flowshop scheduling problem with the total tardiness criterion. The no-idle permutation flowshop problem is a variant of the well-known permutation flowshop scheduling problem where idle time is not allowed on machines. In other words, the start time of processing the first job on a given machine must be delayed in order to satisfy the no-idle constraint. The paper presents the following contributions: First of all, a discrete artificial bee colony algorithm is presented to solve the problem on hand first time in the literature. Secondly, some novel methods of calculating the total tardiness from makespan are introduced for the no-idle permutation flowshop scheduling problem. Finally, the main contribution of the paper is due to the fact that a novel speed-up method for the insertion neighborhood is developed for the total tardiness criterion. The performance of the discrete artificial bee colony algorithm is evaluated against a traditional genetic algorithm. The computational results show its highly competitive performance when compared to the genetic algorithm. Ultimately, we provide the best known solutions for the total tardiness criterion with different due date tightness levels for the first time in the literature for the Taillard’s benchmark suit.     

Minimizing shifts for personnel task scheduling problems: A three-phase algorithm

The personnel task scheduling problem is a subject of commercial interest which has been investigated since the 1950s. This paper proposes an effective and efficient three-phase algorithm for solving the shift minimization personnel task scheduling problem (SMPTSP). To illustrate the increased efficacy of the proposed algorithm over an existing algorithm, computational experiments are performed on a test problem set with characteristics motivated by employee scheduling applications. Experimental results show that the proposed algorithm outperforms the existing algorithm in terms of providing optimal solutions, improving upon most of the best-known solutions and revealing high-quality feasible solutions for those unsolved test instances in the literature.     

High-Level Relay Hybrid Metaheuristic Method for Multi-Depot Vehicle Routing Problem with Time Windows

This paper presents an efficient hybrid metaheuristic solution for multi-depot vehicle routing with time windows (MD-VRPTW). MD-VRPTW involves the routing of a set of vehicles with limited capacity from a set of depots to a set of geographically dispersed customers with known demands and predefined time windows. The present work aims at using a hybrid metaheuristic algorithm in the class of High-Level Relay Hybrid (HRH) which works in three levels and uses an efficient genetic algorithm as the main optimization algorithm and tabu search as an improvement method. In the genetic algorithm various heuristics incorporate local exploitation in the evolutionary search. An operator deletion- retrieval strategy is executed which shows the efficiency of the inner working of the proposed method. The proposed algorithm is applied to solve the problems of the standard Cordeau??s Instances. Results show that proposed approach is quite effective, as it provides solutions that are competitive with the best known in the literature.     

A modified method for constructing efficient solutions structure of MOLP

This paper deals with a recently proposed algorithm for obtaining all weak efficient and efficient solutions in a multi objective linear programming (MOLP) problem. The algorithm is based on solving some weighted sum problems, and presents an easy and clear solution structure. We first present an example to show that the algorithm may fail when at least one of these weighted sum problems has not a finite optimal solution. Then, the algorithm is modified to overcome this problem. The modified algorithm determines whether an efficient solution exists for a given MOLP and generates the solution set correctly (if exists) without any change in the complexity.     

The use of possibility theory in the definition of fuzzy Pareto-optimality

Pareto-optimality conditions are crucial when dealing with classic multi-objective optimization problems. Extensions of these conditions to the fuzzy domain have been discussed and addressed in recent literature. This work presents a novel approach based on the definition of a fuzzily ordered set with a view to generating the necessary conditions for the Pareto-optimality of candidate solutions in the fuzzy domain. Making use of the conditions generated, one can characterize fuzzy efficient solutions by means of carefully chosen mono-objective problems and Karush-Kuhn-Tucker conditions to fuzzy non-dominated solutions. The uncertainties are inserted into the formulation of the studied fuzzy multi-objective optimization problem by means of fuzzy coefficients in the objective function. Some numerical examples are analytically solved to illustrate the efficiency of the proposed approach.