Unidirectional loop network layout by a LP heuristic and design of telecommunications networks

In this paper, we present a new linear programming-based heuristic procedure for optimal design of the unidirectional loop network layout problem. The heuristic procedure employs a linear programming formulation and solves the problem using the flow matrix of the unidirectional loop problem. To find an optimal solution, one can either generate all possible solutions or use a branch-and-bound procedure. But, both above methods require very high computational time and computer memory for larger problems. The heuristic developed in this paper is quite fast and obtains near optimal solutions. The heuristic procedure was tested on 16 different problems selected from the literature. The results showed that in most cases optimal—and in a few cases near optimal—solutions were obtained with very little computational time. Several examples are discussed. We also demonstrate that the above problem formulation and approach can be used to solve a special class of telecommunication networks where a set of computers (or processors) are attached by unidirectional point-to-point links around a loop.     

Solving a combined cutting-stock and lot-sizing problem with a column generating procedure

In NonÅs and Thorstenson [A combined cutting stock and lot sizing problem. European Journal of Operational Research 120(2) (2000) 327–42] a combined cutting-stock and lot-sizing problem is outlined under static and deterministic conditions. In this paper we suggest a new column generating solution procedure for this problem that works well on both small and large-sized problems. The procedure includes characteristics from both the column generating procedure in NonÅs and Thorstenson, which works well on small-sized problems, and from the sequential heuristic due to Haessler [A heuristic programming solution to a nonlinear cutting stock problem, Management Science 17(12) (1971) 793–802], which works well on large-sized problems. Numerical results are presented that show that the new heuristic performs better than both of the earlier procedures. Comparisons with results obtained by other authors indicate that the procedure works well also for the extended cutting-stock problem with only a setup cost for each pattern change.     

A GRASP algorithm based new heuristic for the capacitated location routing problem

Abstract

In this paper, the capacitated location-routing problem (CLRP) is studied. CLRP is composed of two hard optimisation problems: the facility location problem and the vehicle routing problem. The objective of CLRP is to determine the best location of multiple depots with their vehicle routes such that the total cost of the solution is minimal. To solve this problem, we propose a greedy randomised adaptive search procedure. The proposed method is based on a new heuristic to construct a feasible CLRP solution, and then a local search-based simulated annealing is used as improvement phase. We have used a new technique to construct the clusters around the depots. To prove the effectiveness of our algorithm, several LRP instances are used. The results found are very encouraging.     

Heuristic algorithms for the general nonlinear separable knapsack problem

We consider the nonlinear knapsack problem with separable nonconvex functions. Depending on the assumption on the integrality of the variables, this problem can be modeled as a nonlinear programming or as a (mixed) integer nonlinear programming problem. In both cases, this class of problems is very difficult to solve, both from a theoretical and a practical viewpoint. We propose a fast heuristic algorithm, and a local search post-optimization procedure. A series of computational comparisons with a heuristic method for general nonconvex mixed integer nonlinear programming and with global optimization methods shows that the proposed algorithms provide high-quality solutions within very short computing times.     

Firing sequences backward algorithm for simple assembly line balancing problem of type 1

The objective of simple assembly line balancing problem type-1 (SALBP-1) is to minimize the number of workstations on an assembly line for a given cycle time. Since SALBP-1 is NP-hard, many iterative backtracking heuristics based on branch and bound procedure, tabu search, and genetic algorithms were developed to solve SALBP-1. In this study, a new heuristic algorithm based on Petri net approach is presented to solve the problem. The presented algorithm makes an order of firing sequence of transitions from Petri net model of precedence diagram. Task is assigned to a workstation using this order and backward procedure. The algorithm is coded in MATLAB, and its efficiency is tested on Talbot’s and Hoffmann’s benchmark datasets according to some performance measures and classifications. Computational study validates its effectiveness on the benchmark problems. Also comparison results show that the algorithm is efficiency to solve SALBP-1.     

基于动态极大度的极小碰集求解方法

