Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2006.03.026 Byline: S.S. Chauhan, Alain Martel, Sophie D'Amour Abstract: Fine paper mills produce a variety of paper grades to satisfy demand for a large number of sheeted products. Huge reels of different paper grades are produced on a cyclical basis on paper machines. These reels are then cut into rolls of smaller size which are then either sold as such, or sheeted into finished products in converting plants. A huge number of roll sizes would be required to cut all finished products without trim loss and they cannot all be inventoried. An assortment of rolls is inventoried with the implication that the sheeting operations may yield trim loss. The selection of the assortment of roll sizes to stock and the assignment of these roll sizes to finished products have a significant impact on performances. This paper presents a model to decide the parent roll assortment and assignments to finished products based on these products demand processes, desired service levels, trim loss and inventory holding costs. Risk pooling economies made by assigning several finished products to a given roll size is a fundamental aspect of the problem. The overall model is a binary non-linear program. Two solution methods are developed: a branch and price algorithm based on column generation and a fast pricing heuristic, and a marginal cost heuristic. The two methods are tested on real data and also on randomly generated problem instances. The approach proposed was implemented by a large pulp and paper company. Author Affiliation: FOR@C Research Consortium, Network Organization Technology Research Center (CENTOR), Universite Laval, Sainte-Foy, Que., Canada G1K 7P4

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2010.02.002 Byline: Enrico Angelelli (a), Renata Mansini (b), M. Grazia Speranza (a) Abstract: In this paper we apply the kernel search framework to the solution of the strongly NP-hard multi-dimensional knapsack problem (MKP). Kernel search is a heuristic framework based on the identification of a restricted set of promising items (kernel) and on the exact solution of ILP sub-problems. Initially, the continuous relaxation of the MKP, solved on the complete set of available items, is used to identify the initial kernel. Then, a sequence of ILP sub-problems are solved, where each sub-problem is restricted to the present kernel and to a subset of other items. Each ILP sub-problem may find better solutions with respect to the previous one and identify further items to insert into the kernel. The kernel search was initially proposed to solve a complex portfolio optimization problem. In this paper we show that the method has general key features that make it appropriate to solve other combinatorial problems using binary variables to model the decisions to select or not items. We adapt the kernel search to the solution of MKP and show that the method is very effective and efficient with respect to known problem-specific approaches. Moreover, the best known values of some MKP benchmark problems from the MIPLIB library have been improved. Author Affiliation: (a) Department of Quantitative Methods, University of Brescia, Italy (b) Department of Information Engineering, University of Brescia, Italy

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2010.01.017 Byline: Rasmus R. Amossen (a), David Pisinger (b) Abstract: The problem addressed in this paper is the decision problem of determining if a set of multi-dimensional rectangular boxes can be orthogonally packed into a rectangular bin while satisfying the requirement that the packing should be guillotine cuttable. That is, there should exist a series of face parallel straight cuts that can recursively cut the bin into pieces so that each piece contains a box and no box has been intersected by a cut. The unrestricted problem is known to be NP-hard. In this paper we present a generalization of a constructive algorithm for the multi-dimensional bin packing problem, with and without the guillotine constraint, based on constraint programming. Author Affiliation: (a) IT University of Copenhagen, Rued Langgaards Vej 7, DK-2300 Copenhagen S, Denmark (b) DTU Management Engineering, Produktionstorvet 424, DK-2800, Kgs. Lyngby, Denmark

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.cor.2009.11.013 Byline: F. Guerriero, L. Talarico Keywords: Activity network; Critical path; Time-constrained network; Time-window constraint; Time-schedule constraint; Time-switch constraint Abstract: Finding the longest path in an activity network, where time constraints are attached to activities, is generalized from the traditional critical path problem. Time constraints have attracted much research interest in recent years, because they can be used to represent a large set of real situations, arising not only in the field of the project management. In this paper, we propose a general approach for finding the critical path in a deterministic activity-on-the-arc network, considering three different types of time constraints. The first one is the time-window constraint, which imposes that an activity can start only in a predefined time interval, whereas no constraints are imposed on the activity completion time. The second one is the time-schedule constraint, which assumes that an activity can start its execution at one of the pre-specified instants of time. The third one is the time-switch constraint, which imposes a specified starting time on the project activities and forces them to be inactive during specified time periods. The algorithm introduced in this paper has been developed by redefining and combining together two procedures well-known in the scientific literature. The former, proposed by Chen, Rinks and Tang in 1997, can be used for finding the critical path in an activity network where time-schedule and time-window constraints are considered. The latter, proposed by Yang and Chen in 2000, can be applied in activity networks with only time-switch constraints. The method, developed in this paper, can be used to find the critical path in all the practical situations, in which the aforementioned time constraints are taken into account simultaneously. The proposed approach has been coded in Java and has been validated by considering two sets of instances: the former has been taken from the public domain project scheduling problem library, developed by Kolisch and Sprecher in 1997, whereas the latter consists of randomly generated activity networks. The computational results collected are very promising, showing that the solution process for the considered instances required at most few seconds, using a commercial Pentium class PC. Author Affiliation: Dipartimento di Elettronica, Informatica e Sistemistica, University of Calabria, Italy

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.06.020 Byline: Jun Woo Kim (a), Sang Chan Park (b) Keywords: Call center; Additional service; Two-stage service; Outsourcing strategy Abstract: This paper considers 'two-stage' call centers where some incoming calls are completed by first service while others require an additional second service. Although this type of call center is not uncommon, it has not been dealt with, if any, in the call center literature. In this paper, we introduce the concept of the 'two-stage' call center and discuss its features. Furthermore, we develop an effective outsourcing strategy in 'two-stage' call centers. To this end, we model 'two-stage' service system and propose several call routing structures. The structures are compared through numerical test and conventional queueing theories form the theoretical basis of our study. Author Affiliation: (a) Department of Industrial Engineering, KAIST, Guseong-dong, Yuseong-gu, Daejeon 305-701, South Korea (b) College of Business Administration, Kyung Hee University, 1 Hoegi-dong, Dongdaemun-gu, Seoul 130-701, South Korea

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.06.022 Byline: Yuichi Nagata (a), Olli Braysy (b), Wout Dullaert (c)(d) Abstract: In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instances. Author Affiliation: (a) Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, 4259 Nagatsuta Midori-ku Yokohama, Kanagawa 226-8502, Japan (b) Agora Innoroad Laboratory, Agora Center, P.O. Box 35, FI-40014 University of Jyvaskyla, Finland (c) Institute of Transport and Maritime Management Antwerp, University of Antwerp, Keizerstraat 64, 2000 Antwerp, Belgium (d) Antwerp Maritime Academy, Noordkasteel Oost 6, 2030 Antwerp, Belgium

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.06.009 Byline: Ancu Hazir (a)(b), Mohamed Haouari (c)(d), Erdal Erel (b) Keywords: Project scheduling; Time/cost trade-off; Benders Decomposition Abstract: This paper investigates the budget variant of the discrete time/cost trade-off problem (DTCTP). This multi-mode project scheduling problem requires assigning modes to the activities of a project so that the total completion time is minimized and the budget and the precedence constraints are satisfied. This problem is often encountered in practice as timely completion of the projects without exceeding the budget is crucial. The contribution of this paper to the literatures is to describe an effective Benders Decomposition-based exact algorithm to solve the DTCTP instances of realistic sizes. Although Benders Decomposition often exhibits a very slow convergence, we have included several algorithmic features to enhance the performance of the proposed tailored approach. Computational results attest to the efficacy of the proposed algorithm, which can solve large-scale instances to optimality. Author Affiliation: (a) Industrial Engineering Department, Aankaya University, Ankara 06530, Turkey (b) Faculty of Business Administration, Bilkent University, Ankara 06800, Turkey (c) Department of Industrial and Systems Engineering, Faculty of Engineering, Ozyegin University, Istanbul, Turkey (d) Princess Fatimah Alnijris's Research Chair for AMT, College of Engineering, King Saud University, Saudi Arabia

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.02.006 Byline: Luis V. Santana-Quintero (a), Alfredo G. Hernandez-Diaz (b), Julian Molina (c), Carlos A. Coello Coello (a), Rafael Caballero (c) Abstract: The aim of this paper is to show how the hybridization of a multi-objective evolutionary algorithm (MOEA) and a local search method based on the use of rough set theory is a viable alternative to obtain a robust algorithm able to solve difficult constrained multi-objective optimization problems at a moderate computational cost. This paper extends a previously published MOEA [Hernandez-Diaz AG, Santana-Quintero LV, Coello Coello C, Caballero R, Molina J. A new proposal for multi-objective optimization using differential evolution and rough set theory. In: 2006 genetic and evolutionary computation conference (GECCO'2006). Seattle, Washington, USA: ACM Press; July 2006], which was limited to unconstrained multi-objective optimization problems. Here, the main idea is to use this sort of hybrid approach to approximate the Pareto front of a constrained multi-objective optimization problem while performing a relatively low number of fitness function evaluations. Since in real-world problems the cost of evaluating the objective functions is the most significant, our underlying assumption is that, by aiming to minimize the number of such evaluations, our MOEA can be considered efficient. As in its previous version, our hybrid approach operates in two stages: in the first one, a multi-objective version of differential evolution is used to generate an initial approximation of the Pareto front. Then, in the second stage, rough set theory is used to improve the spread and quality of this initial approximation. To assess the performance of our proposed approach, we adopt, on the one hand, a set of standard bi-objective constrained test problems and, on the other hand, a large real-world problem with eight objective functions and 160 decision variables. The first set of problems are solved performing 10,000 fitness function evaluations, which is a competitive value compared to the number of evaluations previously reported in the specialized literature for such problems. The real-world problem is solved performing 250,000 fitness function evaluations, mainly because of its high dimensionality. Our results are compared with respect to those generated by NSGA-II, which is a MOEA representative of the state-of-the-art in the area. Author Affiliation: (a) CINVESTAV-IPN, Computer Science Department, Av. IPN No. 2508 Col. San Pedro Zacatenco, Mexico D.F. 07360, Mexico (b) Pablo de Olavide University, Department of Economics, Quantitative Methods and Economic History, Ctra. de Utrera km. 1, 41013 Seville, Spain (c) University of Malaga, Department of Applied Economics (Mathematics), Campus El Ejido s./n. 29071, Spain

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.04.008 Byline: Tatsushi Nishi, Yuichiro Hiranaka, Masahiro Inuiguchi Abstract: In this paper, we address a new Lagrangian relaxation (LR) method for solving the hybrid flowshop scheduling problem to minimize the total weighted tardiness. For the conventional LR, the problem relaxing machine capacity constraints can be decomposed into individual job-level subproblems which can be solved by dynamic programming. The Lagrangian dual problem is solved by the subgradient method. In this paper, a Lagrangian relaxation with cut generation is proposed to improve the Lagrangian bounds for the conventional LR. The lower bound is strengthened by imposing additional constraints for the relaxed problem. The state space reductions for dynamic programming for subproblems are also incorporated. Computational results demonstrate that the proposed method outperforms the conventional LR method without significantly increasing the total computing time. Author Affiliation: Division of Mathematical Science for Social Systems, Department of Systems Innovation, Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama, Toyonaka City, Osaka 560-8531, Japan

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.04.010 Byline: B. Naderi (a), S.M.T. Fatemi Ghomi (a), M. Aminnayeri (a), M. Zandieh (b) Keywords: Scheduling; Open shop; Constructive heuristic; Encoding scheme; Permutation; Redundancy; Insertion and reinsertion operators Abstract: This paper deals with open shops under makespan minimization. Encoding scheme plays a pivotal role in the success of any algorithm to solve a scheduling problem. Although the permutation list has many advantages (such as high adaptability to any operators, conceptual simplicity and ease of implementation), it suffers from a notorious inherent drawback, called redundancy. This serious drawback has made many researchers conclude that permutation list is ineffective for open shop scheduling. Therefore, they have turned toward the utilization of rank matrix encoding scheme to overcome this shortcoming at the expense of losing other advantages of permutation list. In this paper, we first pinpoint the origin of redundancy in the permutation list. We then analyze circumstances in which the redundancy occurs and afterwards present four efficient theorems to avoid this critical disadvantage. Regarding the theorems, we understand that redundancy is quite identifiable and also controllable. By introducing an alternative possibility to rank matrices of excluding redundancy, the solution space of open shops is significantly reduced. By reducing the search space, the probability of finding an excellent solution in reasonable computational time outstandingly soars. Finally, based on insertion and reinsertion operators we propose four constructive heuristics incorporating simple applications of the theorems. We evaluate the effectiveness and efficiency of our proposed algorithms on three well-known benchmarks and against some other existing heuristics. All the results and analyses illustrate the authenticity and superiority of our theorems and proposed constructive heuristics. Author Affiliation: (a) Department of Industrial Engineering, Amirkabir University of Technology, Tehran, Iran (b) Department of Industrial Management, Management and Accounting Faculty, Shahid Beheshti University, G.C., Tehran, Iran

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.05.013 Byline: Graham Kendall (a), Sigrid Knust (b), Celso C. Ribeiro (c), Sebastian Urrutia (d) Abstract: Sports have worldwide appeal. Professional sport leagues involve significant investments in players. Events such as the Olympics Games, the Football World Cup and the major golf and tennis tournaments generate huge worldwide television audiences and many sports are multi-million dollar industries. A key aspect of sporting events is the ability to generate schedules that optimize logistic issues and that are seen as fair to all those who have an interest. This is not just restricted to generating the fixtures, but also to other areas such as assigning officials to the games in the competitions. This paper provides an annotated bibliography for sports scheduling articles. This area can be traced back over 40 years. It is noticeable that the number of papers has risen in recent years, demonstrating that scientific interest is increasing in this area. Author Affiliation: (a) University of Nottingham, School of Computer Science, Jubilee Campus, Nottingham NG8 1BB, UK (b) Technical University of Clausthal, Department of Mathematics, 38678 Clausthal-Zellerfeld, Germany (c) Universidade Federal Fluminense, Department of Computer Science, Rua Passo da Patria 156, Niteroi, RJ 24210-240, Brazil (d) Universidade Federal de Minas Gerais, Department of Computer Science, Av. AntA[acute accent]nio Carlos 6627, Belo Horizonte, MG 31270-010, Brazil

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.02.012 Byline: R. Tavakkoli-Moghaddam (a), F. Taheri (b), M. Bazzazi (b), M. Izadi (c), F. Sassani (d) Abstract: This paper presents a novel, two-level mixed-integer programming model of scheduling N jobs on M parallel machines that minimizes bi-objectives, namely the number of tardy jobs and the total completion time of all the jobs. The proposed model considers unrelated parallel machines. The jobs have non-identical due dates and ready times, and there are some precedence relations between them. Furthermore, sequence-dependent setup times, which are included in the proposed model, may be different for each machine depending on their characteristics. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches or optimization tools is extremely difficult. This paper proposes an efficient genetic algorithm (GA) to solve the bi-objective parallel machine scheduling problem. The performance of the presented model and the proposed GA is verified by a number of numerical experiments. The related results show the effectiveness of the proposed model and GA for small and large-sized problems. Author Affiliation: (a) Department of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran (b) Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran (c) Department of Computer Engineering and IT, Amirkabir University of Technology, Tehran, Iran (d) Department of Mechanical Engineering, The University of British Columbia, Vancouver, Canada

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.01.006 Byline: Francisco Ballestin (a), Vicente Valls (b), Sacramento Quintanilla (c) Abstract: A recent paper (Ballestin F, Valls V, Quintanilla S. Preemption in resource-constrained project scheduling. European Journal of Operational Research 2008;189:1136-152) revealed the potential benefits of allowing one interruption when scheduling activities in a resource-constrained project. This paper further investigates the effect of interruption on project length in more general cases. To achieve this, a new model that covers most practical applications of discrete activity preemption is proposed and a metaheuristic algorithm for the problem is developed. Computational experiments on the standard j120 and j30 sets generated using ProGen study the difference in makespan between allowing m interruptions per activity, m=0,1,2,... . In the second part of the paper the usefulness of preemption in the presence of due dates is analysed. Author Affiliation: (a) Dpto. de Estadistica e Investigacion Operativa, Facultad de Economicas y Empresariales, Universidad Publica de Navarra, Pamplona, Spain (b) Dpto. de Estadistica e Investigacion Operativa, Facultad de Matematicas, Universitat de Valencia, Spain (c) Dpto. de Economia Financiera y Matematica, Facultad de Economicas y Empresariales, Universitat de Valencia, Spain Article Note: (footnote) [star] This research was partially supported by the Ministerio de Educacion y Ciencia under Contract DPI2007-63100.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.01.018 Byline: Mauro Dell'Amico, Jose Carlos Diaz Diaz, Manuel Iori, Roberto Montanari Abstract: The problem of designing new keyboard layouts able to improve the typing speed of an average message has been widely considered in the literature of the Ergonomics domain. Empirical tests with users and simple optimization criteria have been used to propose new solutions. On the contrary, very few papers in Operations Research have addressed this optimization problem. In this paper we firstly resume the most relevant problems in keyboard design, enlightening the related Ergonomics aspects. Then we concentrate on keyboards that must be used with a single finger or stylus, like that of portable data assistant, smartphones and other small devices. We show that the underlying optimization problem is a generalization of the well-known quadratic assignment problem (QAP). We recall some of the most effective metaheuristic algorithms for QAP and we propose some non-trivial extensions to the keyboard design problem. We compare the new algorithms through computational experiments with instances obtained from word lists of the English, French, Italian and Spanish languages. We provide on the web benchmark instances for each language and the best solutions we obtained. Author Affiliation: DISMI, University of Modena and Reggio Emilia, via Amendola, 2, 42100 Reggio Emilia, Italy

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.01.013 Byline: Pedro Martins (a), Mauricio C. de Souza (b) Abstract: Given an undirected graph with weights associated with its edges, the min-degree constrained minimum spanning tree (md-MST) problem consists in finding a minimum spanning tree of the given graph, imposing minimum degree constraints in all nodes except the leaves. This problem was recently proposed in Almeida et al. [Min-degree constrained minimum spanning tree problem: Complexity, proprieties and formulations. Operations Research Center, University of Lisbon, Working-paper no. 6; 2006], where its theoretical complexity was characterized and showed to be NP-hard. The present paper discusses variable neighborhood search (VNS) metaheuristics addressing the md-MST. A so-called enhanced version of a second order (ESO) repetitive technique is also considered, in order to guide the search in both shaking and improvement phases of the VNS method. A Kruskal based greedy heuristic adapted to the md-MST is also presented, being used within the ESO framework. VNS randomized methodologies are also discussed. These are the first heuristics to the md-MST ever proposed in the literature. Computational experiments are conducted on instances adapted from benchmark ones used in the context of the well-known degree constraint minimum spanning tree problem. These experiments have shown that randomized VNS methods enclosing an ESO algorithm can produce very interesting results. In particular, that a simpler VNS randomized methodology might be taken into account when very high dimensional instances are under consideration. Author Affiliation: (a) CIO - Centro de Investigacao Operacional - FC/UL and ISCAC - Instituto Politecnico de Coimbra, Portugal (b) Departamento de Engenharia de Producao, Universidade Federal de Minas Gerais, Brasil

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.01.003 Byline: Rafael Marti (a), Jose Luis Gonzalez Velarde (b), Abraham Duarte (c) Keywords: Metaheuristics; Bi-objective programming; Routing Abstract: In this paper the path dissimilarity problem is considered. The problem has previously been studied within several contexts, the most popular of which is motivated by the need to select transportation routes for hazardous materials. The aim of this paper is to formally introduce the problem as a bi-objective optimization problem, in which a single solution consists of a set of p different paths, and two conflicting objectives arise, on one hand the average length of the paths must be kept low, and on the other hand the dissimilarity among the paths in the set should be kept high. Previous methods are reviewed and adapted to this bi-objective problem, thus we can compare the methods using the standard measures in multi-objective optimization. A new GRASP procedure is proposed and tested against the revised methods, and we show that it is able to create better approximations of efficient frontiers than existing methods. Author Affiliation: (a) Departamento de Estadistica e Investigacion Operativa, Universidad de Valencia, Spain (b) Centro de Manufactura y Calidad, Tecnologico de Monterrey, Mexico (c) Departamento de Ciencias de la Computacion, Universidad Rey Juan Carlos, Spain

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.11.001 Byline: Augusto Eusebio (a)(b), Jose Rui Figueira (b)(c) Abstract: This paper deals with an algorithm for finding all the non-dominated solutions and corresponding efficient solutions for bi-objective integer network flow problems. The algorithm solves a sequence of E-constraint problems and computes all the non-dominated solutions by decreasing order of one of the objective functions. The optimal integer solutions for the E-constraint problems are determined by exploring a branch-and-bound tree. The algorithm makes use of the network structure to perform the computations, i.e., the network structure of the problem is not destroyed with the inclusion of an E-constraint. This paper presents the main features of the algorithm, the theoretical bases of the proposed approach and some computational issues. Experiments were done and the results are also reported in the paper. Author Affiliation: (a) Escola Superior de Tecnologia e Gestao, Instituto Politecnico de Leiria, Morro do Lena, Alto Vieiro, 2411-901 Leiria, Portugal (b) CEG-IST, Centre for Management Studies, Instituto Superior Tecnico, Technical University of Lisbon, TagusPark, Av. Cavaco Silva, 2780-990 Porto Salvo, Portugal (c) LAMSADE, Universite Paris-Dauphine, Place du Marechal De Lattre de Tassigny, 75 775 Paris Cedex 16, France

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.10.001 Byline: Mohsen S. Sajadieh, Mohammad R. Akbari Jokar, Mohammad Modarres Keywords: Coordinated vendor-buyer; Integrated production-inventory; Stochastic lead-time Abstract: This paper develops an approach to determine the optimal production and shipment policy for an integrated vendor-buyer problem. The vendor manufactures the product in batches at a finite rate and ships the output to the buyer. All shipments to the buyer are equal-sized batches. Despite previous papers in the literature, we assume that the supply lead-time between vendor and buyer is stochastic and shortage is also allowed. The objective is to minimize the expected total cost of both buyer and vendor. We derive the expected annual integrated total cost function and propose an analytic solution procedure to determine the optimal policy. To illustrate the significance of cost-reduction of the integrated approach in comparison with independent decisions by buyer or vendor, some numerical examples are also presented. Author Affiliation: Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.08.012 Byline: Sancho Salcedo-Sanz, Emilio G. Ortiz-Garcia, Angel M. Perez-Bellido, Antonio Portilla-Figueras, Francisco Lopez-Ferreras Abstract: This paper proposes a linear programming (LP)-guided Hopfield-genetic algorithm for a class of combinatorial optimization problems which admit a 0-1 integer linear programming. The algorithm modifies the updating order of the binary Hopfield network in order to obtain better performance of the complete hybrid approach. We theoretically analyze several different updating orders proposed. We also include in the paper a novel proposal to guide the Hopfield network using the crossover and mutation operators of the genetic algorithm. Experimental evidences that show the good performance of the proposed approach in two different combinatorial optimization problems are also included in the paper. Author Affiliation: Department of Signal Theory and Communications, Universidad de Alcala de Henares, Campus Universitario, 28871 Alcala de Henares, Madrid, Spain Article Note: (footnote) [star] This work has been partially supported by Universidad de Alcala and Comunidad de Madrid with a Grant no. CCG07-UAH/TIC-1894, and by Ministerio de Educacion with a Grant no. TEC 2006-07010/TCM. A.M. Perez-Bellido and E.G. Ortiz-Garcia are supported by Universidad de Alcala, under the University F.P.I. grants program.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.08.019 Byline: I. Espejo, A.M. Rodriguez-Chia, C. Valero Abstract: This paper presents a procedure to solve the convex ordered median problem where the distances are measured with l.sub.p-norms. In order to do that, we consider an approximated problem and develop an algorithm based on a gradient descent method that generates a sequence with decreasing objective value. We prove its convergence to the optimal solution of the approximated problem. The paper ends with some computational results of the proposed methodology. Author Affiliation: Department of Statistics and Operations Research, University of Cadiz, Spain

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.06.007 Byline: M. Fatih Tasgetiren (a), Quan-Ke Pan (b), Yun-Chia Liang (c) Abstract: This paper is concerned with solving the single machine total weighted tardiness problem with sequence dependent setup times by a discrete differential evolution algorithm developed by the authors recently. Its performance is enhanced by employing different population initialization schemes based on some constructive heuristics such as the well-known NEH and the greedy randomized adaptive search procedure (GRASP) as well as some priority rules such as the earliest weighted due date (EWDD) and the apparent tardiness cost with setups (ATCS). Additional performance enhancement is further achieved by the inclusion of a referenced local search (RLS) in the algorithm together with the use of destruction and construction (DC) procedure when obtaining the mutant population. Furthermore, to facilitate the greedy job insertion into a partial solution which will be employed in the NEH, GRASP, DC heuristics as well as in the RLS local search, some newly designed speed-up methods are presented for the insertion move for the first time in the literature. They are novel contributions of this paper to the single machine tardiness related scheduling problems with sequence dependent setup times. To evaluate its performance, the discrete differential evolution algorithm is tested on a set of benchmark instances from the literature. Through the analyses of experimental results, its highly effective performance with substantial margins both in solution quality and CPU time is shown against the best performing algorithms from the literature, in particular, against the very recent newly designed particle swarm and ant colony optimization algorithms of Anghinolfi and Paolucci [A new discrete particle swarm optimization approach for the single machine total weighted tardiness scheduling problem with sequence dependent setup times. European Journal of Operational Research 2007; doi:10.1016/j.ejor.2007.10.044] and Anghinolfi and Paolucci [A new ant colony optimization approach for the single machine total weighted tardiness scheduling problem. http://www.discovery.dist.unige.it/papers/Anghinolfi_Paolucci_ACO.pdf, respectively. Ultimately, 51 out of 120 overall aggregated best known solutions so far in the literature are further improved while other 50 instances are solved equally. Author Affiliation: (a) Department of Operations Management and Business Statistics, Sultan Qaboos University, Al Khod P.O.Box 20, Muscat, Sultanate of Oman (b) College of Computer Science, Liaocheng University, Liaocheng, Shandong Province 252059, PR China (c) Department of Industrial Engineering and Management, Yuan Ze University, Taiwan, ROC

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.06.001 Byline: Gur Mosheiov (a)(b), Assaf Sarig (b) Abstract: This paper focuses on a minmax due-window assignment problem. The goal is to schedule the jobs and the due-window such that the highest cost among all jobs is minimized. The objective function contains four cost components: for earliness, tardiness, due-window starting time and due-window size. We present a polynomial time solution for the case of a single machine and for a two-machine flow-shop. The cases of parallel identical machines and uniform machines are NP-hard, and simple heuristics and lower bounds are introduced and tested numerically. Scope and purpose Contracts between suppliers and customers often contain a time interval (a due-window), such that goods delivered within this interval are considered to be on time and are not penalized. The due-window starting time and size are determined during sales negotiations with customers. A late and/or large due-window clearly makes the supplier less attractive, and hence the total cost function should increase in the due-window starting time and size. This paper focuses on due-window assignment problems on several classical machine settings: a single machine, a two-machine flow-shop and parallel identical and uniform machines. Author Affiliation: (a) School of Business Administration, The Hebrew University, Jerusalem 91905, Israel (b) Department of Statistics, The Hebrew University, Jerusalem 91905, Israel

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.06.005 Byline: A. Chebouba (a)(b), F. Yalaoui (a), A. Smati (b), L. Amodeo (a), K. Younsi (b), A. Tairi (c) Abstract: In this paper, an ant colony optimization (ACO) algorithm is proposed for operations of steady flow gas pipeline. The system is composed of compressing stations linked by pipelegs. The decisions variables are chosen to be the operating turbocompressor number and the discharge pressure for each compressing station. The objective function is the power consumed in the system by these stations. Until now, essentially gradient-based procedures and dynamic programming have been applied for solving this no convex problem. The main original contribution proposed, in this paper, is that we use an ACO algorithm for this problem. This method was applied to real life situation. The results are compared with those obtained by employing dynamic programming method. We obtain that the ACO is an interesting way for the gas pipeline operation optimization. Author Affiliation: (a) ICD, UTT, FRE CNRS 2848, LOSI, 12 rue Marie Curie, BP 2060, 10010 Troyes Cedex, France (b) Laboratory of Reliability of The Oil Equipments and The Materials, Faculty of Hydrocarbon and Chemistry, University of Boumerdes, Algeria (c) Faculty of Hydrocarbon and Chemistry, University of Boumerdes, Algeria

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.06.002 Byline: Xujin Chen, Jie Hu, Xiaodong Hu Abstract: In this paper, we establish a new model for path planning with interval data which arises in a variety of applications. It is formulated as minimum risk-sum path problem: given a source-destination pair in a network G=(V,E), traveling on each link e in G may take time x.sub.e in a prespecified interval [l.sub.e,u.sub.e] and take risk (u.sub.e-x.sub.e)/(u.sub.e-l.sub.e), the goal is to find a path in G from the source to the destination, together with an allocation of travel times along each link on the path, so that the total travel time of links on the path is no more than a given time bound and the risk-sum over the links on the path is minimized. Our study shows that this new model has two features that make it different from the existing models. First, the minimum risk-sum path problem is polynomial-time solvable, and second, it provides many solutions that vary with time bounds and risk sums and leaves the choice for decision makers. Therefore, the new model is more flexible and easier to use for the path planning with interval data. Author Affiliation: Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing 100190, China Article Note: (footnote) [star] The preliminary version of this paper was presented at the ESCAPE'2007. This work was supported in part by the National Natural Science Foundation of China under Grant no. 70221001, 10531070 and 10771209.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.03.005 Byline: Ali Amiri Abstract: The integration of the issue of survivability of wireless networks in the design process of the backbone network is addressed in this paper. The effectiveness of this integration plays a critical role in the success of the wireless network and the satisfaction of its mobile users. In this paper, we consider the design problem of allocating the backbone links in ATM-based personal communication networks (PCNs) that are survivable under single backbone link failures. Survivability is achieved by selecting two link-disjoint routes in the backbone network between every pair of ATM switches. We also take the novel approach of not only minimizing the diameter of the network as a primary objective but also minimizing the total length of the network as a secondary objective. We propose a new heuristic algorithm to optimize the design of the network based on both objectives. We report the results of an extensive simulation study that show that our algorithm generates backbone networks that can withstand single link failures, have shorter average diameters and smaller total lengths and achieve a higher percentage of admitted calls under a mobile environment. Author Affiliation: Department of MSIS, College of Business, Oklahoma State University, Stillwater, OK 74078, USA

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.03.001 Byline: Changzheng Liu (a), Yueyue Fan (a), Fernando OrdoA[+ or -]ez (b) Abstract: Network protection against natural and human-caused hazards has become a topical research theme in engineering and social sciences. This paper focuses on the problem of allocating limited retrofit resources over multiple highway bridges to improve the resilience and robustness of the entire transportation system in question. The main modeling challenges in network retrofit problems are to capture the interdependencies among individual transportation facilities and to cope with the extremely high uncertainty in the decision environment. In this paper, we model the network retrofit problem as a two-stage stochastic programming problem that optimizes a mean-risk objective of the system loss. This formulation hedges well against uncertainty, but also imposes computational challenges due to involvement of integer decision variables and increased dimension of the problem. An efficient algorithm is developed, via extending the well-known L-shaped method using generalized benders decomposition, to efficiently handle the binary integer variables in the first stage and the nonlinear recourse in the second stage of the model formulation. The proposed modeling and solution methods are general and can be applied to other network design problems as well. Author Affiliation: (a) Department of Civil and Environmental Engineering and Institute of Transportation Studies, University of California, Davis, CA 95616, USA (b) Department of Industrial and System Engineering, University of Southern California, Los Angeles, CA 90089, USA

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.03.002 Byline: A.S. Camanho (a), M.C. Portela (b), C.B. Vaz (c) Abstract: This paper develops a method based on data envelopment analysis (DEA) for efficiency assessments taking into account the effect of non-discretionary factors. A typology that classifies the non-discretionary factors into two groups is proposed: the factors that characterize the external conditions where the decision making units (DMUs) operate (external factors), and the factors that are internal to the production process but cannot be controlled by the decision makers (internal factors). This paper proposes an enhanced DEA model that accommodates non-discretionary inputs and outputs and treats them differently depending on their classification as internal or external to the production process. This generalized model integrates the previous approaches for dealing with non-discretionary variables described in the DEA literature. The model defines the efficient frontier based exclusively on the discretionary variables and internal non-discretionary factors, but the potential peers of each DMU are restricted to other units facing comparable external conditions (represented by the external non-discretionary factors). The peer selection criteria implemented in the DEA model is informed by decision makers' opinion. The applicability of the model developed is illustrated with a real-world assessment of retailing stores. Author Affiliation: (a) Faculdade de Engenharia, Universidade do Porto, Rua Dr. Roberto Frias, 4200-465 Porto, Portugal (b) Faculdade de Economia e Gestao, Universidade Catolica Portuguesa, Rua Diogo Botelho, 1327, 4169-005 Porto, Portugal (c) Escola Superior de Tecnologia e Gestao, Instituto Politecnico de Braganca, Campus Santa Apolonia, 134, 5301-857 Braganca, Portugal

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2008.02.012 Byline: Arshia Ahi, Mir.B. Aryanezhad, Behzad Ashtiani, Ahmad Makui Abstract: This paper deals with the cellular manufacturing system (CMS) that is based on group technology (GT) concepts. CMS is defined as identifying the similar parts that are processed on the same machines and then grouping them as a cell. The most proposed models for solving CMS problems are focused on cell formation and intracellular machine layout problem while cell layout is considered in few papers. In this paper we apply the multiple attribute decision making (MADM) concept and propose a two-stage method that leads to determine cell formation, intracellular machine layout and cell layout as three basic steps in the design of CMS. In this method, an initial solution is obtained from technique for order preference by similarity to the ideal solution (TOPSIS) and then this solution is improved. The results of the proposed method are compared with well-known approaches that are introduced in literature. These comparisons show that the proposed method offers good solutions for the CMS problem. The computational results are also reported. Author Affiliation: Department of Industrial Engineering, Iran University of Science and Technology (IUST), Narmak, 16846_13114, Tehran, Iran

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2007.12.013 Byline: Ruben Ruiz (a), Ali Allahverdi (b) Abstract: This paper studies the flowshop scheduling problem with a complex bicriteria objective function. A weighted sum of makespan and maximum tardiness subject to a maximum tardiness threshold value is to be optimized. This problem, with interesting potential applications in practice, has been sparsely studied in the literature. We propose global and local dominance relationships for the three-machine problem and a fast and effective genetic algorithm (GA) for the more general m-machine case. The proposed GA incorporates a novel three-phase fitness assignment mechanism specially targeted at dealing with populations in which both feasible as well as infeasible solutions might coexist. Comprehensive computational and statistical experiments show that the proposed GA outperforms the two most effective existing heuristics by a considerable margin in all scenarios. Furthermore, the proposed GA is also faster and able to find more feasible solutions. It should be noted that when the weight assigned to maximum tardiness is zero, then the problem is reduced to minimizing makespan subject to a maximum tardiness threshold value. Heuristics for both problems have been provided in the literature recently but they have not been compared. Another contribution of this paper is to compare these recent heuristics with each other. Author Affiliation: (a) Instituto Tecnologico de Informatica, Universidad Politecnica de Valencia, Camino de Vera S/N, 46021, Valencia, Spain (b) Department of Industrial and Management Systems Engineering, College of Engineering and Petroleum, Kuwait University, P.O. Box 5969, Safat, Kuwait

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2007.12.009 Byline: D.R. Goossens, F.C.R. Spieksma Abstract: In a combinatorial auction, multiple items are for sale simultaneously to a set of buyers. These buyers are allowed to place bids on subsets of the available items. A special kind of combinatorial auction is the so-called matrix bid auction, which was developed by Day [Expressing preferences with price-vector agents in combinatorial auctions. PhD thesis, University of Maryland; 2004]. The matrix bid auction imposes restrictions on what a bidder can bid for a subsets of the items. This paper focusses on the winner determination problem, i.e. deciding which bidders should get what items. We discuss the computational complexity of the winner determination problem for a special case of the matrix bid auction. We present two mathematical programming formulations for the general matrix bid auction winner determination problem. Based on one of these formulations, we develop two branch-and-price algorithms to solve the winner determination problem. Finally, we present computational results for these algorithms and compare them with results from a branch-and-cut approach based on Day and Raghavan [Matrix bidding in combinatorial auctions. Manuscript; 2006]. Author Affiliation: ORSTAT, K.U.Leuven, Naamsestraat 69, 3000 Leuven, Belgium Article Note: (footnote) [star] This research was partially supported by FWO Grant No. G.0114.03; an extended abstract corresponding to this paper has been accepted for the 6th Workshop on Experimental Algorithms, Rome.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2007.11.002 Byline: Dirk Briskorn, Andreas Drexl Abstract: Generally speaking in sports competition a number of teams play against each other over a period of time according to a certain scheme. The round robin scheme is very popular in many team sports like soccer and basketball. In this paper we study several basic variants of round robin tournaments. Additionally, we examine real world issues that have to be considered when constructing a sports league schedule. We consider constraints imposed by third parties such as security aspects and legal requirements. Moreover, we analyze constraints aiming at attractive and fair sports league schedules. Throughout this paper integer programming models are the means to formally define what the particular problem under consideration is all about. Moreover, the standard solver Cplex is used in order to compute optimal solutions for small- to medium-size instances. Computational results indicate which particular constraint to relax in order to come up with acceptable schedules in reasonable time. Author Affiliation: Christian-Albrechts-Universitat zu Kiel, Institut fur Betriebswirtschaftslehre, Olshausenstr. 40, 24098 Kiel, Germany

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2007.10.021 Byline: Guenther Fuellerer (a), Karl F. Doerner (a), Richard F. Hartl (a), Manuel Iori (b) Abstract: In this paper a combination of the two most important problems in distribution logistics is considered, known as the two-dimensional loading vehicle routing problem. This problem combines the loading of the freight into the vehicles, and the successive routing of the vehicles along the road network, with the aim of satisfying the demands of the customers. The problem is solved by different heuristics for the loading part, and by an ant colony optimization (ACO) algorithm for the overall optimization. The excellent behavior of the algorithm is proven through extensive computational results. The contribution of the paper is threefold: first, on small-size instances the proposed algorithm reaches a high number of proven optimal solutions, while on large-size instances it clearly outperforms previous heuristics from the literature. Second, due to its flexibility in handling different loading constraints, including items rotation and rear loading, it allows us to draw qualitative conclusions of practical interest in transportation, such as evaluating the potential savings by permitting more flexible loading configurations. Third, in ACO a combination of different heuristic information usually did not turn out to be successful in the past. Our approach provides an example where an ACO algorithm successfully combines two completely different heuristic measures (with respect to loading and routing) within one pheromone matrix. Author Affiliation: (a) Department of Business Administration, University of Vienna, Bruenner Strasse 72, 1210 Vienna, Austria (b) DISMI, University of Modena and Reggio Emilia, Via Amendola 2, 42100 Reggio Emilia, Italy

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2007.09.005 Byline: Xiao-Bing Hu, Ezequiel Di Paolo Abstract: Aircraft arrival sequencing and scheduling (ASS) is a major issue in the daily air traffic control (ATC) operations. This paper reports on the application of genetic algorithms (GAs) to tackle the ASS problem in multi-runway systems. Most existing GAs for ASS are confronted with feasibility and efficiency problems in the design of their evolutionary operators, particularly the crossover. The new GA reported in this paper uses the following relationship between aircraft to construct chromosomes. This makes it possible to design a highly efficient crossover operator-uniform crossover, which is hardly applicable to those GAs designed directly based on the order of aircraft in arrival queues. The main benefit from the proposed uniform crossover operator is the effectiveness and efficiency in identifying, inheriting and protecting common sub-traffic-sequences without sacrificing the capability of diversifying chromosomes, which is demonstrated in the extensive comparative simulation study. By adopting the strategy of receding horizon control, the reported GA exhibits a good potential of real-time implementation in the ASS problem. Author Affiliation: Department of Informatics, University of Sussex, Falmer, Brighton, BN1 9QH, UK Article Note: (footnote) [star] This work is supported by EPSRC Grant EP/C51632X/1.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2007.04.003 Byline: Patrizia Beraldi (a), Gianpaolo Ghiani (b), Antonio Grieco (b), Emanuela Guerriero (b) Abstract: In this paper we develop new rolling-horizon and fix-and-relax heuristics for the identical parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs. Unlike previous papers, our procedures are based on a compact formulation relying on the hypotheses of identical machines. This feature makes our approach suitable for large-scale applications (with hundreds of machines) arising in the textile and fiberglass industries. Moreover, our procedures are shown to provide a feasible solution for any feasible instance. Comparisons with lower bounds provided by a truncated branch-and-bound show that the gap between the best heuristic solution and the lower bound never exceeds 3%. Author Affiliation: (a) Dipartimento di Elettronica, Informatica e Sistemistica and Excellence Center on High Performance Computing, Universita degli Studi della Calabria, 87030 Rende (CS), Italy (b) Dipartimento di Ingegneria dell'Innovazione, Universita degli Studi di Lecce, 73100 Lecce, Italy

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2007.04.002 Byline: Fernando C. Gomes (a), Claudio N. Meneses (b), Panos M. Pardalos (b), Gerardo Valdisio R. Viana (a)(c) Abstract: In this paper we describe and implement a parallel algorithm to find approximate solutions for the Closest String Problem (CSP). The CSP, also known as Motif Finding problem, has applications in Coding Theory and Computational Biology. The CSP is NP-hard which motivates us to think about heuristics to solve large instances. Several approximation algorithms have been designed for the CSP, but all of them have a poor performance guarantee. Recently some researchers have shown empirically that integer programming techniques can be successfully used to solve moderate-size instances (10-30 strings each of which is 300-800 characters long) of the CSP. However, real-world instances are larger than those tested. In this paper we show how a simple heuristic can be used to find near-optimal solutions to that problem. We implemented a parallel version of this heuristic and report computational experiments on large-scale instances. These results show the effectiveness of our approach. Author Affiliation: (a) Department of Computer Science, Federal University of Ceara, Brazil (b) Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, FL 32611, USA (c) Computer Science Department, State University of Ceara, Brazil Article Note: (footnote) [star] This work has been partially supported by NSF, NIH and CRDF grants. A preliminary version of this paper appeared at the proceedings of the I International Symposium on Mathematical and Computational Biology, November 2004, Brazil.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2007.01.024 Byline: Yu-Chung Tsao, Gwo-Ji Sheen Abstract: We study the problem of dynamic pricing, promotion and replenishment for a deteriorating item subject to the supplier's trade credit and retailer's promotional effort. In this paper we adopt a price- and time-dependent demand function to model the finite time horizon inventory for deteriorating items. The objective of this paper is to determine the optimal retail price, the promotional effort and the replenishment quantity so that the net profit is maximized. We discuss the properties and develop an algorithm for solving the problem described. The numerical analyses show that an appropriate promotion policy can benefit the retailer and that the promotion policy is important, especially for deteriorating items. Furthermore dynamic decision-making is shown to be superior to fixed decision-making in terms of profit maximization. Some special cases, such as with no credit period and for non-deteriorating items, are discussed as is the influence of the time-varying demand, the rate of deterioration and the credit period on the retailer behavior. Author Affiliation: Institute of Industrial Management, National Central University, Chung-Li 320, Taiwan

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2007.01.019 Byline: Alan Erera, Burak Karacik, Martin Savelsbergh Abstract: This paper describes a scheme for the dynamic management of linehaul drivers developed for a large US less-than-truckload (LTL) carrier. Virtually all scheduling problems faced by transportation service providers are complicated by time-constrained vehicle operators that can be renewed only after resting. LTL driver scheduling is further complicated by the fact that trucking moves, unlike passenger airline flights or train dispatches, are not pre-scheduled. The technology developed in this paper combines greedy search with enumeration of time-feasible driver duties, and is capable of generating in a matter of minutes cost-effective driver schedules covering 15,000-20,000 loads and satisfying a variety of real-life driver constraints. Computational results justify the algorithmic design choices made in the development of the scheme, and a comparison with real-world dispatch data indicates that the technology produces driver schedules of very high quality. Author Affiliation: The Supply Chain Logistics Institute, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2006.10.008 Byline: Y.A. Rios-Solis, F. Sourd Abstract: We consider the parallel machine scheduling problem where jobs have different earliness-tardiness penalties and a restrictive common due date. This problem is NP-hard in the strong sense. In this paper we define an exponential size neighborhood for this problem and prove that finding the local minimum in it is an NP-hard problem. The main contribution of this paper is to propose a pseudo-polynomial algorithm that finds the best solution of the exponential neighborhood. Additionally, we present some computational results. Author Affiliation: LIP6-University of Paris VI, 4 Place Jussieu, 75252 Paris Cedex 05, France

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2006.10.012 Byline: Zhipeng Lu, Wenqi Huang Abstract: In this paper, we develop a new algorithm that incorporates the improved PERM into an already existing simple deterministic heuristic, the principle of maximum cave degree for corner-occupying actions, to solve the problem of packing equal or unequal circles into a larger circle container. We compare the performance of our algorithm on several problem instances taken from the literature with previous algorithms. The computational results show that the proposed approach produces high-quality solutions within reasonable computational times. Although our algorithm is less efficient than Zhang's for several large-scale equal-size instances, it is noteworthy that for several unequal circle instances we found new lower bounds missed in previous papers. Author Affiliation: School of Computer Science, Huazhong University of Science and Technology, Wuhan, Hubei Province 430074, China

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2006.09.026 Byline: Byeong Seok Ahn (a), Kyung Sam Park (b) Abstract: This paper is concerned with procedures for ranking discrete alternatives when their values are evaluated precisely on multiple attributes and the attribute weights are known only to obey ordinal relations. There are a variety of situations where it is reasonable to use ranked weights, and there have been various techniques developed to deal with ranked weights and arrive at a choice or rank alternatives under consideration. The most common approach is to determine a set of approximate weights (e.g., rank-order centroid weights) from the ranked weights. This paper presents a different approach that does not develop approximate weights, but rather uses information about the intensity of dominance that is demonstrated by each alternative. Under this approach, several different, intuitively plausible, procedures are presented, so it may be interesting to investigate their performance. These new procedures are then compared against existing procedures using a simulation study. The simulation result shows that the approximate weighting approach yields more accurate results in terms of identifying the best alternatives and the overall rank of alternatives. Although the quality of the new procedures appears to be less accurate when using ranked weights, they provide a complete capability of dealing with arbitrary linear inequalities that signify possible imprecise information on weights, including mixtures of ordinal and bounded weights. Author Affiliation: (a) College of Business Administration, Chung-Ang University, 221 Heukseok, Dongjak, Seoul 156-756, South Korea (b) Business School, Korea University, Anam-5Ga, Seongbuk, Seoul 136-701, South Korea

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2006.08.013 Byline: Andreas C. Nearchou Abstract: The problem of scheduling multiple jobs on a single machine so that they are completed by a common specified date is addressed in this paper. This type of scheduling set costs depend on whether a job is finished before (earliness) or after (tardiness) the specified due date. The objective is to minimize a summation of earliness and tardiness penalty costs. Minimizing these costs pushes the completion time of each job as close as possible to the due date. The use of differential evolution as the optimization heuristic to solve this problem is investigated in this paper. Computational experiments over multiple (280 in total) public benchmark problems with up to 1000 jobs to be scheduled show the effectiveness of the proposed approach. The results obtained are of high quality putting new upper bounds to 60% of the benchmark instances. Author Affiliation: Department of Business Administration, University of Patras, 26 500 Rio-Patras, Greece

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2006.08.014 Byline: Claudio Alves, J.M. Valerio de Carvalho Abstract: Many heuristic approaches have been proposed in the literature for the multiple length cutting stock problem, while only few results have been reported for exact solution algorithms. In this paper, we present a new branch-and-price-and-cut algorithm which outperforms other exact approaches proposed so far. Our conclusions are supported on many computational experiments conducted on instances from the literature. In the second part of the paper, we investigate the use of valid dual inequalities within the previous algorithm. We show how column generation can be accelerated in all the nodes of our branching tree using such inequalities. Until now, dual inequalities have been applied only for original linear programming relaxations. Their validity within a branch-and-bound procedure has never been investigated. Our computational experiments show that extending these inequalities to the whole branch-and-bound tree can significantly improve the convergence of our branch-and-price-and-cut algorithm. Author Affiliation: Departamento de Producao e Sistemas, Escola de Engenharia, Universidade do Minho, 4710-057 Braga, Portugal

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2006.03.006 Byline: Richard L. Church Abstract: The p-median problem is perhaps one of the most well-known location-allocation models in the location science literature. It was originally defined by Hakimi in 1964 and 1965 and involves the location of p facilities on a network in such a manner that the total weighted distance of serving all demand is minimized. This problem has since been the subject of considerable research involving the development of specialized solution approaches as well as the development of many different types of extended model formats. One element of past research that has remained almost constant is the original ReVelle-Swain formulation [ReVelle CS, Swain R. Central facilities location. Geographical Analysis 1970;2:30-42]. With few exceptions as detailed in the paper, virtually no new formulations have been proposed for general use in solving the classic p-median problem. This paper proposes a new model formulation for the p-median problem that contains both exact and approximate features. This new p-median formulation is called Both Exact and Approximate Model Representation (BEAMR). We show that BEAMR can result in a substantially smaller integer-linear formulation for a given application of the p-median problem and can be used to solve for either an exact optimum or a bounded, close to optimal solution. We also present a methodological framework in which the BEAMR model can be used. Computational results for problems found in the OR_library of Beasley [A note on solving large p-median problems. European Journal of Operational Research 1985;21:270-3] indicate that BEAMR not only extends the application frontier for the p-median problem using general-purpose software, but for many problems represents an efficient, competitive solution approach. Author Affiliation: Department of Geography and The National Center for Geographic Information and Analysis, University of California at Santa Barbara, Santa Barbara, CA 93106-4060, USA

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2006.03.005 Byline: Enrique Dominguez, Jose MuA[+ or -]oz Abstract: There exist several neural techniques for solving NP-hard combinatorial optimization problems. At the beginning of the 1980s, recurrent neural networks were shown to be able to solve optimization problems. Criticism of this approach includes the tendency of recurrent neural networks to produce infeasible solutions and poor local minima. This paper proposes a new technique which always provides feasible solutions and removes the tuning phase since the constraints are incorporated in the neural architecture instead of the energy function, therefore the tuning parameters are unnecessary. One of the most popular and well-known facility location problems is the p-median problem, which concerns the location of p facilities (or medians) in order to minimize the total weighted distance between the demand points and the facilities. There exist several heuristics to find optimal solutions of the problem based on the traditional formulation. In this paper a new formulation for the p-median problem based on two types of decision variables and with only n+p linear equality constraints is presented, where n is the number of demand points or customers and p is the number of facilities (medians). Also, a competitive recurrent neural network is proposed for this problem. The neural network consists of two layers (allocation layer and location layer) with 2np process units. The process units constitute n+p groups, where only one process unit per group is active at the same time and process units of the same layer are updated in parallel. Moreover, the energy function (objective function) always decreases or remains constant as the system evolves according to the dynamical rule proposed. The effectiveness and efficiency of our algorithm for different problem sizes are analyzed in comparison to conventional heuristic methods. The results show that our recurrent neural network generates good solutions with a reasonable computational effort. Author Affiliation: Department of Computer Science, University of Malaga,Campus Teatinos s/n, 29071 Malaga, Spain

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2006.02.021 Byline: Ricardo Josa-Fombellida (a), Juan Pablo Rincon-Zapatero (b) Abstract: In this paper we consider the optimal management of an aggregated dynamic pension fund. There are n classes of workers whose salaries are stochastic. A portion of the salary is contributed to the funding process and the manager invests in a portfolio with m risky assets and a risk-free security. The main objective is to minimize the cost of contributions in a bounded horizon T and to maximize the utility of final surplus, measured as the relative fund level respect to the mean salary. The aim of the paper is to describe the properties of fund allocation and optimal contribution when salaries differ across contributors to the fund. Author Affiliation: (a) Dpto. de Estadistica e Investigacion Operativa, Universidad de Valladolid, P. Prado de la Magdalena s/n, 47005, Valladolid, Spain (b) Dpto. de Economia, Universidad Carlos III de Madrid, C/ Madrid 126, 28903 Getafe-Madrid, Spain Article Note: (footnote) [star] Both authors gratefully acknowledge financial support from Consejeria de Educacion y Cultura de la Junta de Castilla y Leon (Spain) under project VA099/04 and Spanish Ministerio de Ciencia y Tecnologia and FEDER funds under project BFM2002-00425. We are indebted to an anonymous referee for the criticisms and valuable comments.