Search

Abstract: Power efficiency is one of the major considerations in the current hardware/software co-designs. This paper models hardware/software partitioning as an optimization problem with objective of minimizing power consumption under the constraints: hardware area and execution time . An efficient heuristic algorithm with running time is proposed for the quality approximate solutions of the problems with n code fragments. Also, an exact algorithm based on dynamic programming is presented to produce the optimal solution in . The optimal solution for small-sized problems is used to evaluate the performance of the approximate solution. The approximate solutions are compared experimentally with the optimal solutions in our empirical study. The average errors of the approximate solutions is less than for the cases simulated in this paper. [Copyright &y& Elsevier]

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.11.015 Byline: Manuel Lopez-IbaA[+ or -]ez (a), Christian Blum (b) Abstract: The travelling salesman problem with time windows is a difficult optimization problem that arises, for example, in logistics. This paper deals with the minimization of the travel-cost. For solving this problem, this paper proposes a Beam-ACO algorithm, which is a hybrid method combining ant colony optimization with beam search. In general, Beam-ACO algorithms heavily rely on accurate and computationally inexpensive bounding information for differentiating between partial solutions. This work uses stochastic sampling as a useful alternative. An extensive experimental evaluation on seven benchmark sets from the literature shows that the proposed Beam-ACO algorithm is currently a state-of-the-art technique for the travelling salesman problem with time windows when travel-cost optimization is concerned. Author Affiliation: (a) IRIDIA, CoDE, Universite Libre de Bruxelles, Brussels, Belgium (b) ALBCOM Research Group, Universitat Politecnica de Catalunya, Barcelona, Spain Article Note: (footnote) [star] This work was supported by Grant TIN2007-66523 (FORMALISM) of the Spanish government. Moreover, Christian Blum acknowledges support from the Ramon y Cajal program of the Spanish Ministry of Science and Innovation.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2008.11.008 Byline: Ranjan Kumar, Kazuhiro Izui, Masataka Yoshimura, Shinji Nishiwaki Keywords: Redundancy allocation; Multilevel series system; Multilevel series-parallel; Modular redundancy; Component redundancy; Genetic algorithms Abstract: To achieve truly optimal system reliability, the design of a complex system must address multilevel reliability configuration concerns at the earliest possible design stage, to ensure that appropriate degrees of reliability are allocated to every unit at all levels. However, the current practice of allocating reliability at a single level leads to inferior optimal solutions, particularly in the class of multilevel redundancy allocation problems. Multilevel redundancy allocation optimization problems frequently occur in optimizing the system reliability of multilevel systems. It has been found that a modular scheme of redundancy allocation in multilevel systems not only enhances system reliability but also provides fault tolerance to the optimum design. Therefore, to increase the efficiency, reliability and maintainability of a multilevel reliability system, the design engineer has to shift away from the traditional focus on component redundancy, and deal more effectively with issues pertaining to modular redundancy. This paper proposes a method for optimizing modular redundancy allocation in two types of multilevel reliability configurations, series and series-parallel. A modular design variable is defined to handle modular redundancy in these two types of multilevel redundancy allocation problem. A customized genetic algorithm, namely, a hierarchical genetic algorithm (HGA), is applied to solve the modular redundancy allocation optimization problems, in which the design variables are coded as hierarchical genotypes. These hierarchical genotypes are represented by two nodal genotypes, ordinal and terminal. Using these two genotypes is extremely effective, since this allows representation of all possible modular configurations. The numerical examples solved in this paper demonstrate the efficacy of a customized HGA in optimizing the multilevel system reliability. Additionally, the results obtained in this paper indicate that achieving modular redundancy in series and series-parallel systems provides significant advantages when compared with component redundancy. The demonstrated methodology also indicates that future research may yield significantly better solutions to the technological challenges of designing more fault-tolerant systems that provide improved reliability and lower lifecycle cost. Author Affiliation: Department of Aeronautics and Astronautics, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto 606-8501, Japan Article History: Received 21 November 2007; Revised 11 June 2008; Accepted 4 November 2008 Article Note: (footnote) [star] This manuscript was processed by Area Editor E.A. Elsayed.