在计算集合簇的碰集时,结合SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成所有的极小碰集.并在SE-Tree中添加了终止结点,避免了非极小碰集的产生,并且不会因剪枝而丢失正确的解.提出未扩展元素度的概念和结点度的概念,进而在扩展SE-Tree结点时按照未扩展元素度由大到小的顺序扩展,极早地生成集合簇的碰集,减少枚举树生成的结点个数,并且直接根据结点度得出结点对应的集合是否为集合簇的碰集,避免计算集合是否为集合簇的碰集.实验结果表明,该算法程序容易编制且效率较好.     

Optimization and heuristic models to integrate project task and manpower scheduling

The objective of project scheduling is to determine start dates and the labor resources assigned to each activity in order to complete a project on time. By moving start dates within available slack times and altering labor levels, the daily labor-demand profile can be changed. The objective of personnel scheduling is to determine how many of each feasible workday tour are required to satisfy a given labor-demand profile while minimizing the cost of labor plus overhead. Integrating these two problems permits the simultaneous determination of start dates, labor levels and tours for a minimum-cost and on-time schedule. In this paper, single and multiple resource optimization models and heuristic solution procedures to solve the integrated problem are presented. The heuristic procedure outperformed the non-integrated two-step scheduling procedure by reducing the cost of labor and overhead and performed nearly as well as the optimization procedure.     

结合增量与启发式搜索的多目标问题处理方法

提出了一种结合增量与启发式搜索的多目标问题处理方法,设计并实现了一个基于路径扩展方法的多目标增量启发式搜索系统.当问题搜索图中边的权重发生改变或添加删除节点时,该系统通过对搜索现场进行实时的更新,部分利用先前搜索保留的信息,从更新后的状态开始求解新的问题,从而提高了重搜索的效率.对gridworld标准测试样例进行了大量的系统测试,实验结果表明：结合增量与启发式搜索的处理方法能够有效地解决状态格局不断变化的一系列相似的多目标最短路径问题.     

Solving the uncapacitated facility location problem using tabu search

A tabu search heuristic procedure is developed to solve the uncapacitated facility location problem. Tabu search is used to guide the solution process when evolving from one solution to another. A move is defined to be the opening or closing of a facility. The net cost change resulting from a candidate move is used to measure the attractiveness of the move. After a move is made, the net cost change of a candidate move is updated from its old value. Updating, rather than re-computing, the net cost changes substantially reduces computation time needed to solve a problem when the problem is not excessively large. Searching only a small subset of the feasible solutions that contains the optimal solution, the procedure is computationally very efficient. A computational experiment is conducted to test the performance of the procedure and computational results are reported. The procedure can easily find optimal or near optimal solutions for benchmark test problems from the literature. For randomly generated test problems, this tabu search procedure not only obtained solutions completely dominating those obtained with other heuristic methods recently published in the literature but also used substantially less computation time. Therefore, this tabu search procedure has advantage over other heuristic methods in both solution quality and computation speed.     

A heuristic and a branch-and-bound algorithm for the Assembly Line Worker Assignment and Balancing Problem

In traditional assembly lines, it is reasonable to assume that task execution times are the same for each worker. However, in Sheltered Work Centres for Disabled this assumption is not valid: some workers may execute some tasks considerably slower or even be incapable of executing them. Worker heterogeneity leads to a problem called the Assembly Line Worker Assignment and Balancing Problem (ALWABP). For a fixed number of workers the problem is to maximize the production rate of an assembly line by assigning workers to stations and tasks to workers, while satisfying precedence constraints between the tasks.This paper introduces new heuristic and exact methods to solve this problem. We present a new MIP model, propose a novel heuristic algorithm based on beam search, as well as a task-oriented branch-and-bound procedure which uses new reduction rules and lower bounds for solving the problem. Extensive computational tests on a large set of instances show that these methods are effective and improve over existing ones.     

Minimizing total tardiness and earliness on unrelated parallel machines with controllable processing times

