A graph coloring approach for image segmentation

In this paper we develop a segmentation scheme for digital images based upon an iterative binary coloring technique that takes into account changing behavior of adjacent pixels. The output is a hierarchical structure of images which allows a better understanding of complex images. In particular, we propose two algorithms that should be considered as image preprocessing techniques.     

Multi-objective optimization in partitioning the healthcare system of Parana State in Brazil

Motivated by a proposal of the local authority for improving the existing healthcare system in the Parana State in Brazil, this article presents an optimization-based model for developing a better system for patients by aggregating various health services offered in the municipalities of Parana into some microregions. The problem is formulated as a multi-objective partitioning of the nodes of an undirected graph (or network) with the municipalities as the nodes and the roads connecting them as the edges of the graph. Maximizing the population homogeneity in the microregions, maximizing the variety of medical procedures offered in the microregions, and minimizing the inter-microregion distances to be traveled by patients are considered as three objective functions of the problem. An integer-coded multi-objective genetic algorithm is adopted as the optimization tool, which yields a significant improvement to the existing healthcare system map of the Parana State. The results obtained may have a strong impact on the healthcare system management in Parana. The model proposed here could be a useful tool to aid the decision-making in health management, as well as for better organization of any healthcare system, including those of other Brazilian States.     

On edge orienting methods for graph coloring

We consider the problem of orienting the edges of a graph so that the length of a longest path in the resulting digraph is minimum. As shown by Gallai, Roy and Vitaver, this edge orienting problem is equivalent to finding the chromatic number of a graph. We study various properties of edge orienting methods in the context of local search for graph coloring. We then exploit these properties to derive four tabu search algorithms, each based on a different neighborhood. We compare these algorithms numerically to determine which are the most promising and to give potential research directions.     

An efficient approach for searching optimal multi-keywords coverage routes

Journal of Combinatorial Optimization - Keyword-aware optimal route queries are a combinatorial optimization problem with three factors, namely keyword coverage, route budget constraint and route...     

随机动态装卸混合问题的分区求解策略

针对需求服从一般分布的随机动态装卸混合问题,提出一种求解该问题的分区求解策略,分析了需求稀少和需求密集情况下该策略的渐近性.仿真比较了需求服从一般分布情形下分区求解策略、随机队列中位策略、多车场随机队列中位策略和堆栈策略的求解效果,以及需求服从一般分布和需求服从均匀分布情形下分区求解策略的求解效果.结果表明,对于需求服从一般分布的随机动态装卸混合问题,分区求解策略是一种有效的求解策略.     

An unexpected meeting of four seemingly unrelated problems: graph testing, DNA complex screening, superimposed codes and secure key distribution

This paper discusses the relation among four problems: graph testing, DNA complex screening, superimposed codes and secure key distribution. We prove a surprising equivalence relation among these four problems, and use this equivalence to improve current results on graph testing. In the rest of this paper, we give a lower bound for the minimum number of tests on DNA complex screening model. The first and second author would like to dedicate this paper to professor Frank K. Hwang on the occasion of his 65th birthday. This research is partially supported by Republic of China, National Science Council grant NSC 92-2115-M-009-014.     

一种改进的TSP问题启发式算法

旅行推销商问题(TSP)属于组合优化领域中一个典型的NP Hard问题。本文在最近城市搜索法的基础上,提出一种改进的启发式算法———两端延伸最近城市搜索法,这种方法能够很快得到最优解(近优解),且大大降低了计算复杂度。同时,对TSP问题进行了分类,并给出相应的启发式解法。     

An online algorithm for continuous slab caster scheduling

Lee et al. (Lee, K., Chang, S.Y., and Hong, Y., 2004. Continuous slab caster scheduling and interval graphs. Production Planning & Control, 13 (5), 495–501) have introduced a slab caster scheduling problem and developed an optimal algorithm. Their algorithm is efficient but an offline algorithm that we need the information on all the customer orders a priori to implement. In this article, we propose an online algorithm that we can implement without knowledge of the orders yet to arrive. We show that the offline version of our new algorithm also provides an optimal solution and the online version has the worst case performance ratio of 3. We also give a short proof on the correctness of Lee et al.'s algorithm.     

An integrated strategy for a production planning and warehouse layout problem: Modeling and solution approaches