Very recently, Pan et al. [Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO07, pp. 126-33] presented a new and novel discrete differential evolution algorithm for the permutation flowshop scheduling problem with the makespan criterion. On the other hand, the iterated greedy algorithm is proposed by [Ruiz, R., & Stutzle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033-49] for the permutation flowshop scheduling problem with the makespan criterion. However, both algorithms are not applied to the permutation flowshop scheduling problem with the total flowtime criterion. Based on their excellent performance with the makespan criterion, we extend both algorithms in this paper to the total flowtime objective. Furthermore, we propose a new and novel referenced local search procedure hybridized with both algorithms to further improve the solution quality. The referenced local search exploits the space based on reference positions taken from a reference solution in the hope of finding better positions for jobs when performing insertion operation. Computational results show that both algorithms with the referenced local search are either better or highly competitive to all the existing approaches in the literature for both objectives of makespan and total flowtime. Especially for the total flowtime criterion, their performance is superior to the particle swarm optimization algorithms proposed by [Tasgetiren, M. F., Liang, Y. -C., Sevkli, M., Gencyilmaz, G. (2007). Particle swarm optimization algorithm for makespan and total flowtime minimization in permutation flowshop sequencing problem. European Journal of Operational Research, 177(3), 1930-47] and [Jarboui, B., Ibrahim, S., Siarry. P., Rebai, A. (2007). A combinatorial particle swarm optimisation for solving permutation flowshop problems. Computers & Industrial Engineering, doi: 10.1016/j.cie.2007.09.006]. Ultimately, for Taillard's benchmark suite, four best known solutions for the makespan criterion as well as 40 out of the 90 best known solutions for the total flowtime criterion are further improved by either one of the algorithms presented in this paper. Keywords: Permutation flowshop Scheduling Iterated greedy algorithm Discrete differential evolution algorithm Discrete particle swarm optimization Referenced local search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2007.12.008 Byline: Mircea AncAu Keywords: Printed circuit board; Optimization; TSP; Heuristic; Monte Carlo Abstract: With the rapid growth of printed circuit board technology today, board density is becoming an important concern. In every aspect of production, productivity and cost are crucial matters. The aim of this research is the optimization of printed circuit board manufacturing by improving the process productivity. Attention was focused on reducing tool path length and processing time. The paper is divided in two main parts. First part presents an original hybrid heuristic algorithm, for solving traveling salesman problem. The algorithm is based on the structure of a general optimization procedure, and is used to reduce the tool path length. Also, it is developed a practical mathematical model for printed circuit board processing time calculation. The case study on the second part of the paper shows basically the efficient use of the above algorithm in finding the optimal length of the tool path. It is shown the influence of stacked printed circuit board on process productivity. By means of its concepts management, the paper represent a real guide for optimal design of printed circuit board drilling technology. Author Affiliation: Technical University of Cluj-Napoca, Faculty of Machine Building, Department of Manufacturing, B-dul Muncii 103-105, 400641 Cluj-Napoca, Romania Article History: Received 20 July 2006; Revised 26 October 2007; Accepted 11 December 2007