Job scheduling has always been a challenging task in modern manufacturing and the most real life scheduling problems which involves multi-criteria and multi-machine environments. In this research our direction is largely motivated by the adoption of the Just-In-Time (JIT) philosophy in parallel machines system, where processing times of jobs are controllable. The goal of this paper is to minimize total weighted tardiness and earliness besides jobs compressing and expanding costs, depending on the amount of compression/expansion as well as maximum completion time called makespan simultaneously. Jobs due dates are distinct and no inserted idle time is allowed after starting machine processing. Also each machine is capable of processing only some predetermined jobs and operations with probably different speeds. A Mixed Integer Programming (MIP) model is proposed to formulate such a problem and is solved optimally in small size instances. A Parallel Net Benefit Compression-Net Benefit Expansion (PNBC–NBE) heuristic is then presented to acquire the optimal jobs set amount of compression and expansion processing times in a given sequence. To solve medium-to-large size cases, a proposed heuristic, two meta-heuristics and a hybrid technique are also employed. Experimental results demonstrate that our hybrid procedure is a proficient method and could efficiently solve such complicated problems.     

Observations on using genetic-algorithms for channel allocation in mobile computing

This paper highlights the potential of using genetic algorithms to solve cellular resource allocation problems. The objective in this work is to gauge how well a GA-based channel borrower performs when compared to a greedy borrowing heuristic. This is needed to establish how suited GA-like (stochastic search) algorithms are for the solution of optimization problems in mobile computing environments. This involves the creation of a simple mobile networking resource environment and design of a GA-based channel borrower that works within this environment. A simulation environment is also built to compare the performance of the GA-based channel-borrowing method with the heuristic. To enhance the performance of the GA, extra attention is paid to developing an improved mutation operator. The performance of the new operator is evaluated against the heuristic borrowing scheme. For a real-time implementation, the GA needs to have the properties of a micro GA strategy. This involves making improvements to the crossover operator and evaluation procedure so the GA can converge to a "good" solution rapidly.     

Forward recursive scheme with improved marginal analysis heuristic for machine expansion scheduling in a new job shop

This study attempts to develop a method of machine expansion scheduling which determines how many machines should be purchased and allocated to every workstation during each period within the prescheduled ramp-up planning horizon in a new job shop to meet expected performance targets and minimize investment in machinery. This study suggests using the forward recursive scheme associated with marginal analysis heuristic, which itself is characterized by inherent simplicity and broad applicability, to solve the intricate problems of machine expansion scheduling. Furthermore, this study improves the marginal analysis heuristic, meaning that the algorithm incorporates an additional refining procedure to increase the possibility of achieving a solution close to the real optimum. Finally, this study used production data from an actual semiconductor manufacturer as an example to illustrate the proposed analytic algorithm.     

Fusing ant colony optimization with Lagrangian relaxation for the multiple-choice multidimensional knapsack problem

The multiple-choice multidimensional knapsack problem (MMKP) concerns a wide variety of practical problems. It is strongly constrained and NP-hard; thus searching for an efficient heuristic approach for MMKP is of great significance. In this study, we attempt to solve MMKP by fusing ant colony optimization (ACO) with Lagrangian relaxation (LR). The algorithm used here follows the algorithmic scheme of max–min ant system for its outstanding performance in solving many other combinatorial optimization problems. The Lagrangian value of the item in MMKP, obtained from LR, is used as the heuristic factor in ACO since it performs best among the six domain-based heuristic factors we define. Furthermore, a novel infeasibility index is proposed for the development of a new repair operator, which converts possibly infeasible solutions into feasible ones. The proposed algorithm was compared with four existing algorithms by applying them to three groups of instances. Computational results demonstrate that the proposed algorithm is capable of producing competitive solutions.     

Frequency reassignment problem in mobile communication networks

In this paper, we present a new frequency reassignment problem (FP) arising from the installation of new base stations for capacity expansion of a mobile telecommunication network, and develop two mathematical formulations along with some valid inequalities. Also, we develop a novel decomposition based heuristic procedure for solving large size problems. Computational results show that the developed valid inequalities are quite strong, and the developed heuristic procedure finds an optimal solution to the most test problems within reasonable time bound.     

一种有效的任务分配算法