We study a real-world production warehousing case, where the company always faces the challenge to find available space for its products and to manage the items in the warehouse. To resolve the problem, an integrated strategy that combines warehouse layout with the capacitated lot-sizing problem is presented, which have been traditionally treated separately in the existing literature. We develop a mixed integer linear programming model to formulate the integrated optimization problem with the objective of minimizing the total cost of production and warehouse operations. The problem with real data is a large-scale instance that is beyond the capability of optimization solvers. A novel Lagrangian relax-and-fix heuristic approach and its variants are proposed to solve the large-scale problem. The preliminary numerical results from the heuristic approaches are reported.     

大规模邻域搜索算法求解时变车辆调度问题

对时变网络车辆调度问题提出一种满足先入先出准则的时变处理方法,并建立相应的数学模型,提出一种基于大规模邻域搜索技术的智能优化算法进行求解,算法顶层采用动态规划算法搜索环状交换邻域以得到每辆车的最佳服务顾客集合;底层设计动态搜索算法用以安排每辆车的最佳服务路线.在此基础上提出顶层加入虚拟顾客和底层嵌入insert两类改进策略.通过实验仿真比较,验证了所提算法的有效性.     

An efficient generalized network-simplex-based algorithm for manufacturing network flows

Fang and Qi (Optim. Methods Softw. 18:143–165, 2003) introduced a new generalized network flow model called manufacturing network flow model for manufacturing process modeling. A key distinguishing feature of such models is the assembling of component raw-materials, in a given proportion, into an end-product. This assembling operation cannot be modeled using usual generalized networks (which allow gains and losses in flows), or using multi-commodity networks (which allow flows of multiple commodity types on a single arc). The authors developed a network-simplex-based algorithm to solve a minimum cost flow problem formulated on such a generalized network and indicated systems of linear equations that need to be solved during the course of the network-simplex-based solution procedure. In this paper, it is first shown how various steps of the network-simplex-based solution procedure can be performed efficiently using appropriate data structures. Further, it is also shown how the resulting system of linear equations can be solved directly on the generalized network.     

A mathematical model and genetic algorithm-based approach for parallel two-sided assembly line balancing problem

Assembly lines are usually constructed as the last stage of the entire production system and efficiency of an assembly line is one of the most important factors which affect the performance of a complex production system. The main purpose of this paper is to mathematically formulate and to provide an insight for modelling the parallel two-sided assembly line balancing problem, where two or more two-sided assembly lines are constructed in parallel to each other. We also propose a new genetic algorithm (GA)-based approach in alternatively to the existing only solution approach in the literature, which is a tabu search algorithm. To the best of our knowledge, this is the first formal presentation of the problem as well as the proposed algorithm is the first attempt to solve the problem with a GA-based approach in the literature. The proposed approach is illustrated with an example to explain the procedures of the algorithm. Test problems are solved and promising results are obtained. Statistical tests are designed to analyse the advantage of line parallelisation in two-sided assembly lines through obtained test results. The response of the overall system to the changes in the cycle times of the parallel lines is also analysed through test problems for the first time in the literature.     

An immune algorithm with stochastic aging and kullback entropy for the chromatic number problem

We present a new Immune Algorithm, IMMALG, that incorporates a Stochastic Aging operator and a simple local search procedure to improve the overall performances in tackling the chromatic number problem (CNP) instances. We characterize the algorithm and set its parameters in terms of Kullback Entropy. Experiments will show that the IA we propose is very competitive with the state-of-art evolutionary algorithms.     

An Approach for Balancing Health and Ecological Risks at Hazardous Waste Sites

Human health and ecological risks must be balanced at hazardous waste sites in order to ensure that remedial actions prevent unacceptable risks of either type. Actions that are designed to protect humans may fail to protect nonhuman populations and ecosystems or may damage ecosystems. However, there is no common scale of health and ecological risk that would allow comparisons to be performed. This paper presents an approach to addressing this problem based on classifying all risks (i.e., health and ecological risks due contaminants and remediation) as insignificant ( de minimis ), highly significant ( de manifestis ), or intermediate. For health risks the classification is based on standard criteria. However, in the absence of national guidance concerning the acceptability of ecological risks, new ecological criteria are proposed based on an analysis of regulatory precedents. Matrices and flow charts are presented to guide the use of these risk categories in remedial decision making. The assessment of mercury contamination of the East Fork Poplar Creek is presented as an example of the implementation of the approach.     

An efficient tabu search algorithm for the single- machine mean tardiness problem