Establishing the neighbor list to efficiently calculate the inter-atomic forces consumes the majority of computation time in molecular dynamics (MD) simulation. Several algorithms have been proposed to improve the computation efficiency for short-range interaction in recent years, although an optimized numerical algorithm has not been provided. Based on a rigorous definition of Verlet radius with respect to temperature and list-updating interval in MD simulation, this paper has successfully developed an estimation formula of the computation time for each MD algorithm calculation so as to find an optimized performance for each algorithm. With the formula proposed here, the best algorithm can be chosen based on different total number of atoms, system average density and system average temperature for the MD simulation. It has been shown that the Verlet Cell-linked List (VCL) algorithm is better than other algorithms for a system with a large number of atoms. Furthermore, a generalized VCL algorithm optimized with a list-updating interval and cell-dividing number is analyzed and has been verified to reduce the computation time by in a MD simulation for a two-dimensional lattice system. Due to similarity, the analysis in this study can be extended to other many-particle systems. [Copyright &y& Elsevier]

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ijpe.2010.07.020 Byline: Anna Nagurney Abstract: In this paper, we propose a framework for supply chain network design and redesign that allows for the determination of the optimal levels of capacity and operational product flows associated with supply chain activities of manufacturing, storage, and distribution at minimal total cost and subject to the satisfaction of product demands. We formulate both the design and redesign problems as variational inequalities and show that the same algorithm, which exploits the underlying network structure, can be used for the solution of either problem. We illustrate the new framework with numerical examples that demonstrate the practicality and flexibility of the approach. Author Affiliation: Department of Finance and Operations Management, Isenberg School of Management, University of Massachusetts, Amherst, MA 01003, USA Article History: Received 11 July 2009; Accepted 14 July 2010

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2010.08.019 Byline: E. Trovato (a), P. Castagliola (b), G. Celano (c), S. Fichera (c) Keywords: Short production run; Process dispersion; Statistical process control; Control charts; Cost minimization Abstract: Short-run productions are common in industrial environments where flexibility is required in the manufacturing of parts and several product variants can be produced. Monitoring process stability during the production run is strategic to avoid the occurrence of an excessive number of non conforming units which can lead to excessive scrap or rework costs. The selection of the best control strategy can be obtained with respect to an economic objective by minimizing the cost associated with the implementation strategy. In this paper, several strategies including preventive maintenance, Shewhart, EWMA and CUSUM control charts are compared to monitor process dispersion. Constraints related to the line productivity and the inspection activities configuration have been included in the problem formulation. A proper optimization algorithm has been developed to cope with the investigated problem. A large benchmark of process scenarios has been investigated and the obtained results show that the selection of the best strategy is not a straightforward task due to the influence of several process operating parameters. Finally, a numerical example is detailed to get more insight about the investigated problem. Author Affiliation: (a) Ecole des Mines de Nantes, Nantes, France (b) Universite de Nantes & IRCCyN UMR CNRS 6597, Nantes, France (c) Dipartimento di Ingegneria Industriale e Meccanica, Universita di Catania, Catania, Italy Article History: Received 24 November 2009; Revised 28 July 2010; Accepted 30 August 2010 Article Note: (footnote) [star] This manuscript was processed by Area Editor E.A. Elsayed.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2010.06.009 Byline: Jingfa Liu (a), Gang Li (b), Duanbing Chen (c), Wenjie Liu (a), Yali Wang (d) Keywords: Packing problem; Equilibrium constraint; Layout optimization; Simulated annealing Abstract: This paper studies the layout optimization problem with equilibrium constraint. It is a two-dimensional packing problem with the industrial background of simplified satellite module layout design, and is known as NP-hard problem. By incorporating the heuristic neighborhood search mechanism and the adaptive gradient method into the simulated annealing procedure, a heuristic simulated annealing algorithm is put forward for this problem. The special neighborhood search mechanism can avoid the disadvantage of blind search in the simulated annealing algorithm, and the adaptive gradient method is used to execute local search and speed up finding the global optimal solution. Numerical examples are illustrated to verify the effectiveness of the proposed algorithm. Author Affiliation: (a) School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044, China (b) School of Mathematics and Physics, Nanjing University of Information Science and Technology, Nanjing 210044, China (c) School of Computer Science, University of Electronic Science and Technology of China, Chengdu 610054, China (d) School of Electronic and Information Engineering, Nanjing University of Information Science and Technology, Nanjing 210044, China Article History: Received 20 November 2009; Revised 16 June 2010; Accepted 16 June 2010

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ijpe.2010.05.003 Byline: Lin-Yu Tseng (a)(b), Ya-Tai Lin (b) Keywords: Genetic algorithm; Tabu search; Flowshop scheduling; Total flowtime; Genetic local search Abstract: Recently, the flowshop scheduling problem to minimize total flowtime has attracted more attention from researchers. In this paper, a genetic local search algorithm is proposed to solve this problem. The proposed algorithm hybridizes the genetic algorithm and the tabu search. It employs the genetic algorithm to do the global search and the tabu search to do the local search. The orthogonal-array-based crossover is utilized to enhance the capability of intensification. Also, a novel orthogonal-array-based mutation is proposed, in order to add capability of intensification to the traditional mutation operator. The performance of the proposed genetic local search algorithm is very competitive. It improved 54 out of 90 current best solutions reported in the literature for short-term search, and it also improved 18 out of 20 current best solutions reported in the literature for long-term search. Author Affiliation: (a) Institute of Networking and Multimedia, National Chung Hsing University, 250 Kuo Kuang Road, Taichung, Taiwan (b) Department of Computer Science and Engineering, National Chung Hsing University, 250 Kuo Kuang Road, Taichung, Taiwan Article History: Received 16 April 2007; Accepted 23 April 2010

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.06.017 Byline: Feng Pan, Rakesh Nagi Abstract: This paper considers a supply chain design problem for a new market opportunity with uncertain demand in an agile manufacturing setting. We consider the integrated optimization of logistics and production costs associated with the supply chain members. These problems routinely occur in a wide variety of industries including semiconductor manufacturing, multi-tier automotive supply chains, and consumer appliances to name a few. There are two types of decision variables: binary variables for selection of companies to form the supply chain and continuous variables associated with production planning. A scenario approach is used to handle the uncertainty of demand. The formulation is a robust optimization model with three components in the objective function: expected total costs, cost variability due to demand uncertainty, and expected penalty for demand unmet at the end of the planning horizon. The increase of computational time with the numbers of echelons and members per echelon necessitates a heuristic. A heuristic based on a k-shortest path algorithm is developed by using a surrogate distance to denote the effectiveness of each member in the supply chain. The heuristic can find an optimal solution very quickly in some small- and medium-size cases. For large problems, a "good" solution with a small gap relative to our lower bound is obtained in a short computational time. Author Affiliation: Department of Industrial and Systems Engineering, University at Buffalo (SUNY), Buffalo, NY 14260, USA

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.06.016 Byline: Y. Massim (a), F. Yalaoui (b), L. Amodeo (b), E. Chatelet (c), A. Zeblah (a) Keywords: Buffers; Average throughput; Work inventory; Optimization; Artificial immune system; Decomposition method Abstract: Adequate allocation of buffers in transfer lines is crucial to the optimization of line throughput and work in process (WIP) inventory. Their optimal allocation is subject to specific constraints, associated costs, and revenue projections. In this paper, we implement a combined artificial immune system optimization algorithm in conjunction with a decomposition method to optimally allocate buffers in transfer lines. The aim of the buffer allocation problem (BAP) is to achieve optimal system performance under buffers space constraints. Maximizing line throughput does not necessarily achieve maximum profit. In this study the immune decomposition algorithm (IDA) is used to determine optimal buffer allocation for maximum line throughput and maximum line economic profit. Results of extensive series of tests carried out to compare, in production lines with different characteristics, the performances of the proposed method and those of other algorithms are presented. Author Affiliation: (a) University of Sidi Bel Abbes, BP 89 Gumbeta, 22000 Sidi Bel Abbes, Algeria (b) Institut Charles Delaunay (CNRS FRE 2848), LOSI, University of Technology of Troyes, Troyes, 12 rue Marie Curie, Troyes Cedex, France (c) Institut Charles Delaunay (CNRS FRE 2848), LM2S, University of Technology of Troyes, Troyes, 12 rue Marie Curie, Troyes Cedex, France

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.08.006 Byline: Roberto Montemanni (a), Derek H. Smith (b) Abstract: Heuristic manipulation attempts to modify the search space of an optimization problem, using information provided by an underlying heuristic method. In this paper it is applied in combination with tabu search to the fixed spectrum frequency assignment problem. The frequency assignment problem involves the assignment of discrete channels (or frequencies) to the transmitters of a radio network, such as a mobile telephone network. Frequency separation is necessary to avoid interference by other transmitters to the signal received from the wanted transmitter at the reception points. Unnecessary separation causes an excess requirement for spectrum. Good assignments minimize interference and the spectrum required. In fixed spectrum frequency assignment the frequency spectrum available is given and the target is to minimize the interference in the network. Computational experiments confirm that the manipulation technique is able to drive the underlying tabu search algorithm towards improved solutions. Author Affiliation: (a) Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA), CH-6928 Manno, Switzerland (b) Division of Mathematics and Statistics, University of Glamorgan, Pontypridd, CF37 1DL Wales, UK

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.07.004 Byline: Antoniya Georgieva (a), Ivan Jordanov (b) Abstract: A hybrid novel meta-heuristic technique for bound-constrained global optimisation (GO) is proposed in this paper. We have developed an iterative algorithm called LPI Optimisation (LPIO) that uses low-discrepancy sequences of points and meta-heuristic knowledge to find regions of attraction when searching for a global minimum of an objective function. Subsequently, the well-known Nelder-Mead (NM) simplex local search is used to refine the solution found by the LPIO method. The combination of the two techniques (LPIO and NM) provides a powerful hybrid optimisation technique, which we call LPINM. Its properties -- applicability, convergence, consistency and stability are discussed here in detail. The LPINM is tested on a number of benchmark multimodal mathematical functions from 2 to 20 dimensions and compared with results from other stochastic heuristic methods. Author Affiliation: (a) Nuffield Department of Obstetrics and Gynaecology, John Radcliffe Hospital, Oxford University, OX3 9DU, UK (b) School of Computing, University of Portsmouth, PO1 3HE, UK

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.11.003 Byline: P.P. Repoussis (a), C.D. Tarantilis (a), O. Braysy (b), G. Ioannou (a) Abstract: This paper presents a hybrid evolution strategy (ES) for solving the open vehicle routing problem (OVRP), which is a well-known combinatorial optimization problem that addresses the service of a set of customers using a homogeneous fleet of non-depot returning capacitated vehicles. The objective is to minimize the fleet size and the distance traveled. The proposed solution method manipulates a population of [mu] individuals using a ([mu]+I')-ES; at each generation, a new intermediate population of I' offspring is produced via mutation, using arcs extracted from parent individuals. The selection and combination of arcs is dictated by a vector of strategy parameters. A multi-parent recombination operator enables the self-adaptation of the mutation rates based on the frequency of appearance of each arc and the diversity of the population. Finally, each new offspring is further improved via a memory-based trajectory local search algorithm, while an elitist scheme guides the selection of survivors. Experimental results on well-known benchmark data sets demonstrate the competitiveness of the proposed population-based hybrid metaheuristic algorithm. Author Affiliation: (a) Department of Management Science and Technology, Athens University of Economics and Business, Patision 76, GR10434 Athens, Greece (b) Agora Innoroad Laboratory, Agora Center, University of Jyvaskyla, P.O. Box 35, FI-40014, Finland

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2009.09.001 Byline: Gao-Ji Sun, Yan-Kui Liu, Yan-Fei Lan Keywords: Material procurement planning; Two-stage fuzzy programming; Minimum-risk criteria; Approximation approach; Particle swarm optimization Abstract: This paper presents a new class of two-stage fuzzy material procurement planning (MPP) models with minimum-risk criteria, in which the material demand, the spot market material unit price and the spot market material supply quantity are uncertain and assumed to be fuzzy variables with known possibility distributions. We formulate the two-stage MPP model with the objective of maximizing the credibility of the total material procurement costs less than a given allowable investment level, and the credibility can be regarded as the material procurement risk criteria in a fuzzy environment. Since the fuzzy material demand, the fuzzy spot market material unit price and the fuzzy spot market material supply quantity are usually continuous fuzzy variables with infinite supports, the proposed MPP model belongs to an infinite-dimensional optimization problem that cannot be solved directly. To avoid this difficulty, we apply an approximation approach (AA) to the proposed two-stage fuzzy MPP model, and turn it into an approximating finite-dimensional optimization one. The convergence about the objective function of the approximating two-stage MPP model to that of the original two-stage MPP one is also discussed. Since the exact analytical expression for the objective function in the approximating fuzzy MPP model is unavailable, and the approximating MPP model is a mixed-integer program that is neither linear nor convex, traditional optimization algorithms cannot be used to solve it. Therefore, we develop two heuristic algorithms to solve the approximating MPP model. The first is a particle swarm optimization (PSO) algorithm based on the AA, and the second is a hybrid PSO algorithm which based on the AA and a neural network (NN). Finally, we provide an actual optimization problem about the fuel procurement to compare the effectiveness of the designed algorithms. Author Affiliation: College of Mathematics and Computer Science, Hebei University, Baoding, 071002 Hebei, China Article History: Received 7 June 2008; Revised 2 May 2009; Accepted 2 September 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.04.011 Byline: Mohamed Ouzineb (a)(b), Mustapha Nourelfath (a)(c), Michel Gendreau (a)(b) Abstract: This paper develops an efficient heuristic to solve two typical combinatorial optimization problems frequently met when designing highly reliable systems. The first one is the redundancy allocation problem (RAP) of series-parallel binary-state systems. The design goal of the RAP is to select the optimal combination of elements and redundancy levels to maximize system reliability subject to the system budget and to the system weight. The second problem is the expansion-scheduling problem (ESP) of multi-state series-parallel systems. In this problem, the study period is divided into several stages. At each stage, the demand is represented as a piecewise cumulative load curve. During the system lifetime, the demand can increase and the total productivity may become insufficient to assume the demand. To increase the total system productivity, elements are added to the existing system. The objective in the ESP is to minimize the sum of costs of the investments over the study period while satisfying availability constraints at each stage. The heuristic approach developed to solve the RAP and the ESP is based on a combination of space partitioning, genetic algorithms (GA) and tabu search (TS). After dividing the search space into a set of disjoint subsets, this approach uses GA to select the subspaces, and applies TS to each selected subspace. Numerical results for the test problems from previous research are reported and compared. The results show the advantages of the proposed approach for solving both problems. Author Affiliation: (a) Interuniversity Research Center on Entreprise Networks, Logistics and Transportation (CIRRELT), Canada (b) Universite de Montreal, Departement d'informatique et de recherche operationnelle, Montreal (Qc.), Canada (c) Universite Laval, Faculty of Science and Engineering, Mechanical Engineering Department, Pavillon Adrien-Pouliot, Quebec (Qc.), Canada G1K 7P4

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.04.002 Byline: Fardin Ahmadizar (a), Mehdi Ghazanfari (b), Seyyed Mohammad Taghi Fatemi Ghomi (c) Keywords: Group shop scheduling problem; Random release dates; Random processing times; Makespan; Ant colony algorithm; Simulation Abstract: This paper deals with a stochastic group shop scheduling problem. The group shop scheduling problem is a general formulation that includes the other shop scheduling problems such as the flow shop, the job shop and the open shop scheduling problems. Both the release date of each job and the processing time of each job on each machine are random variables with known distributions. The objective is to find a job schedule which minimizes the expected makespan. First, the problem is formulated in a form of stochastic programming and then a lower bound on the expected makespan is proposed which may be used as a measure for evaluating the performance of a solution without simulating. To solve the stochastic problem efficiently, a simulation optimization approach is developed that is a hybrid of an ant colony optimization algorithm and a heuristic algorithm to generate good solutions and a discrete event simulation model to evaluate the expected makespan. The proposed approach is tested on instances where the random variables are normally, exponentially or uniformly distributed and gives promising results. Author Affiliation: (a) Department of Industrial Engineering, University of Kurdistan, Pasdaran Boulvard, Sanandaj, Iran (b) Department of Industrial Engineering, Iran University of Science and Technology, Narmak, Tehran 16846 13114, Iran (c) Department of Industrial Engineering, Amirkabir University of Technology, 424 Hafez Avenue, Tehran, Iran

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.04.004 Byline: Shimon Abravaya (a), Michael Segal (b) Abstract: This paper deals with the problem of locating a maximal cardinality set of obnoxious facilities within a bounded rectangle in the plane such that their pairwise L.sub.[infinity]-distance as well as the L.sub.[infinity]-distance to a set of already placed demand sites is above a given threshold. We employ techniques and methods from computational geometry to design an optimization algorithm and an efficient 1/2-approximation algorithm for the problem, and employ the optimization algorithm to design a PTAS based on the shifting strategy [Hochbaum DS, Maass W. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM 1985;32:130-6]. As a byproduct we improve the algorithm for placing obnoxious facilities given by Katz et al. [Improved algorithms for placing undesirable facilities. Computers & Operations Research 2002;29:1859-72.]. Author Affiliation: (a) Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel (b) Department of Communication Systems Engineering, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.02.017 Byline: Yuvraj Gajpal, Prakash Abad Abstract: In this paper we use an ant colony system (ACS) algorithm to solve the vehicle routing problem with simultaneous delivery and pickup (VRPSDP) which is a combinatorial optimization problem. ACS is an algorithmic approach inspired by the foraging behavior of real ants. Artificial ants are used to construct a solution for the problem by using the pheromone information from previously generated solutions. The proposed ACS algorithm uses a construction rule as well as two multi-route local search schemes. The algorithm can also solve the vehicle routing problem with backhaul and mixed load (VRPBM). An extensive numerical experiment is performed on benchmark problem instances available in literature. It is found that ACS gives good results compared to the existing algorithms. Author Affiliation: Michael G DeGroote School of Business, McMaster University, Hamilton, Ontario, Canada L8S4M4

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.07.011 Byline: T. Meyer (a), A.T. Ernst (b), M. Krishnamoorthy (b) Abstract: The single allocation p-hub center problem is an NP-hard location-allocation problem which consists of locating hub facilities in a network and allocating non-hub nodes to hub nodes such that the maximum distance/cost between origin-destination pairs is minimized. In this paper we present an exact 2-phase algorithm where in the first phase we compute a set of potential optimal hub combinations using a shortest path based branch and bound. This is followed by an allocation phase using a reduced sized formulation which returns the optimal solution. In order to get a good upper bound for the branch and bound we developed a heuristic for the single allocation p-hub center problem based on an ant colony optimization approach. Numerical results on benchmark instances show that the new solution approach is superior over traditional MIP-solver like CPLEX. As a result we are able to provide new optimal solutions for larger problems than those reported previously in literature. We are able to solve problems consisting of up to 400 nodes in reasonable time. To the best of our knowledge these are the largest problems solved in the literature to date. Author Affiliation: (a) Department of Mathematics, University of Kaiserslautern, Gottlieb-Daimler-Strasse, 67663 Kaiserslautern, Germany (b) CSIRO Mathematical and Information Sciences, Private Bag 33, Clayton South MDC, Clayton VIC 3169, Australia

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2009.04.001 Byline: Alexander Grigoriev (a), Nadejda V. Grigorieva (b) Keywords: Optimization; Environmental studies; Accidents; Gas-oil transport; Dynamic programming algorithm Abstract: A shutoff valve is a control device that blocks oil flow in a pipeline in order to reduce the oil escape. This paper addresses the valve location problem where, given a pipeline network and a number of valves for installation, the task is to find a valve location that minimizes the maximum environmental damage of an oil spill. We present the first complete framework for fast computing of an optimal valve location in a general oil pipeline network. To achieve this, we formalize the problem and explain how to quantify environmental damages. Next, we present two fast algorithms optimally solving the valve location problem on linear pipeline segments. Further, we show how to extend the algorithms to solve the problem on a general pipeline network. We conclude with a computational study showing that solutions provided by our framework can reduce the adverse effects of a spill by up to 37% compared to the currently used solutions. Author Affiliation: (a) Department of Quantitative Economics, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands (b) Institute of Power Resources Transport (IPTER), 144/3, pr. Octyabrya, Ufa-450055, Russia Article History: Received 3 March 2008; Revised 2 April 2009; Accepted 3 April 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2009.04.007 Byline: Li Chunlin, Li Layuan Keywords: Grid computing; System-centric scheduling; Simulation Abstract: In grid computing, grid users who submit applications and resources providers who provide resources have different motivations when they join the grid. Application-centric scheduling aims to optimize the performance of individual application. Resource-centric scheduling aims to optimize the resource utilization of resources provider. Due to autonomy both in grid users and resource providers, the objectives of application-centric and resource-centric scheduling often conflict. The paper proposes a system-centric scheduling that provides a solution of joint optimization of the objectives for both the grid resource and grid application. Utility functions are used to express the objectives of grid resource and application. The system-centric scheduling policy can be formulated as joint optimization of utilities of grid applications and grid resources, which combine both application centric and resource-centric scheduling benefits. Simulations are conducted to study the performance of the system-centric scheduling algorithm. The experiment results show that the system-centric scheduling algorithm yields significantly better performance than application-centric scheduling algorithm and resource-centric scheduling algorithm. Author Affiliation: Department of Computer Science, Wuhan University of Technology, Wuhan 430063, PR China Article History: Received 19 August 2007; Revised 9 December 2008; Accepted 14 April 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ijpe.2008.03.015 Byline: Sylverin Kemmoe Tchomte (a)(b), Michel Gourgand (c) Abstract: This article addresses the particle swarm optimization (PSO) method. It is a recent proposed algorithm by Kennedy and Eberhart [1995. Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks (Perth, Australia), vol. IV, IEEE Service Center, Piscataway, NJ, pp. 1942-1948]. This optimization method is motivated by social behaviour of organisms such as bird flocking and fish schooling. PSO algorithm is not only a tool for optimization, but also a tool for representing socio-cognition of human and artificial agents, based on principles of social behaviour. Some scientists suggest that knowledge is optimized by social interaction and thinking is not only private but also interpersonal. PSO as an optimization tool, provides a population-based search procedure in which individuals called particles change their position (state) with time. In a PSO system, particles fly in a multidimensional search space. During flight, each particle adjusts its position according to its own experience, and according to the experience of neighbours, making use of the best position encountered by itself and its neighbours. In this paper, we propose firstly, an extension of the PSO system that integrates a new displacement of the particles (the balance between the intensification process and the diversification process) and we highlight a relation between the coefficients of update of each dimension velocity between the classical PSO algorithm and the extension. Secondly, we propose an adaptation of this extension of PSO algorithm to solve combinatorial optimization problem with precedence constraints in general and resource-constrained project scheduling problem in particular. The numerical experiments are done on the main continuous functions and on the resource-constrained project scheduling problem (RCPSP) instances provided by the psplib. The results obtained are encouraging and push us into accepting than both PSO algorithm and extensions proposed based on the new particles displacement are a promising direction for research. Author Affiliation: (a) Laboratoire d'Informatique (LIMOS, UMR CNRS 6158), Campus des Cezeaux, 63177 Aubiere, France (b) IUP, Universite d'Auvergne, 26 Av. Leon Blum, 63008 Clermont Ferrand, Cedex, France (c) ISIMA, Universite Blaise Pascal, Campus des Cezeaux, 63177 Aubiere, Cedex, France Article History: Received 17 December 2007; Accepted 24 March 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2007.12.016 Byline: Feng-Cheng Yang, Yon-Chun Chou Keywords: Ant Colony Optimization System; Pheromone withdraw; Segment-based pheromone update; Superior and inferior segments; Segment-Discriminated Ant System Abstract: The Ant Colony Optimization method is a heuristic algorithm for solving various optimization problems, particularly the combinatorial optimization problems. Traditional ant-optimization methods might encounter search stagnation owing to a biased pheromone map that is dominated by local optimal trails. To overcome this drawback and lower the number of solution constructions for finding the optima, this paper presents an improving ant-optimization system, the Superior/Inferior Segment-Discriminated Ant System (SDAS). This system proposes a segment-based pheromone update strategy to deposit pheromone on superior segments and withdraw pheromone from inferior ones. The method uses the control-chart technique to define superior and inferior limits to partition the constructed solutions into superior, inferior, and ordinary solutions. Inferior and superior segments are then extracted from the superior and inferior solutions by stochastic set operations. Since the pheromone map is not easily dominated by any local optimal trail, the solution search is more efficient and effective. Several benchmarks from the TSP-LIB and OR-LIB were used as sample problems to test the proposed system against other ant-optimization systems, including the AS, ACS, AS_rank, AS_elite, and MMAS. Numerical results indicated that the SDAS obtains solutions that are similar to or better than others. Maturity index for the pheromone map was discussed and experimental results showed that the proposed method was able to prolong the time for the map to maturity to avoid earlier search stagnation. Author Affiliation: Graduate Institute of Industrial Engineering, National Taiwan University, 1, Section 4, Roosevelt Road, Taipei 106, Taiwan

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ijpe.2008.11.015 Byline: Satyaveer S. Chauhan (a)(b), Alexandre Dolgui (c), Jean-Marie Proth (d) Keywords: Assembly-to-order; Random lead-times; Supply planning; Optimization; Simulated annealing Abstract: This paper studies a customized product assembly scenario where some components cannot be stocked due to high component cost and risk. We consider the case where these key components are ordered after a demand has been registered with a promised delivery date. Component lead-times are stochastic and associated distribution function is known in advance. The objective is to determine the ordering time for each component such as to minimize the sum of expected holding and backlogging costs. An approach to solve this problem is proposed and the algorithm is tested on a randomly generated data set. Author Affiliation: (a) John Molson School of Business, Concordia University, 1455 de Maisonneuve Boulevard West, Montreal, Quebec, Canada H3G 1M8 (b) Centre Interuniversitaire de Recherche sur les Reseaux d'Entreprise, la Logistique et le Transport (CIRRELT), Montreal, Canada (c) Centre for Industrial Engineering and Computer Science, Ecole des Mines de Saint Etienne, 158, cours Fauriel 42023 Saint Etienne, France (d) INRIA-SAGEP, 22 rue du Colombier, 57420 Pouilly, France Article History: Received 1 May 2007; Accepted 7 November 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ijpe.2008.11.017 Byline: Ihsan Sabuncuoglu (a), Erdal Erel (b), Arda Alp (c) Keywords: General assignments problem; U-type assembly line balancing problem; Ant colony optimization; Metaheuristic Abstract: An assembly line is a production line in which units move continuously through a sequence of stations. The assembly line balancing problem is defined as the allocation of tasks to an ordered sequence of stations subject to precedence constraints with the objective of optimizing a performance measure. In this paper, we propose ant colony algorithms to solve the single-model U-type assembly line balancing problem. We conduct an extensive experimental study in which the performance of the proposed algorithm is compared against best known algorithms reported in the literature. The results indicate that the proposed algorithms display very competitive performance against them. Author Affiliation: (a) Department of Industrial Engineering, Bilkent University, Bilkent 06800, Ankara, Turkey (b) Faculty of Business Administration, Bilkent University, Bilkent 06800, Ankara, Turkey (c) Artificial Intelligence Laboratory, School of Computer and Communication Sciences, Ecole Polytechnique Federale de Lausanne (EPFL), CH-1015 Lausanne, Switzerland Article History: Received 10 April 2007; Accepted 14 November 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.09.002 Byline: Saadettin Erhan Kesen (a), M. Duran Toksari (b), Zulal Gungor (c), Ertan Guner (c) Keywords: Virtual manufacturing cells; Simulation; Ant colony optimization; Metamodels Abstract: The aim of this paper is two fold. First we investigate the three different types of systems, namely cellular layout (CL), process layout (PL) and virtual cells (VCs). VCs are addressed by using family-based scheduling rule, developed by a part allocation algorithm in a PL. Simulation is used to compare three types of systems under the performance metrics such as mean flow time and mean tardiness. Results indicate that VCs have better responsiveness in terms of the performance metrics. Second we develop a new ant colony optimization-based metamodels fed by existing simulation runs to represent the prospective simulation runs, which require a lot of time and effort. Regression metamodels, which allow us to obtain much faster results, are seen to be promising to estimate the systems behaviors. Author Affiliation: (a) Faculty of Engineering and Architecture, Industrial Engineering Department, Selcuk University, Campus, 42075 Konya, Turkey (b) Faculty of Engineering , Industrial Engineering Department, Erciyes University, 38039 Kayseri, Turkey (c) Faculty of Engineering and Architecture, Industrial Engineering Department, Gazi University, Maltepe, 06570 Ankara, Turkey

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2008.09.001 Byline: Jessica A. Carballido (a), Ignacio Ponzoni (a)(b), Nelida B. Brignole (a)(b) Keywords: Instrumentation design; Genetic algorithms; Combinatorial optimization problem; Decision support system Abstract: In this paper the core of a genetic algorithm designed to define a sensor network for instrumentation design (ID) is presented. The tool has been incorporated into a decision support system (DSS) that assists the engineer during the ID process. The algorithm satisfactorily deals with non-linear mathematical models, and considers four design objectives, namely observability, cost, reliability and redundancy, exhibiting properties that were either never addressed by existing techniques or partially dealt with in the literature. Its performance was tested by carrying out the ID of an ammonia synthesis industrial plant. Results were statistically analysed. A face validity study on the fitness function's soundness was also assessed by a chemical engineer with insight and expertise in this problem. The technique performed satisfactorily from the point of view of the expert in ID, and therefore it constitutes a significant upgrading for the DSS. Author Affiliation: (a) Laboratorio de Investigacion y Desarrollo en Computacion Cientifica (LIDeCC), Departamento de Ciencias e Ingenieria de la Computacion, Universidad Nacional del Sur, Av. Alem 1253, Bahia Blanca, 8000 Buenos Aires, Argentina (b) Planta Piloto de Ingenieria Quimica, CONICET, Bahia Blanca 8000, Argentina Article History: Received 11 December 2007; Revised 28 April 2008; Accepted 3 September 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2008.08.015 Byline: Elyas Shivanian (a), Esmaile Khorram (b) Keywords: Monomial geometric programming; Fuzzy relation equalities and inequalities; Max-product composition Abstract: Monomials function has always been considered as a significant and most extensively used function in real living. Resource allocation, structure optimization and technology management can often apply these functions. In optimization problems the objective functions can be considered by monomials. In this paper, we present monomials geometric programming with fuzzy relation inequalities constraint with max-product composition. Simplification operations have been given to accelerate the resolution of the problem by removing the components having no effect on the solution process. Also, an algorithm and a few practical examples are presented to abbreviate and illustrate the steps of the problem resolution. Author Affiliation: (a) Department of Mathematics, Faculty of Science, Imam Khomeini International University, Qazvin 34194-288, Iran (b) Faculty of Mathematics and Computer Science, Amirkabir University of Technology, Tehran 15914, Iran Article History: Received 16 February 2008; Revised 4 August 2008; Accepted 31 August 2008

In many organizations, it is desirable to distribute workload as equally as possible among a group of employees or machines. This paper proposes a performance measure, that we call the Normalized Sum of Square for Workload Deviations (NSSWD), and studies the problem of how to schedule a set of n jobs on m parallel identical processors in order to minimize the NSSWD. The NSSWD criterion is relevant where uniformity of wear to machines or of workload to employees is desirable. An algorithm, called Workload Balancing (WB), is proposed for solving this problem. Moreover, we perform a simulation experiment to evaluate WB against several well-known heuristics in the literature. Lastly, we discuss the computational results obtained from the simulation experiment. Keywords: Heuristics Load balancing Optimization Parallel machines scheduling

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2007.06.034 Byline: Ying-Hua Chang (a), Young-Chang Hou (b) Keywords: Genetic Algorithms; Dynamic programming decision path encoding; Production allocation; Constraints satisfaction; Optimization problems Abstract: Genetic algorithm is a novel optimization technique for solving constrained optimization problems. The penalty function methods are the popular approaches because of their simplicity and ease of implementation. Penalty encoding method needs more generations to get good solutions because it causes invalid chromosomes during evolution. In order to advance the performance of Genetic Algorithms for solving production allocation problems, this paper proposes a new encoding method, which applies the upper/lower bound concept of dynamic programming decision path on the chromosome encoding of genetic algorithm, that encodes constraints into chromosome to ensure that chromosomes are all valid during the process of evolution. Utilization of the implicated parallel processing characteristic of genetic algorithms to improve dynamic programming cannot guarantee to solve complex problems in the polynomial time. Additionally, a new simultaneous crossover and mutation operation is proposed to enable the new method to run correctly following the standard genetic algorithm procedures. This approach is evaluated on some test problems. Solutions obtained by this approach indicate that our new encoding genetic algorithms certainly accelerate the performance of the evolution process. Author Affiliation: (a) Department of Information Management, Tatung University, 40 ChungShan North Road, 3rd Section, Taipei 104, ROC (b) Department of Information Management, Tamkang University, 151 Ying-chuan Road, Tamsui, Taipei 251, ROC Article History: Received 14 June 2006; Revised 12 May 2007; Accepted 16 June 2007

2024 JUL 18 (NewsRx) -- By a News Reporter-Staff News Editor at Women's Health Weekly -- Investigators publish new report on cervical cancer. According to news reporting from Kanazawa, Japan, [...]

2023 OCT 7 (NewsRx) -- By a News Reporter-Staff News Editor at Obesity, Fitness & Wellness Week -- Fresh data on algorithms are presented in a new report. According to [...]

2021 DEC 11 (NewsRx) -- By a News Reporter-Staff News Editor at Obesity, Fitness & Wellness Week -- Researchers detail new data in Expert Systems. According to news reporting originating [...]

We consider an assortment optimization problem where a retailer chooses an assortment of products that maximizes the profit subject to a capacity constraint. The demand is represented by a multinomial [...]

* Intelligence * Surveillance * Computer hardware * MAP processors * Operating systems SRC Computers (Colorado Springs, Colo.) has developed a new hardware architecture and programming environment that deliver orders [...]

Problem statement: The problem of finding the minimum value of objective function, when we know only some values of it, is needed in more practical fields. Quadratic interpolation algorithms are the famous tools deal with this kind of these problems. These algorithms interested with the polynomial space in which the objective function is approximated. Approach: In this study we approximated the objective function by a one dimensional quadratic polynomial. This approach saved the time and the effort to get the best point at which the objective is minimized. Results: The quadratic polynomial in each one of the steps of the proposed algorithm, accelerate the convergent to the best value of the objective function without taking into account all points of the interpolation set. Conclusion: Any n-dimensional problem of finding a minimal value of a function, given by some values, can be converted to one dimensional problem easier in deal. Key words: Quadratic interpolation, tabulated function, trust region, derivative free optimization, INTRODUCTION Many optimization problems can be occur in practice, for example, in most of labs, one obtains data for certain phenomena and wants know that the point at which this [...]