本文针对非均质问题,在TRANCUBE多处理机系统上利用图匹配中的启发式方法,提出一种新的任务分配算法.该算法不仅简单,而且效率高.     

A hybrid heuristic for the overlapping cluster editing problem

Clustering problems are applicable to several areas of science. Approaches and algorithms are as varied as the applications. From a graph theory perspective, clustering can be generated by partitioning an input graph into a vertex-disjoint union of cliques (clusters) through addition and deletion of edges. Finding the minimum number of edges additions and deletions required to cluster data that can be represented as graphs is a well-known problem in combinatorial optimization, often referred to as cluster editing problem. However, many real-world clustering applications are characterized by overlapping clusters, that is, clusters that are non-disjoint. In these situations cluster editing cannot be applied to these problems. Literature concerning a relaxation of the cluster editing, where clusters can overlap, is scarce. In this work, we propose the overlapping cluster editing problem, a variation of the cluster editing where the goal is to partition a graph, also by editing edges, into maximal cliques that are not necessarily disjoint. In addition, we also present three slightly different versions of a hybrid heuristic to solve this problem. Each hybrid heuristic is based on coupling two metaheuristicsthat, together, generate a set of clusters; and one of three mixed-integer linear programming models, also introduced in this paper, that uses these clusters as input. The objective with the metaheuristics is to limit the solution exploration space in the models’ resolution, therefore reducing its computational time.Tests results show that the all proposed hybrid heuristic versions are able to generate good-quality overlapping cluster editing solutions. In particular, one version of the hybrid heuristic achieved, at a low computational cost, the best results in 51 of 112 randomly-generated graphs. Although the other two hybrid heuristic versions have harder to solve models, they obtained reasonable results in medium-sized randomly-generated graphs. In addition, the hybrid heuristic achieved good results identifying labeled overlapping clusters in a supervised data set experiment. Furthermore, we also show that, with our new problem definition, clustering a vertex in more than one cluster can reduce the edges editing cost.     

A controlled genetic algorithm by fuzzy logic and belief functionsfor job-shop scheduling

Most scheduling problems are highly complex combinatorial problems. However, stochastic methods such as genetic algorithm yield good solutions. In this paper, we present a controlled genetic algorithm (CGA) based on fuzzy logic and belief functions to solve job-shop scheduling problems. For better performance, we propose an efficient representational scheme, heuristic rules for creating the initial population, and a new methodology for mixing and computing genetic operator probabilities.     

An improved heuristic for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is an important and practical problem in the OR literature. In short, the problem is to identify routes to service (e.g., pickup or deliver) demand located along the edges of a network such that the total cost of the routes is minimized. In general, a single route cannot satisfy the entire demand due to capacity constraints on the vehicles. CARP belongs to the set of NP-hard problems; consequently numerous heuristic and metaheuristic solution approaches have been developed to solve it. In this paper an “ellipse rule” based heuristic is proposed for the CARP. This approach is based on the path-scanning heuristic, one of the mostly used greedy-add heuristics for this problem. The innovation consists basically of selecting edges only inside ellipses when the vehicle is near the end of each route. This new approach was implemented and tested on three standard datasets and the solutions are compared against: (i) the original path-scanning heuristic; (ii) two other path-scanning heuristics and (iii) the three best known metaheuristics. The results indicate that the “ellipse rule” approach lead to improvements over the three path-scanning heuristics, reducing the average distance to the lower bound in the test problems by about 44%.     

A modified simple heuristic for the p-median problem, with facilities design applications

Facilities design is closely related to efficient use of available resources. This paper presents a heuristic approach to solve two core problems of a good facilities design: facility location and facility layout. The latter group of problems will be solved for warehouse and production systems in particular. All these problems can be formulated as p-median clustering problems. Teitz and Bart (Oper. Res. 16 (1968) 955–961) developed the vertex substitution method to solve those problems. This paper introduces effective improvements on this heuristic. The approach is tested on a large number of randomly generated cases and on problems taken from the literature. The results demonstrate the effectiveness and superiority of our method.