In this paper, an efficient tabu search algorithm is prepared for solving the single-machine mean tardiness problem. The proposed implementation of the tabu search approach suggests simple techniques for generating neighbourhoods of a given sequence and a combined scheme for intensification and diversification. The tabu search method is shown to produce results very close to the optimal solution using randomly generated problems with varying degrees of difficulty.     

一种求解时变条件下有宵禁限制最短路的算法

在组合优化过程中,往往需要获得从起点到终点之间的最短路.由于道路、天气、交通条件等因素的影响,使得网络具有很强的时变特性.同时,对于网络中的节点往往有宵禁的限制.对时变条件下有宵禁限制并有到达时间限制的最短路进行了研究,建立了软、硬宵禁限制下的数学模型,给出并证明了时变条件下获得有宵禁限制最短路的最优条件,并设计了求解的多项式算法,通过此算法可以获得时变条件下有宵禁限制的最短路.同时,算法和模型还考虑了不同的起点出发时间,使路径决策者可以根据自身的情况,选择合适的出发时间和路径.最后给出了一个应用算例,分析了宵禁对于获得的最短路的影响.     

An efficient scheduling algorithm for the hot coil making in the steel mini-mill

This paper investigates and suggests an efficient solution to the problem of scheduling the steel making line in the Mini Steel Mill, which consists of three major processes: molten steel making, continuous slab casting, and hot charged rolling. Careful synchronization of these processes is a key productivity factor, since a very limited amount of work-in-process inventory is allowed. Since each process must run in batch, the schedule for the Mini-Mill consists of grouping and sequencing of lots for each process. However, each process has its own criteria for judging the quality of its lot grouping, which often conflicts with other processes. An efficient scheduling algorithm for the Mini-Mill is proposed. Numerical experiments with real world data suggest that the proposed algorithm yield satisfactory schedules very efficiently. The algorithm is currently used for the actual scheduling of a Mini-Mill in Korea.     

An integrated approach for the electronic contract manufacturer selection problem

In the global competitive environment, lead companies have to outsource their manufacturing to electronic contract manufacturers (ECM) in order to reduce operational cost and capture higher profit. Thus, the process of selecting contract manufacturers to be strategic partners is important for these companies. For this reason, this paper proposes an integrated approach for the electronic contract manufacturer selection problem, combining the voting method and the goal programming (GP) model to take into account quantitative factors involved in the selection process, which is applied to a real-world ECM selection problem encountered by a leading provider of complete broadband access solutions. Results of the case study indicate that the voting method can acquire the rating information quickly from manufacturing managers based on suitable evaluating criteria. The rating information simultaneously incorporates ECMs' performance scores as a weight for each ECM. A production planner can easily employ the GP model and ECMs’ weight information to effectively assign demand quantities to ECMs. Therefore, the integrated approach is a practical and useful tool for solving the contract manufacturer selection problem.     

An exact approach for the balanced <Emphasis Type="Italic">k</Emphasis>-way partitioning problem with weight constraints and its application to sports team realignment

In this work a balanced k-way partitioning problem with weight constraints is defined to model the sports team realignment. Sports teams must be partitioned into a fixed number of groups according to some regulations, where the total distance of the road trips that all teams must travel to play a double round robin tournament in each group is minimized. Two integer programming formulations for this problem are introduced, and the validity of three families of inequalities associated to the polytope of these formulations is proved. The performance of a tabu search procedure and a branch and cut algorithm, which uses the valid inequalities as cuts, is evaluated over simulated and real-world instances. In particular, an optimal solution for the realignment of the Ecuadorian football league is reported and the methodology can be suitable adapted for the realignment of other sports leagues.     

An integrated closed-loop product lifecycle management approach for reverse logistics design

Nowadays, reverse logistics is gaining importance for many companies in different industries. This importance is rooted in the fact that it generates profit and decreases the environmental impacts of products. Even though the decrease of environmental impacts is an indispensable requisite, reverse logistics design is only driven by cost indicators. The main reason behind this high cost is access to environmental information is difficult and is directly linked to data all along the lifecycle of the product. This paper presents a method by which reverse logistics design integrates environmental impacts based on the management of closed-loop product lifecycle. This method is divided into two processes: from beginning of life to end of life and from end of life to beginning of life. The first process integrates product data in order to calculate environmental impacts of the potential reverse logistics networks, whereas the second process selects the most appropriate reverse logistics network before optimising the product based on this particular network. The proposition is illustrated by a case study on a recycled aluminium automotive part.