Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2007.10.019 Byline: Kazuki Matsumoto (a), Hiroyoshi Miwa (b), Toshihide Ibaraki (b) Keywords: Scheduling; Corrugated paper; Complexity; Contiguous set; Integer programming Abstract: Corrugated paper is produced by gluing three types of papers of the same breadth. Given a set of orders, we first assign each order to one of the standard breadths, and then sequence those assigned to each standard breadth so that they are continuously manufactured from the three rolls of the specified standard breadth equipped in the machine called corrugator. Here we are asked to achieve multi-goals of minimizing total length of roll papers, total loss of papers caused by the differences between standard breadths and real breadths of the orders, and the number of machine stops needed during production. We use integer programming to assign orders to standard breadths, and then develop a special purpose algorithm to sequence the orders assigned to each standard breadth. This is a first attempt to handle scheduling problems of the corrugator machine. Author Affiliation: (a) Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Sakyo-ku, Kyoto 606-8501, Japan (b) Department of Informatics, School of Science and Technology, Kwansei Gakuin University, 2-1 Gakuen Sanda, Hyogo 669-1337, Japan Article History: Received 24 March 2007; Accepted 5 October 2007

Keywords Transportation; Routing; Set orienteering; Matheuristic Highlights * The paper proposes an adaptive memory matheuristic for the set orienteering problem. * Local search is equipped with mathematical programming components. * Solution reconstruction mechanisms exploit high-quality node sequences stored in an adaptive memory structure. * The algorithm outperforms the results of the state-of-the-art methodologies. * New very large-scale test problems are introduced and solved for the first time. Abstract This paper proposes a novel matheuristic algorithm for the Set Orienteering Problem (SOP). The set orienteering problem generalizes the Orienteering Problem (OP) by considering customers to be divided into mutually exclusive clusters. The profit associated with each cluster is collected by visiting at least one of the customers belonging to this cluster. The problem calls for the determination of the closed route that maximizes the collected profit without violating a given maximum route duration. We propose a matheuristic algorithm based on local search. The proposed algorithm is equipped with mathematical programming components for dealing with various subproblems, as well as an adaptive memory structure for producing high-quality starting solutions. Promising and diverse solutions are collected and multiple solution reconstruction mechanisms are presented. Extensive computational experiments are conducted for parameter tuning, and for evaluating the contribution of the mathematical programming components and the adaptive memory mechanism. The proposed solution approach is compared against previously published SOP algorithms. It produces the best solutions for 98.20% of the instances of the classic SOP benchmark data set. For 102 of the total 612 instances a new best solution is obtained. In addition, a new large data set of 304 instances is introduced with instances of up to 3162 customers and 634 clusters to evaluate the scalability of the proposed algorithm, and the effectiveness of the various adaptive memory schemes. The proposed algorithm manages to outperform or match the best-known solution for 281 out of 304 instances when compared with a state-of-the-art open source SOP algorithm. Author Affiliation: Department of Management Science and Technology, School of Business, Athens University of Economics and Business, Athens, Greece * Corresponding author. Article History: Received 12 March 2022; Accepted 7 February 2023 Byline: Michael Dontas [mdontas@aueb.gr], Georgios Sideris [geosideris@aueb.gr], Eleftherios G. Manousakis [lmanousakis@aueb.gr] (*), Emmanouil E. Zachariadis [ezach@aueb.gr]

Keywords Multiple objective programming; Branch and bound; Combinatorial optimization; Linear relaxation; Warm-starting Highlights * Develops a branch-and-bound algorithm for multi-objective integer problems. * Uses the linear relaxation as a lower bound set in the algorithm. * Warm-starts the linear relaxation using information from the father node. * Warm-starting the linear relaxation improves efficiency considerably. * Reports extensive computational results. Abstract In this paper we propose a generic branch-and-bound algorithm for solving multi-objective integer linear programming problems. In the recent literature, competitive frameworks has been proposed for bi-objective 0--1 problems, and many of these frameworks rely on the use of the linear relaxation to obtain lower bound sets. When increasing the number of objective functions, however, the polyhedral structure of the linear relaxation becomes more complex, and consequently requires more computational effort to obtain. In this paper we overcome this obstacle by speeding up the computations. To do so, in each branching node we use information available from its father node to warm-start a Bensons-like algorithm. We show that the proposed algorithm significantly reduces the CPU time of the framework on several different problem classes with three, four and five objective functions. Moreover, we point out difficulties that arise when non-binary integer variables are introduced in the models, and test our algorithm on problem that contains non-binary integer variables too. Author Affiliation: Department of Economics and Business Economics, School of Business and Social Sciences, Aarhus University, Fuglesangs Allé 4, DK-8210 Aarhus V, Denmark * Corresponding author. Article History: Received 5 August 2021; Accepted 31 January 2022 Byline: Nicolas Forget [nforget@econ.au.dk] (*), Sune Lauth Gadegaard, Lars Relund Nielsen

Keywords Packing; 2D bin packing; Guillotine; Heuristic; Variable-sized bins Highlights * Heuristic for solving the 2D bin packing problem with guillotine constraints. * Supports variants with variable-sized bins and 90-degree rotation of items. * Combines the ruin and recreate paradigm with a goal-driven approach. * Experiments demonstrate the effectiveness of the introduced heuristic. Abstract This paper addresses the two-dimensional bin packing problem with guillotine constraints. The problem requires a set of rectangular items to be cut from larger rectangles, known as bins, while only making use of edge-to-edge (guillotine) cuts. The goal is to minimize the total bin area needed to cut all required items. This paper also addresses variants of the problem which permit 90.sup.[ring operator] rotation of items and/or a heterogeneous set of bins. A novel heuristic is introduced which is based on the ruin and recreate paradigm combined with a goal-driven approach. When applying the proposed heuristic to benchmark instances from the literature, it outperforms the current state-of-the-art algorithms in terms of solution quality for all variants of the problem considered. Author Affiliation: KU Leuven, Department of Computer Science, NUMA, Belgium * Corresponding author. Article History: Received 13 January 2021; Accepted 17 November 2021 Byline: Jeroen Gardeyn [jeroen.gardeyn@kuleuven.be] (*), Tony Wauters [tony.wauters@kuleuven.be]

Keywords Humanitarian coverage path planning; Unmanned aerial vehicle routing; Greedy randomized adaptive search procedure Highlights * A novel approach for humanitarian coverage path planning using UAVs. * The cumulative UAV routing problem formulation. * Three effective multithreaded GRASP-VND metaheuristic implementations. * Obtained best known solutions for the cumulative capacitated vehicle routing problem. Abstract This paper presents a Cumulative Unmanned Aerial Vehicle Routing Problem (CUAVRP) approach to optimize Humanitarian Coverage Path Planning (HCPP). Coverage path planning consists of finding the route which covers every point of a certain area of interest. This paper considers a Search & Rescue mission, using a homogeneous fleet of Unmanned Aerial Vehicles (UAVs). In this scenario, the objective is to minimize the sum of arrival times at all points of the area of interest, thus, completing the search with minimum latency. The HCPP problem is transformed into a Vehicle Routing Problem by using an approximate cellular decomposition technique to discretize the area into a grid, where the rectangles represent the UAV sensor's field of view. The center points of the formed rectangles, become the nodes used for a UAV routing problem. This approach uses the objective of minimizing the sum of arrival times at customers, found in the Cumulative Capacitated Vehicle Routing Problem (CCVRP), adjusted for the Search & Rescue Coverage Path Planning using UAVs. The Min-max objective is also implemented and tested. Three versions of a Parallel Weighted Greedy Randomized Adaptive Search Procedure - Variable Neighborhood Decent (GRASP-VND) algorithm is implemented to solve the Cumulative UAV Routing Problem for Humanitarian Coverage Path Planning. Author Affiliation: Technical University of Crete, School of Production Engineering and Management, University Campus, Chania 73100, Greece * Corresponding author. Article History: Received 2 November 2020; Accepted 7 September 2021 Byline: Nikolaos A. Kyriakakis [nkyriakakis@isc.tuc.gr], Magdalene Marinaki [magda@dssl.tuc.gr], Nikolaos Matsatsinis [nikos@ergasya.tuc.gr], Yannis Marinakis [marinakis@ergasya.tuc.gr] (*)

Keywords Routing; Three-dimensional loading; Split delivery; Column generation Highlights * We study the split heterogeneous vehicle routing problem with loading constraints. * A column generation-based heuristic algorithm is proposed. * Straightforward loading patterns are produced using a heuristic algorithm. * The proposed algorithm requires less running time than literature algorithms. * Experiments are performed on benchmark and large real-world instances. Abstract This paper introduces a complex real-world problem on a large scale that combines the split delivery heterogeneous vehicle routing problem with three-dimensional loading and considers new routing and loading constraints. The problem aims to find a set of routes with minimum transportation cost by satisfying the demand of all customers and loading constraints. We propose a column generation-based heuristic algorithm that employs three heuristic algorithms to solve the subproblem and a hybrid algorithm for loading. Computational experiments on the literature instances indicate that the proposed algorithm can produce very near solutions to the literature algorithm's solutions in significantly shorter running times. This paper introduces real-world instances with 230 to 850 customers, several times larger than the existing benchmarks. The results of the proposed algorithm for real-world instances are effective, and compared to the current situation, it leads to a reduction of 20% in the average total cost of transportation. Also, the average number of vehicles is reduced by 36%. Author Affiliation: Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan 84156-83111, Iran * Corresponding author. Article History: Received 20 August 2020; Accepted 14 August 2021 Byline: Maryam Rajaei, Ghasem Moslehi [moslehi@iut.ac.ir] (*), Mohammad Reisi-Nafchi

Keywords Flexible manufacturing systems; Scheduling; Iterated local search; Tool switching; Sequence-dependent setup times Highlights * The job sequencing and tool switching problem with non-identical parallel machines is studied. * Three different objective functions are considered. * Machine-dependent processing and tool switching times are taken into account. * A MILP model and several ILS algorithms are proposed. * Computational experiments show the efficiency of the algorithms. Abstract In this paper, a new generalization of the uniform job sequencing and tool switching problem is presented. It considers non-identical parallel machines, which differ in tool magazine capacity and setup times. Applications of the problem can be found in the metal working or semiconductor manufacturing industries when the jobs require different tool sets for processing. The paper provides a Mixed Integer Programming formulation for the job sequencing and tool switching problem with machine-dependent processing and tool switching times under the consideration of three conflicting objectives (minimizing the total flowtime, minimizing the makespan and minimizing the total number of tool switches). Different efficient construction heuristics and Iterated Local Search methods are proposed and evaluated, using 640 new and publicly available instances. The results of the construction heuristics, the Iterated Local Search schemes and a Mixed Integer Programming Solver are discussed. The extensive computational experiments show the merit of the perturbation strategy in order to overcome local optima. It is shown that certain methods are more or less suitable depending on the objective function. Author Affiliation: School of Business, Economics and Information Systems, Chair of Information Systems (Information and IT Service Management), University of Passau, Innstrasse 43, 94032 Passau, Germany Article History: Received 27 March 2020; Accepted 9 May 2021 (footnote)1 http://www.wi.uni-passau.de/ Byline: Dorothea Calmels [dorothea.calmels@uni-passau.de] (1)

Keywords Project scheduling; Nash equilibria; Flow networks; Milestones; Lazy-constraint generation Highlights * The paper studies presence of milestones in a multi-agent project scheduling. * We analyze the problem complexity. * The suggested algorithm is based on a lazy-constraint generation technique. * We investigate the role of milestones to drive the project to the owner's goal. Abstract This paper addresses a project scheduling environment in which the activities are partitioned among a set of agents. The project owner is interested in completing the project as soon as possible. Therefore, she/he defines rewards and penalties to stimulate the agents to complete the project faster. The project owner offers a per-day reward for early project completion and defines intermediate project milestones to be met within specific due dates, with associated per-day penalties. Each agent can, therefore, decide the duration of her/his activities, taking into account linear activity crashing costs, the reward for early project completion, and the penalty arising from violating milestone due-dates. We consider Nash equilibria, i.e., situations in which no agent has an interest in individually changing the duration of any of her/his activities, and in particular, the problem of finding a minimum-makespan equilibrium. This problem is known to be NP-hard, and in this paper, we (i) propose a new and efficient exact algorithmic approach for finding the minimum-makespan equilibrium and (ii) through an extensive computational campaign we evaluate the role played by milestones in driving the project towards the owner's goal. Author Affiliation: (a) Czech Institute of Informatics, Robotics, and Cybernetics, Czech Technical University in Prague, Jugoslávských partyzánu 1580/3, Prague 160 00, Czechia (b) Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche, Università degli Studi di Siena, via Roma 56, Siena 53100, Italy (c) LAAS-CNRS, Université de Toulouse, CNRS, UPS, 7 Avenue du Colonel Roche, Toulouse 31400, France * Corresponding author at: Czech Institute of Informatics, Robotics, and Cybernetics, Czech Technical University in Prague, Jugoslávských partyzánu 1580/3, Prague 160 00, Czechia. Article History: Received 8 January 2020; Accepted 13 January 2021 Byline: Premysl Sucha [suchap@cvut.cz] (*,a,c), Alessandro Agnetis [agnetis@diism.unisi.it] (b), Marko Sidlovský (a), Cyril Briand [briand@laas.fr] (c)

Keywords Finance; Credit risk modelling; Discrete Markov chains; Lumpability Highlights * The paper studies the problem of compliance of internal credit rating models used for pricing and provisioning. * We apply the approximate lumpability method to reduce a Markov chain to an equivalent, lower-dimensional process. * An algorithm to solve the problem of approximate lumpability is proposed, which, often reduces to a closed form solution. * The proposed methodology is applied to multiple examples of credit risk modelling and applications. * The proposed techniques are applicable to other problems related to Markov chain modelling e.g. decision theory and finance. Abstract The aim of this paper is threefold. Firstly, we define the necessary quantities associated to the lumpability of a Markov chain and study their fundamental properties. Secondly, we examine the case of approximate lumpability of a non-lumpable Markov and an efficient method of minimizing the error in the approximation. Finally, we introduce a family of general minimization problems that can be approached using this method and examine applications in credit risk modelling, particularly under recent regulatory changes related to loan classification and provision calculations under IFRS 9. Author Affiliation: (a) Department of Statistics and Stochastic Modelling and Applications Laboratory, Athens University of Economics and Business, 76 Patission Str, 10434 Athens, Greece (b) Department of Mathematics, University of Sussex, Pevensey 2, BN1 9QH Brighton, UK * Corresponding author. Article History: Received 21 October 2019; Revised 8 November 2020; Accepted 10 November 2020 Byline: K. Georgiou (a), G.N. Domazakis (b), D. Pappas (a), A.N. Yannacopoulos [ayannaco@aueb.gr] (*,a)

Keywords Metaheuristics; Biological analogue; Candidate solutions; Evolutionary algorithms; Individuals Highlights * The existing studies assume identical behavior for all candidate solutions. * In nature, we know that individuals do not react similarly to the same stimulus. * This is called character and it is lacking from existing implementations. * In this paper, we emulate the corresponding human social analogue. * We implement the different behaviors with the assistance of a novel mutation operator. Abstract The fundamental unit of each evolutionary algorithm is the individual. Each individual represents a potential solution to the problem at hand. Despite the importance of individual solution for multi-objective algorithms' performance the majority of the existing implementations select a simplistic approach by assuming identical behavior for all candidate solutions of a population. However, from the biological analogue we know that individuals do not react similarly to the same stimulus. This is called character and it is lacking from existing implementations. In this paper, we emulate the corresponding human social analogue by generating individuals that exhibit different behavior when are subject to the same stimulus. The implementation of different behaviors is facilitated through a novel mutation operator. The experimental results favor the proposed approach when compared with other state-of-the-art algorithms for a number of test instances. Author Affiliation: Decision Support Systems Laboratory, Department of Informatics, University of Piraeus, 80, Karaoli & Dimitriou Str., 18534 Piraeus, Greece * Corresponding author. Article History: Received 7 February 2020; Accepted 15 November 2020 Byline: Konstantinos Liagkouras [kliagk@unipi.gr] (*), Konstantinos Metaxiotis [kmetax@unipi.gr]

Keywords Routing; Multi-period; Demand management; Touting; Metaheuristics Highlights * Introducing 'touting', a new demand management technique in dynamic VRPs. * Touting encourages customers to place order earlier. * Proposing several strategies to determine the most relevant customers to tout. * Touting strategies are combined with a rolling-time horizon vehicle routing algorithm. * Empirical evaluation shows that touting allows for more efficient routing. Abstract This paper introduces a dynamic multi-period vehicle routing problem with touting as demand management technique, where customers that have not yet placed an order can be actively encouraged to order a service sooner. Touting the right customers, such as those located nearby customers who already placed orders, allows for more efficient routes over time. However, it also increases the frequency of visits at such touted customers as they are serviced before they would normally require, which leads to smaller demand volumes per visit. To tackle this trade-off, we propose several strategies to decide which customers to tout and when, using the characteristics of the customers as well as the current plan at the time of touting. Specifically, using the demand and the location information, we approach the ones which are close to the current tour, relatively far from the depot and not likely to easily be covered in the near future. This information is then used as a part of different touting strategies, which are further embedded in a rolling-time horizon vehicle routing algorithm to address the multi-period nature of the problem. These different strategies are empirically compared in a simulation based on a real-world waste collection problem. We demonstrate that touting indeed allows to significantly reduce the travel distance in a dynamic vehicle routing problem. Author Affiliation: (a) Sheffield University Management School, Sheffield, S10 1FL, United Kingdom (b) Warwick Business School, University of Warwick, Coventry, CV4 7AL, United Kingdom (c) Mercator Endowed Chair of Demand Management & Sustainable Transport, WHU - Otto Beisheim School of Management, Vallendar 56179, Germany * Corresponding author. Article History: Received 29 October 2021; Accepted 25 February 2023 Byline: Merve Keskin [m.keskin@sheffield.ac.uk] (*,a), Juergen Branke [juergen.branke@wbs.ac.uk] (b), Vladimir Deineko [vladimir.deineko@wbs.ac.uk] (b), Arne K. Strauss [arne.strauss@whu.edu] (c)

Keywords Heuristics; Time-dependent; Green vehicle routing problem; Adaptive large neighborhood search Abstract In recent years, reducing emissions has been important for mitigating global warming and the effects of traffic congestion. As a variant of the green vehicle routing problem (GVRP), the time-dependent GVRP with time windows (TDGVRPTW) accounts for both time-dependent travel times and time window constraints and integrates the minimization of carbon emissions. Therefore, the TDGVRPTW is of great practical interest. In this paper, we design an effective adaptive large neighborhood search (ALNS) algorithm for solving the TDGVRPTW. The proposed algorithm uses a time discretization search (TDS) method to determine the departure time from each customer node, together with efficient feasibility checking procedures. The ALNS algorithm has been extensively tested on benchmark instances derived from the literature. The results show that, for small-size instances for which optimal solutions are known, the proposed algorithm can solve several instances to optimality and that high-quality solutions can be obtained for the instances that are not solved to optimality. For large-size instances involving up to 1000 customers, ALNS is particularly effective in computing solutions using a very limited amount of computing time. Author Affiliation: (a) State Key Laboratory of Synthetic Automation for Process Industries, Institute of Intelligent Data and Systems Engineering, Northeastern University, Shenyang 110819, PR China (b) Division of Engineering Management and Decision Sciences, College of Science and Engineering, Hamad Bin Khalifa University, Qatar Foundation, P.O. Box 34110, Doha, Qatar (c) School of Business Administration, Southwestern University of Finance and Economics, Chengdu 611130, PR China (d) Business School, Liaoning University, Shenyang 110316, PR China (e) Dalian University of Technology, School of Economics and Management, 116024, Dalian, Liaoning, People's Republic of China * Corresponding author. Article History: Received 5 May 2022; Accepted 17 February 2023 Byline: Yiming Liu (a), Baldacci Roberto (b), Jianwen Zhou (a), Yang Yu (e), Yu Zhang (c), Wei Sun [lnusunwei@163.com] (*,d)

Keywords Stochastic programming; Progressive hedging; Parallel computing; Maintenance scheduling; Natural gas trading Highlights * An integration of generation maintenance scheduling and natural gas trading. * A multistage decision-making process considering uncertain natural gas and electricity prices. * The implementation of progressive hedging algorithm with parallel computing technique in a distributed HPC system. * Studied the impact of natural gas generator assets and natural gas contract clauses on the optimal profit for GENCOs. Abstract A preventive maintenance scheduling problem is studied on behalf of generation companies (GENCOs) with natural gas power plants, while taking into account their signed natural gas contracts and the opportunities of purchasing and selling natural gas in the spot market. This paper considers the uncertain prices of both natural gas and electricity in the spot market, and proposes a multistage stochastic mixed integer programming (MSMIP) model seeking the optimal operations regarding maintenance outage scheduling and natural gas trading. Large-scale MSMIP problems suffer not only the curse of dimensionality, but also computational difficulties with both discrete and continuous variables at each stage. To this respect, this paper leverages the progressive hedging algorithm based on scenario-based decomposition to solve large MSMIP problems. The solutions obtained from the algorithm exhibit promising quality under our numerical studies. Due to the independence among all the subproblems after the decomposition, the algorithm is amenable to parallel computing, which leads to faster convergence as demonstrated in the numerical results. Computational experiments also show that it is beneficial to use MSMIP while considering both maintenance planning and natural gas contracting. In addition, the results also indicate the GENCOs with a larger number of small generators perform better than those with a smaller number of big generators. Author Affiliation: (a) College of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing, China (b) Department of Industrial Engineering and Management Systems, University of Central Florida, Orland, FL, USA * Corresponding author. Article History: Received 7 April 2019; Revised 11 March 2020; Accepted 11 March 2020 Byline: Zhouchun Huang (a), Qipeng Phil Zheng [qipeng.zheng@ucf.edu] (*,b)

Keywords Location; Support vector machine; Ramp loss model; Mixed integer programming; Indicator constraints Highlights * Support vector machines with ramp loss models are analyzed. * Strategies for tightening the values of big M parameters of the model are proposed. * The strategies are focused on l.sub.1-norm and l.sub.2-norm cases. * Linear, quadratic and Lagragian relaxation models are solved in the strategies. * The performance of these strategies are tested in simulated and real-life datasets. Abstract This paper considers various models of support vector machines with ramp loss, these being an efficient and robust tool in supervised classification for the detection of outliers. The exact solution approaches for the resulting optimization problem are of high demand for large datasets. Hence, the goal of this paper is to develop algorithms that provide efficient methodologies to exactly solve these optimization problems. These approaches are based on three strategies for obtaining tightened values of the big M parameters included in the formulation of the problem. Two of them require solving a sequence of continuous problems, while the third uses the Lagrangian relaxation to tighten the bounds. The proposed resolution methods are valid for the l.sub.1-norm and l.sub.2-norm ramp loss formulations. They were tested and compared with existing solution methods in simulated and real-life datasets, showing the efficiency of the developed methodology. Author Affiliation: Departamento de Estadistica e Investigacion Operativa, Universidad de Cadiz, Cadiz, Spain * Corresponding author. Article History: Received 28 June 2019; Revised 1 March 2020; Accepted 4 March 2020 Byline: Marta Baldomero-Naranjo [marta.baldomero@uca.es] (*), Luisa I. Martinez-Merino [luisa.martinez@uca.es], Antonio M. Rodriguez-Chia [antonio.rodriguezchia@uca.es]

Keywords Routing; Hours of service regulations; Truck driver scheduling; Bidirectional labeling; Branch-and-price-and-cut Highlights * First bidirectional labeling approach for truck driver routing and scheduling. * Hours of service regulations in the US and the EU can be handled. * Branch-and-price-and-cut algorithm outperforms previous approaches. * The presented algorithm can tackle duration-related cost functions efficiently. Abstract This paper studies the vehicle routing and truck driver scheduling problem where routes and schedules must comply with hours of service regulations for truck drivers. It presents a backward labeling method for generating feasible schedules and shows how the labels generated with the backward method can be combined with labels generated by a forward labeling method. The bidirectional labeling is embedded into a branch-and-price-and-cut approach and evaluated for hours of service regulations in the United States and the European Union. Computational experiments show that the resulting bidirectional branch-and-price-and-cut approach is significantly faster than unidirectional counterparts and previous approaches. Author Affiliation: (a) Johannes Gutenberg University Mainz, Mainz, Germany (b) Kuhne Logistics University, Hamburg, Germany * Corresponding author. Article History: Received 18 July 2019; Revised 22 October 2019; Accepted 24 October 2019 (footnote)[white star] This paper extends and replaces a previous unpublished working paper which focused on hours of service regulations in the United States. Byline: Christian Tilk [tilk@uni-mainz.de] (*,a), Asvin Goel [asvin.goel@the-klu.org] (b)

Keywords OR In energy; Multi-stage robust optimization; Dynamic programming; Economic dispatch; Energy storage Highlights * A multi-stage robust optimization method for an economic dispatch problem. * The system involves renewable generation sources and storage units. * Day-ahead plan is computed under nominal conditions to alleviate conservativeness. * The feasibility of real-time operation is guaranteed for the day-ahead plan. * A new approach for preventing simultaneous charge/discharge problem is proposed. Abstract In this paper, an economic dispatch problem for power grids involving renewable generation and storage units is studied. A multi-stage robust optimization algorithm for computing base dispatches and re-dispatches is proposed. Unlike the other approaches in the literature, the proposed method finds an exact solution to the multi-stage robust optimization problem considered when there are no storage devices or storage devices are ideal (i.e. charging/discharging inefficiencies are neglectable). In the presence of non-ideal storage devices, the algorithm can produce upper-bounding approximations. The devised approximation scheme has two distinguishing features. Firstly, the base dispatches and, especially, multi-stage re-dispatch policies computed are guaranteed to be free of simultaneous charges/discharges. Secondly, it produces lower bounds allowing one to assess the quality of solutions. Optimality and convergence properties of the proposed method are proven and it is compared with other alternatives in the literature through numerical experiments. Results show that significant economic benefits can be achieved compared to the other approaches and solutions could be obtained within acceptable time limits for large-scale problems. Author Affiliation: Yildiz Technical University, Control and Automation Engineering Department, Davutpasa Campus, 34320, Istanbul, Turkey Article History: Received 4 August 2022; Accepted 23 January 2023 Byline: Ugur Yildiran [uyildiran@yildiz.edu.tr]

Keywords Scheduling; Seru; On-line operation; Resource conflicts; Competitive ratio Highlights * A proactive waiting strategy is proposed for SPSs with on-line vision. * A seru may proactively wait even it is ready to be physically constructed. * A nested algorithm is designed for on-line seru scheduling with resource conflicts. * For two seru families, the nested algorithm is proved to be 2[rho]-competitive. * For more than two seru families, 7,290,000 instances are randomly generated. Abstract Seru production systems (SPSs) with quick responsiveness and high flexibility have been applied in many Asian electronic enterprises. An SPS can quickly respond to market demands with changing varieties and fluctuated volumes. Resource conflicts are used to indicate the requirements for a same worker by more than one seru. This paper studies the on-line seru scheduling problem with resource conflicts in limited work space, which decides serus' built-up sequence over time and aims at minimizing the makespan. To keep a balance between quick responsiveness and production efficiency in an SPS, a proactive waiting strategy is proposed and a nested algorithm is structured with an external framework and an internal sequencing policy. The external framework handles resource conflicts among serus and divides serus into groups in which resource conflicts do not exist. The internal sequencing policy acts on each group and decides the built-up sequence for serus. The nested algorithm is proved to be 2[rho]-competitive with two seru families. Performance of the nested algorithm can be enhanced by improving the internal sequencing policy without changing the external framework, which is conformed by computational experiments. With more seru families, experimental results show that the nested-LPT algorithm can adapt to frequent arrivals of orders, complicated resource conflicts, and fluctuating market demands. Author Affiliation: (a) School of Computer Science, Beijing Institute of Technology, Beijing, China (b) Southeast Academy of Information Technology, Beijing Institute of Technology, Putian, China (c) School of Automation, Beijing Institute of Technology, Beijing, China (d) Guangdong Shenling Environmental Systems Co., Ltd., Foshan, China (e) Graduate School of Business, Doshisha University, Kyoto, Japan * Corresponding author. Article History: Received 30 March 2022; Accepted 13 January 2023 Byline: Dongni Li [ldn@bit.edu.cn] (*,a,b), Yuzhou Jiang [jiang_yuzhou@163.com] (a), Jinhui Zhang [zhangjinh@bit.edu.cn] (c), Zihua Cui [zihua.cui@shenling.com] (d), Yong Yin [yyin@mail.doshisha.ac.jp] (e)

Keywords Finance; Blockchain; Decentralized finance; Decentralized clearing; Systemic risk Highlights * Construction of an endogenous decentralized clearing mechanism. * Algorithmic construction of blockchain of accepted bids to clear debt. * Optimal bids and existence of Nash equilibrium for debt clearing. Abstract In this paper, we construct a decentralized clearing mechanism which endogenously and automatically provides a claims resolution procedure. This mechanism can be used to clear a network of obligations through blockchain. In particular, we investigate default contagion in a network of smart contracts cleared through blockchain. In so doing, we provide an algorithm which constructs the blockchain so as to guarantee the payments can be verified and the miners earn a fee. We, additionally, consider the special case in which the blocks have unbounded capacity to provide a simple equilibrium clearing condition for the terminal net worths; existence and uniqueness are proven for this system. Finally, we consider the optimal bidding strategies for each firm in the network so that all firms are utility maximizers with respect to their terminal wealths. We show that a pure strategy Nash equilibrium need not exist, and then look for mixed Nash equilibrium bidding strategies. The implications of these strategies, and more broadly blockchain, on systemic risk are considered. Author Affiliation: (a) Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, USA (b) Department of Mathematics, SUNY at Buffalo, 317 Mathematics Building Buffalo, NY 14260, USA (c) Stevens Institute of Technology, School of Business, Hoboken, NJ 07030, USA * Corresponding author. Article History: Received 20 May 2022; Accepted 16 December 2022 (footnote)1 Work is partially supported by NSF grant DMS-1736414. Byline: Hamed Amini [aminil@ufl.edu] (a), Maxim Bichuch [mbichuch@buffalo.edu] (*,1,b), Zachary Feinstein [zfeinste@stevens.edu] (c)

Keywords Large-scale optimization; Benders decomposition; Stochastic programming; Cut aggregation Highlights * Exact algorithm to solve multicut Benders reformulation of stochastic linear programs. * The algorithm solves a few subproblems at most iterations. * Uses primal stabilization and partial cut aggregation. * Converges faster than classical algorithms on large-scale instances. Abstract This paper introduces a new exact algorithm to solve two-stage stochastic linear programs. Based on the multicut Benders reformulation of such problems, with one subproblem for each scenario, this method relies on a partition of the subproblems into batches. The key idea is to solve at most iterations only a small proportion of the subproblems by detecting as soon as possible that a first-stage candidate solution cannot be proven optimal. We also propose a general framework to stabilize our algorithm, and show its finite convergence and exact behavior. We report an extensive computational study on large-scale instances of stochastic optimization literature that shows the efficiency of the proposed algorithm compared to nine alternative algorithms from the literature. We also obtain significant additional computational time savings using the primal stabilization schemes. Author Affiliation: (a) Université de Bordeaux, CNRS, INRIA, Bordeaux INP, IMB, UMR 5251, F-33400 Talence, France (b) RTE, Paris La Défense, France * Corresponding author. Article History: Received 7 December 2021; Accepted 4 January 2023 Byline: Xavier Blanchot [xavier.blanchot@u-bordeaux.fr] (a,b), François Clautiaux [francois.clautiaux@math.u-bordeaux.fr] (a), Boris Detienne [boris.detienne@math.u-bordeaux.fr] (a), Aurélien Froger [aurelien.froger@math.u-bordeaux.fr] (*,a), Manuel Ruiz [manuel.ruiz@rte-france.com] (b)

Keywords Investment analysis; Real options; Investment timing; Capacity choice Highlights * In the endogenous firm roles with exogenous (fixed) capacity size, where the firm roles are not determined beforehand, we show that the main reason for the most efficient firm to not always be the first investor in the market is the relatively late entry of the most efficient firm as the second firm in the market. * We show that in the case of endogenous firm roles with endogenous capacity size, where the firm roles are not pre-determined, firms enter the market in the order of their cost efficiency. This implies that the most cost-efficient firm always invests first in a triopoly market. * In the designed algorithm, we employ the bisection method at different steps to determine the firms' decisions regarding their investment timing and capacity size in the triopoly market. The algorithm is widely applicable for even more complex models like increasing the number of firms above three and/or allowing firms to invest more than once. Abstract This paper analyzes investment decisions under uncertainty in a triopoly market. We determine the investment timing and the investment size of the firms under the condition that firms hold an asymmetric cost structure. We build on Shibata (European Journal of Operational Research, 2016) who solves this problem with exogenous investment size. He finds that the firm with the lowest cost does not always enter the market as the first investor. However, we obtain that, when extending the analysis for capacity choice, the firm with the lowest cost always enters first in the triopoly market. The designed algorithm, which employs the bisection method at several steps to solve this model, is of value of its own as it can be more generally applied to investment problems in markets with several firms and multiple investment opportunities. Author Affiliation: (a) Department of Econometrics and Operations Research, Tilburg University, Tilburg, the Netherlands (b) ASML Netherlands B.V., Veldhoven, the Netherlands * Corresponding author. Article History: Received 28 May 2022; Accepted 2 December 2022 (footnote)[white star] The authors would like to thank Emanuele Borgonovo (the editor) and anonymous referees for their helpful comments. The authors also thank participants at the 24th Annual International Real Options Conference for their helpful comments. Byline: Farzan Faninam [f.faninam@tilburguniversity.edu] (*,a), Kuno Jï¼M. Huisman (a,b), Peter M. Kort (a)

Keywords Facilities planning and design; Location; Pricing; Leader-follower; Branch-and-cut Highlights * Consider a discrete version of bilevel joint location-pricing problems with finite numbers of mill pricing decisions. * Derive three equivalent single-level mixed-integer linear programming models for the bilevel problems. * Propose a branch-and-cut algorithm for solving large-scale instances, leveraging a specialized bilevel feasibility cut. * Conduct extensive numerical experiments using randomly generated instances and instances from standard testbeds. Abstract The joint optimization of facility location and service charge arises in many industrial and business contexts. This paper investigates a facility location and mill pricing problem (FLMPr), where a company aims to maximize its profit by locating service facilities and setting appropriate service charges to customers. For each facility, the number of pricing levels are finite, and the company will select exactly one level for each facility if it is open. We visualize the problem from a fully decentralized perspective, i.e., each customer acts as an independent decision-maker. Under mill pricing, customers visiting the same facility encounter the same service charge. The problem is formulated as a bilevel program, in which the company makes location and pricing decisions at the upper level, and customers decide whether to seek the service from a facility at the lower level. To solve FLMPr, we leverage three types of closest assignment constraints to reformulate the problem as mixed-integer linear programs (MILPs), which can be directly solved by modern solvers. However, this approach suffers from a time-consuming solver compiling process and cannot handle large-scale instances effectively. This observation motivates us to design a branch-and-cut algorithm by exploring the bilevel structure and deriving a feasibility cut to efficiently eliminate bilevel infeasible solutions. Our extensive experiments reveal that the proposed algorithm can solve large-scale FLMPr satisfactorily and outperforms the MILP approach by a large margin. Finally, we conduct sensitivity analysis and draw interesting observations. Author Affiliation: (a) Institute of High Performance Computing, Agency for Science, Technology and Research (A*STAR), Singapore (b) School of Civil and Environmental Engineering, Nanyang Technological University, Singapore * Corresponding author. Article History: Received 2 November 2021; Revised 26 November 2022; Accepted 29 November 2022 Byline: Yun Hui Lin [liny@ihpc.a-star.edu.sg] (a), Qingyun Tian [qytian@ntu.edu.sg] (*,b)

Keywords Stochastic optimization; Sensitivity analysis; SDDP; Dual SDDP; Relatively complete recourse Highlights * We propose a Dual SDDP algorithm. * We discuss variants of Dual SDDP when relatively complete recourse does not hold. * We study sensitivity analysis of multistage stochastic programs. * We study the application of Dual SDDP to interstage dependent stochastic programs. * Results of numerical simulations on a real-life problem are presented. Abstract In this paper we investigate the dual of a Multistage Stochastic Linear Program (MSLP). By writing Dynamic Programming equations for the dual, we can employ an SDDP type method, called Dual SDDP, which solves these Dynamic Programming equations. allows us to compute a sequence of nonincreasing deterministic upper bounds for the optimal value of the problem. Since the Relatively Complete Recourse (RCR) condition may fail to hold for the dual (even for simple problems), we design two variants of Dual SDDP, namely Dual SDDP with penalizations and Dual SDDP with feasibility cuts, that converge to the optimal value of the dual (and therefore primal when there is no duality gap) problem under mild assumptions. We also show that optimal dual solutions can be obtained using dual information from Primal SDDP (applied to the original primal MSLP) subproblems. As a byproduct of the developed methodology we study sensitivity of the optimal value of the problem as a function of the involved parameters. For the sensitivity analysis we provide formulas for the derivatives of the value function with respect to the parameters and illustrate their application on an inventory problem. Since these formulas involve optimal dual solutions, we need an algorithm that computes such solutions to use them, i.e., we need to solve the dual problem. Finally, as a proof of concept of the tools developed, we present the results of numerical experiments computing the sensitivity of the optimal value of an inventory problem as a function of parameters of the demand process and compare Primal and Dual SDDP on the inventory and a hydro-thermal planning problems. Author Affiliation: (a) School of Applied Mathematics, FGV, Praia de Botafogo, Rio de Janeiro, Brazil (b) Georgia Institute of Technology, Atlanta, GA 30332-0205, USA * Corresponding author. Article History: Received 3 January 2022; Accepted 26 November 2022 Byline: Vincent Guigues [vincent.guigues@fgv.br] (*,a), Alexander Shapiro (b), Yi Cheng (b)

Keywords Routing; Waste collection; Multiple depots; Intermediate facilities; Partial pick-ups Highlights * A Memetic Algorithm for solving a large variety of waste collection problems. * Competitive results for the VRPIF, the MDVRPI and the MDVRP. * Improved results for MDVRPIF instances. * Assessing waste collection infrastructure scenarios for the Brussels Capital Region. Abstract Inspired by a real-life case in the Brussels Capital Region, Belgium, this paper provides a Memetic Algorithm with Sequential Split procedure (MASS) for solving a large variety of waste collection problems with multiple depots, a restricted vehicle fleet at each depot, multiple (intermediate) processing facilities, capacity restrictions per processing facility and partial pick-ups. MASS first generates satisfactory initial solutions which are feasible w.r.t. the shift duration and the vehicle capacity using a novel procedure in which (1) a giant tour is split into vehicle routes, (2) intermediate processing facilities are introduced and (3) waste pick-ups can be split further if profitable. Second, MASS improves these solutions through local search. New test instances are created, which are used to evaluate the performance of MASS's components. We show that MASS provides high-quality feasible solutions by comparing MASS with an exact approach on a small example. Furthermore, MASS is tested on existing instances for the multiple-depot vehicle routing problem (MDVRP), (multi-depot) vehicle routing problem with intermediate facilities ((MD)VRPIF) and the multi-depot vehicle routing problem with inter-depot routes (MDVRPI). MASS shows competitive results for the MDVRP, the VRPIF and the MDVRPI. For the MDVRPIF, MASS obtains better results than those currently found in the literature. To assess its practical value, MASS is used to solve a real-life waste collection problem in the Brussels Capital Region in which alternative scenarios for municipal bio-waste collection and treatment are compared. Author Affiliation: (a) KU Leuven Institute for Mobility, Belgium (b) KU Leuven, Center for Economics and Corporate Sustainability, Faculty of Economics and Business, Campus Brussels, Belgium (c) Vrije Universiteit Amsterdam, School of Business and Economics, Department of Operations Analytics, the Netherlands (d) KU Leuven, Group T, Department of Mechanical Engineering, Centre for Industrial Management, Belgium * Corresponding author. Article History: Received 27 August 2021; Accepted 13 November 2022 Byline: Carolien Lavigne [carolien.lavigne@kuleuven.be] (*,a,b), Dirk Inghels [dirk.inghels@vu.nl] (c), Wout Dullaert [wout.dullaert@vu.nl] (c), Reginald Dewil [reginald.dewil@kuleuven.be] (a,d)

Keywords Logistics; Order batching; Routing; Mixed-shelves storage; AGV-assisted picking Highlights * Integrated order batching and routing in multi-depot AGV-assisted warehouses. * Modeling with two network flow formulations. * Applying mixed-shelves storage policy. * Solving the integrated problem with a novel variable neighborhood search. * Allowing a saving on driving distances of AGVs of up to 62%. Abstract Different retail and e-commerce companies are facing the challenge of assembling large numbers of time-critical picking orders that include both small-line and multi-line orders. To reduce unproductive picker working time as in traditional picker-to-parts warehousing systems, different solutions are proposed in the literature and in practice. For example, in a mixed-shelves storage policy, items of the same stock keeping unit are spread over several shelves in a warehouse; or automated guided vehicles (AGVs) are used to transport the picked items from the storage area to packing stations instead of human pickers. This is the first paper to combine both solutions, creating what we call AGV-assisted mixed-shelves picking systems. We model the new integrated order batching and routing problem in such systems as an extended multi-depot vehicle routing problem with both three-index and two-commodity network flow formulations. Due to the complexity of the integrated problem, we develop a novel variable neighborhood search algorithm to solve the integrated problem more efficiently. We test our methods with different sizes of instances, and conclude that the mixed-shelves storage policy is more suitable than the usual storage policy in AGV-assisted mixed-shelves systems for orders with different sizes of order lines (saving up to 62% on driving distances for AGVs). Our variable neighborhood search algorithm provides optimal solutions within an acceptable computational time. Author Affiliation: (a) Leuphana University of Lüneburg, Universitätallee 1, 21335 Lüneburg, Germany (b) Beijing Hanning Tech Co., Ltd, China * Corresponding author. Article History: Received 27 January 2021; Accepted 31 August 2022 Byline: Lin Xie [xie@leuphana.de] (*,a), Hanyi Li (b), Laurin Luttmann (a)

Keywords Group decision and negotiation; Fair division; Divisible goods; Private law Highlights * Algorithm for the fair division with monetary value among agents with preferences. * Agents' preferences elicited via a star rating system. * Allocations with different monetary value that give equal satisfaction. * Robust to small misspecifications of the parameters. * Easy to compute for the two agent's case. Abstract Inheritances, divorces or liquidations of companies require common assets to be divided among the entitled parties. Legal methods usually consider the market value of goods, while fair division theory takes into account the parties' preferences expressed as utilities. I combine the two practices to define a procedure that optimally allocates divisible goods with market values to people with easily elicited preferences. Imposing an exact equality onn the bundles' monetary values may produce unacceptable solutions. I drop the tight requirement and suggest a procedure in which the differences in the monetary values are explained in terms of satisfaction per monetary share as perceived by the agents. A robustness study shows the consequences of misspecification in the model parameters. Author Affiliation: Luiss University, Italy Article History: Received 28 July 2020; Accepted 13 October 2022 (footnote)1 I wish to thank three anonymous referees, whose comments greatly improved the paper. I would also like to thank all the Invited Speakers to the 'De Aequa Divisione' workshop which took place in Rome, May 23--25, 2019: Anna Bogomolnaia, Markus Brill, Daniela Di Cagno, Edith Elkind, Vasilis Gkatzelis, Jérôme Lang, Juan D. Moreno Ternero, Hervé Moulin, Antonio Nicoló, Fedor Sandomirskiy and William Thomson. They all provided feedback during the presentation of this work at an early stage. Additional thanks go to Hervè Moulin for fruitful discussions that took place during the early stage of this work. Finally, I would like to thank Elizabeth Mary Bevan and Cecilia Flori for correcting my language mistakes in the many revisions. All the mistakes as yet undiscovered are mine. Byline: Marco Dall'Aglio [mdallaglio@luiss.it] (1)

Keywords Scheduling; Moldable tasks; Approximation algorithm Highlights * Optimizing the degree of task parallelism for minimum makespan is studied. * An efficient algorithm with an approximation guarantee likely matching lower bound. * A novel technique for improving approximation guarantee of certain dual algorithms. Abstract We are concerned with the problem of scheduling monotonic moldable tasks on identical processors to minimize the makespan. We focus on the natural case where the number m of processors as resources is fixed or relatively small compared with the number n of tasks. We present an efficient (3/2)-approximation algorithm with time complexity O(nmlog(nm)) (for m>n) and O(n.sup.2logn) (for m[less than or equal to]n). To the best of our knowledge, the best relevant known results are: (a) a (3/2+)-approximation algorithm with time complexity O(nmlog(n/)), (b) a fully polynomial-time approximation scheme for the case of m[greater than or equal to]16n/, and (c) a polynomial-time approximation scheme with time complexity O(n.sup.g(1/)) when m is bounded by a polynomial in n, where g(*) is a super-exponential function. On the other hand, the novel general technique developed in this paper for removing the -term in the worst-case performance ratio can be applied to improving the performance guarantee of certain dual algorithms for other combinatorial optimization problems. Author Affiliation: (a) School of Management, Fudan University, Shanghai 200433, China (b) Warwick Business School, University of Warwick, Coventry CV4 7AL, UK * Corresponding author. Article History: Received 6 August 2021; Accepted 24 August 2022 Byline: Fangfang Wu [ffwu17@fudan.edu.cn] (a), Xiandong Zhang [xiandongzhang@fudan.edu.cn] (a), Bo Chen [b.chen@warwick.ac.uk] (*,b)

Keywords Evolutionary computations; Search and rescue; Optimal search path planning; Ant colony optimization; Humanitarian operations Highlights * We proposed and evaluated algorithms for optimal search path planning with visibility. * Ant colony algorithms efficiently optimize search plans (path and effort allocations). * Problem-based pheromone initialization and update benefit search plan optimization. * Luby and Geometric restart policy help convergence and diversification. * Extensive experiments show that efficient metaheuristic can lead to operational plans. Abstract In search and rescue operations, an efficient search path, colloquially understood as a path maximizing the probability of finding survivors, is more than a path planning problem. Maximizing the objective adequately, i.e., quickly enough and with sufficient realism, can have substantial positive impact in terms of human lives saved. In this paper, we address the problem of efficiently optimizing search paths in the context of the NP-hard optimal search path problem with visibility, based on search theory. To that end, we evaluate and develop ant colony optimization algorithm variants where the goal is to maximize the probability of finding a moving search object with Markovian motion, given a finite time horizon and finite resources (scans) to allocate to visible regions. Our empirical results, based on evaluating 96 variants of the metaheuristic with standard components tailored to the problem and using realistic size search environments, provide valuable insights regarding the best algorithm configurations. Furthermore, our best variants compare favorably, especially on the larger and more realistic instances, with a standard greedy heuristic and a state-of-the-art mixed-integer linear program solver. With this research, we add to the empirical body of evidence on an ant colony optimization algorithms configuration and applications, and pave the way to the implementation of search path optimization in operational decision support systems for search and rescue. Author Affiliation: (a) Department of Operations and Decision Systems, Université Laval, Québec, Canada (b) Department of Computer Science and Software Engineering, Université Laval, Québec, Canada * Corresponding author. Article History: Received 2 August 2021; Accepted 8 June 2022 Byline: Michael Morin [Michael.Morin@osd.ulaval.ca] (*,a), Irène Abi-Zeid (a), Claude-Guy Quimper (b)

Keywords Inventory; Repair kit; Spare parts; Advance demand information; Multiple jobs Highlights * We consider information on failure codes for the management of repair kits. * We present two heuristics for the repair kit problem with advance demand information. * Heuristic solutions are within 10% of optimal solution for small problem instances. * Using failure information for spare parts management yields cost reductions. * One heuristic can easily be adjusted for capacity-constrained repair kit problems. Abstract To promote customer loyalty and generate revenue in after-sales service, many companies provide field repair services to their customers. Service technicians who perform these repair jobs typically carry a set of spare parts called a repair kit in their company van. The repair kit problem aims to determine which parts to include in this kit and in what quantity. Currently, many appliances are equipped with sensors that monitor their different functionalities. If an appliance breaks down because one of these functionalities is disturbed, then the respective sensor triggers a failure code that describes the appliance's condition. From the service technician's perspective, this failure code serves as potentially imperfect advance demand information for spare parts. In this paper, we present an extension of the repair kit problem that uses this information for the replenishment decision. We formulate this repair kit problem with advance demand information as a Markov decision process and propose two heuristic solution procedures. Our first heuristic is far-sighted and optimizes the inventory of all parts individually, while our second heuristic is a myopic greedy algorithm that considers all parts at once. We conduct an extensive numerical study to evaluate the performance of both heuristics and to identify which heuristic performs best under which circumstances. Comparing both heuristics to a state-of-the-art algorithm that disregards any available advance demand information, we find that utilizing this information yields substantial cost savings. Author Affiliation: (a) Otto-von-Guericke-University Magdeburg, Faculty of Economics and Management, Chair of Operations Management, P.O. Box 4120, D-39108 Magdeburg, Germany (b) Technical University of Munich, TUM School of Management, TUM Campus Heilbronn, Bildungscampus 9, 74076 Heilbronn, Germany * Corresponding author. Article History: Received 22 December 2020; Accepted 14 April 2022 Byline: Christoph Rippe [christoph.rippe@ovgu.de] (*,a), Gudrun P. Kiesmüller [gudrun.kiesmueller@tum.de] (b)

Keywords Traveling salesman problem; Arbitrary neighbourhoods; Boundary-based encoding scheme; Hybrid algorithm; Close-enough Highlights * A collaboration-based double-loop hybrid algorithm is proposed. * Neighbourhoods are generalized to arbitrarily connected regions in Euclidean space. * A novel boundary-based encoding scheme for obtaining the solution is presented. * The proposed algorithm can obtain a high-quality path in a reasonable time. * This work makes the traveling salesman problem more practical in real applications. Abstract This paper addresses the traveling salesman problem with arbitrary neighbourhoods, which is an NP-hard problem in combinatorial optimization and is important in operations research and theoretical computer science. Existing methods based on neighbourhood predigestion and discretization are impractical in cases in which the neighbourhoods are arbitrary. In this paper, the neighbourhoods of the traveling salesman problem are generalized to arbitrarily connected regions in planar Euclidean space. A novel approach to solving this problem is proposed, including a boundary-based encoding scheme and a double-loop hybrid algorithm based on particle swarm optimization and genetic algorithm. In the hybrid algorithm, linear descending inertia weight particle swarm optimization is adopted to search continuous visiting positions in the outer loop, and the genetic algorithm is used to optimize the discrete visiting sequence in the inner loop. The boundary-based encoding scheme can reduce the search space significantly without degrading the solution quality, and the hybrid algorithm can find a high-quality solution in a reasonable time. The computational results on both small and large instances demonstrate that the proposed approach can guarantee a high-quality solution in a reasonable time, compared with three other state-of-the-art algorithms: iterative algorithm, branch-and-bound algorithm, and upper and lower bound algorithm. Moreover, the proposed approach works efficiently in a real-world application that cannot be solved by existing algorithms. Author Affiliation: Aeronautics and Astronautics Engineering College, Air Force Engineering University, Baling Road No. 1, Baqiao, Xi'an 710038, Shannxi, PR China * Corresponding author. Article History: Received 6 December 2016; Revised 5 July 2017; Accepted 5 July 2017 Byline: Zhao Yang [yz1695@126.com], Ming-Qing Xiao, Ya-Wei Ge, De-Long Feng, Lei Zhang, Hai-Fang Song, Xi-Lang Tang

Keywords Dynamic programming; Bounding; Multi-profit orienteering problem; Exact approach Highlights * The first exact method for the multi-profit-orienteering problem is proposed. * A hybrid dynamic programming with bounding algorithm is proposed. * The proposed algorithm can close 33 previously unsolved benchmark instances. * The proposed algorithm obtained new best-known solutions of 23 benchmark instances. Abstract The multi-profit orienteering problem (MPOP), a variant of the orienteering problem, was introduced in 2020. In MPOP, each vertex has multiple profits, and a profit is determined by the time of visit. Therefore, the vertices to visit as well as the visit sequence and visit times must be optimally selected. The purpose of MPOP is to maximize the total profits collected from the vertices while satisfying the travel time limit constraint. To date, no exact algorithm has been developed for MPOP. This paper proposes a dynamic programming (DP)-based exact algorithm for MPOP for the first time. The proposed algorithm combines DP, ng-route relaxed DP, incumbent solution generation algorithms, and bounding rules. The proposed algorithm can obtain the optimal solutions for 33 previously unsolved benchmark instances and update the best solutions in 23 benchmark instances for MPOP. Author Affiliation: Department of Industrial and Management Engineering, Pohang University of Science and Technology (POSTECH), Pohang, Gyeongbuk 37673, Republic of Korea * Corresponding author. Article History: Received 6 December 2020; Accepted 23 February 2022 Byline: Hyunjoon Kim [dnwjd2355@postech.ac.kr], Byung-In Kim [bkim@postech.ac.kr] (*)

Keywords Scheduling; Dantzig-Wolfe decomposition; Branch and price; Nanosatellite; Quality of service Highlights * We present a B&P decomposition for task scheduling of satellites. * The decomposition allows to deal with larger instances than the original formulation. * The proposed decomposition showed to be better than Gurobi in most tested instances. Abstract Satellite scheduling is concerned with the assignment of start and finish times for tasks while considering the mission objective, available resources, and constraints. This scheduling problem is especially critical in nanosatellites, given that resources are more scarce than in traditionally-sized spacecrafts. Despite having its own set of constraints and being increasingly deployed, nanosatellite task scheduling has received little attention in the literature. In this paper, we advance the state-of-the-art by devising an effective solution approach for a nanosatellite task scheduling problem. We resort to the Dantzig-Wolfe decomposition to explore the special structure of an existing mixed-integer linear programming (MILP) formulation, decomposing it by tasks, which results in a novel profile-based formulation for the problem. To solve the resulting formulation, we propose a branch-and-price (B&P) algorithm that is suitable for the scheduling of a large number of tasks over an expanded time horizon. Furthermore, we design a dynamic programming algorithm for generating feasible schedules instead of solving the pricing subproblem with an MILP solver, among other algorithmic strategies. Computational experiments using instances that represent realistic scenarios showed that the B&P algorithm is considerably more efficient in solving large instances when compared to commercial solvers. Overall, the proposed solution strategy empowers the decision maker to plan more complex missions, in an optimal or nearly-optimal manner and within a reasonable computation time. Author Affiliation: (a) Department of Electrical Engineering, Federal University of Santa Catarina (UFSC), Florianópolis, Brazil (b) Graduate Program in Applied Computer Science, University of Vale do Itajaí (UNIVALI), Itajaí, Brazil (c) Department of Automation and Systems Engineering, Federal University of Santa Catarina (UFSC), Florianópolis, Brazil (d) Department of Aerospace, Federal University of Maranhão (UFMA), São Luis, Brazil (e) Department of Production Engineering, Federal University of São Carlos (UFSCar), São Carlos, Brazil * Corresponding author at: Graduate Program in Applied Computer Science, University of Vale do Itajaí (UNIVALI), Itajaí, Brazil. Article History: Received 15 July 2021; Accepted 18 February 2022 Byline: Cezar Antônio Rigo [cezar.rigo@posgrad.ufsc.br] (a), Laio Oriel Seman [laio@univali.br] (*,b,c), Eduardo Camponogara [eduardo.camponogara@ufsc.br] (c), Edemar Morsch Filho [edemar.filho@ufma.br] (d), Eduardo Augusto Bezerra [eduardo.bezerra@ufsc.br] (a), Pedro Munari [munari@dep.ufscar.br] (e)

Keywords Nonlinear programming; Mixed integer linear programming; Distributed systems; Failure detection; Heartbeats Highlights * A nonlinear optimisation model for high-performing probabilistic failure detectors. * Transformed nonlinear optimisation model to Mixed-Integer Linear Problem. * New self-optimised failure detector using network data and the model optimal solutions. * Design of a heuristic algorithm to efficiently tackle the scalability challenge. * Testbeds development on both the Amazon Cloud and a Cloud simulator for robust results. Abstract Failure detectors (FDs) are fundamental building blocks for distributed systems. An FD detects whether a process has crashed or not based on the reception of heartbeats' messages sent by this process over a communication channel. A key challenge of FDs is to tune their parameters to achieve optimal performance which satisfies the desired system requirements. This is challenging due to the complexities of large-scale networks. Existing FDs ignore such optimisation and adopt ad-hoc parameters. In this paper, we propose a new Mixed Integer Linear Programming (MILP) optimisation-based FD algorithm. We obtain the MILP formulation via piecewise linearisation relaxations. The MILP involves obtaining optimal FD parameters that meet the optimal trade-off between its performance metrics requirements, network conditions and system parameters. The MILP maximises our FD's accuracy under bounded failure detection time while considering network and system conditions as constraints. The MILP's solution represents optimised FD parameters that maximise FD's expected performance. To adapt to real-time network changes, our proposed MILP-based FD fits the probability distribution of heartbeats' inter-arrivals. To address our FD scalability challenge in large-scale systems where the MILP model needs to compute approximate optimal solutions quickly, we also propose a heuristic algorithm. To test our proposed approach, we adopt Amazon Cloud as a realistic testing environment and develop a simulator for robustness tests. Our results show consistent improvement of overall FD performance and scalability. To the best of our knowledge, this is the first attempt to combine the MILP-based optimisation modelling with FD to achieve performance guarantees. Author Affiliation: (a) Centre for Risk Research, Department of Decision Analytic and Risk, Southampton Business School, University of Southampton, Building 2, University Road, SO17 1BJ, UK (b) The Artificial Intelligence Applications Institute, School of Informatics, Informatics Forum, The University of Edinburgh, Crichton Street, EH8 9AB, UK (c) Edinburgh Research Centre, Huawei Technologies R&D, 2, Semple Street, EH3 8BL, UK * Corresponding author at: Centre for Risk Research, Department of Decision Analytic and Risk, Southampton Business School, University of Southampton, Building 2, University Road, SO17 1BJ; School of Informatics The University of Edinburgh Informatics Forum Edinburgh EH8 9AB. Article History: Received 18 February 2020; Accepted 2 February 2022 (footnote)[white star] This piece of research was partially sponsored by Huawei Ltd. (footnote)1 This work has been achieved while B. Er-Rahmadi was a Research Fellow at the University of Southampton, UK; currently she is affiliated to Edinburgh Research Centre, Huawei Technologies R&D, 2, Semple Street, EH3 8BL, UK. Byline: Btissam Er-Rahmadi [btissam.errahmadi@gmail.com] (1,a,c), Tiejun Ma [tiejun.ma@soton.ac.uk] (*,a,b)

Keywords Routing; Inventory routing; Branch-and-cut; Dantzig-Wolfe reformulation; Valid inequalities Highlights * An improved formulation for the inventory routing problem is presented. * This formulation can efficiently handle time-varying demands. * An arc-flow adaptation of the capacity inequalities is introduced. * A branch-and-cut algorithm based on these components is proposed. * This algorithm yields smaller optimality gaps when demands vary with time. Abstract The Inventory Routing Problem (IRP) is a broad class of complex routing problems where the quantities of delivered products must also be determined. In this paper, we consider the classic IRP where a single supplier must determine when to visit its customers, how much to deliver and how to combine the customer visits in each period into routes. We propose a branch-and-cut algorithm based on a new mathematical formulation for the IRP, improving the average lower bound obtained from algorithms based on the branch-and-cut methodology. The new formulation substitutes parts of the original formulation with a convex combination of extreme points. We call these extreme points customer schedules and for each customer they contain information about delivery periods and corresponding delivered quantities. We show that this algorithm outperforms a state-of-the-art branch-and-cut algorithm on instances with time-varying demands. The customer schedule-based algorithm obtains better lower bounds, which improves the average optimality gap by 29% and 15% on two new sets of instances with time-varying demands. Author Affiliation: (a) Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, Alfred Getz veg 3, 7491 Trondheim, Norway (b) Department of Mathematics and Industrial Engineering & GERAD, Polytechnique Montreal, Montreal, Canada * Corresponding author. Article History: Received 4 May 2021; Accepted 3 February 2022 Byline: Jørgen Skålnes [jorgen.skalnes@ntnu.no] (*,a), Henrik Andersson (a), Guy Desaulniers (b), Magnus Stålhane (a)

Keywords Scheduling; Distributionally robust optimization; Uncertain processing time; Total flow time; Computational complexity Highlights * Distributionally robust solution to total flow time minimization on parallel machines. * Reformulation of the problem in terms of norm regularization. * Complexity characterization with respect to the type of the used norm. * The results show that it is possible to achieve similar stability/quality trade-offs with much-reduced computation cost when the l1 norm is used. Abstract In this paper, we study a distributionally robust parallel machines scheduling problem, minimizing the total flow time criterion. The distribution of uncertain processing times is subject to ambiguity belonging to a set of distributions with constrained mean and covariance. We show that the problem can be cast as a deterministic optimization problem, with the objective function composed of an expectation and a regularization term given as an l.sub.p norm. The main question we ask and answer is whether the particular choice of the used l.sub.p norm affects the computational complexity of the problem and the robustness of its solution. We prove that if durations of the jobs are independent, the solution in terms of any l.sub.p norm can be solved in a pseudopolynomial time, by the reduction to a non-linear bipartite matching problem. We also show an efficient, polynomial-time algorithm for l.sub.1 case. Furthermore, for instances with dependent durations of the jobs, we propose computationally efficient formulation and an algorithm that uses l.sub.1 norm. Moreover, we identify a class of covariance matrices admitting a faster, polynomial-time algorithm. The computational experiments show that the proposed algorithms provide solutions with a similar quality to the existing algorithms while having significantly better computational complexities. Author Affiliation: (a) Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Czechia (b) Department of Control Systems and Mechatronics, Faculty of Computer Science and Management, Wroclaw University of Science and Technology, Poland (c) Faculty of Electrical Engineering, Czech Technical University in Prague, Czechia * Corresponding author at: Faculty of Electrical Engineering, Czech Technical University in Prague, Czechia. Article History: Received 3 December 2020; Accepted 3 January 2022 Byline: Antonin Novak [antonin.novak@cvut.cz] (*,a,c), Andrzej Gnatowski (b), Premysl Sucha (a)

Keywords Production; Lot-sizing and scheduling problem; Integer optimization model; Sequence-dependent setup; Approximate dynamic programming algorithm Highlights * Lot-sizing and scheduling with sequence-dependent setup cost and times is studied. * The time-flow model for the problem is proposed and compared with a standard model. * The time-flow model shows better theoretical and computational performance. * An ADP algorithm based on the time-flow model is also proposed. * The proposed algorithm shows computational benefits over the standard MIP solver. Abstract In this paper, we propose new integer optimization models for the lot-sizing and scheduling problem with sequence-dependent setups, based on the general lot-sizing and scheduling problem. To incorporate setup crossover and carryover, we first propose a standard model that straightforwardly adapts a formulation technique from the literature. Then, as the main contribution, we propose a novel optimization model that incorporates the notion of time flow. We derive a family of valid inequalities with which to compare the tightness of the models' linear programming relaxations. In addition, we provide an approximate dynamic programming algorithm that estimates the value of a state using its lower and upper bounds. Then, we conduct computational experiments to demonstrate the competitiveness of the proposed models and the solution algorithm. The test results show that the newly proposed time-flow model has considerable advantages compared with the standard model in terms of tightness and solvability. The proposed algorithm also shows computational benefits over the standard mixed integer programming solver. Author Affiliation: Department of Industrial Engineering, Seoul National University, 1 Gwanak-ro, Gwanak-gu, Seoul 08826, Republic of Korea * Corresponding author. Article History: Received 16 March 2021; Accepted 22 December 2021 Byline: Younsoo Lee [fifays@snu.ac.kr], Kyungsik Lee [optima@snu.ac.kr] (*)

Keywords Scheduling; Approximate dynamic programming; Energy-efficient production planning; Makespan; Time-of-use tariff Highlights * An online energy-efficient unrelated parallel machine scheduling problem is considered. * An approximate dynamic programming approach is proposed. * A new binary program for solving the optimization problem at each state is proposed. Abstract In this paper, we propose an approximate dynamic programming approach for an energy-efficient unrelated parallel machine scheduling problem. In this scheduling problem, jobs arrive at the system randomly, and each job's ready and processing times become available when an order is placed. Therefore, we consider the online version of the problem. Our objective is to minimize a combination of makespan and the total energy costs. The energy costs include cost of energy consumption of machines for switching on, processing, and idleness. We propose a binary program to solve the optimization problem at each stage of the approximate dynamic program. We compare the results of the approximate programming approach against an integer linear programming formulation of the offline version of the scheduling problem and an existing heuristic method suitable for scheduling problem with ready times. The results show that the approximate dynamic programming algorithm outperforms the two off-line methods in terms of solution quality and computational time. Author Affiliation: (a) School of Electrical Engineering, Computing, and Mathematical Sciences, Curtin University, Bentley, WA 6102, Australia (b) ARC Training Center for Transforming Maintenance through Data Science, Curtin University, Bentley, WA 6102, Australia * Corresponding author at: School of Electrical Engineering, Computing, and Mathematical Sciences, Curtin University, Bentley, WA 6102, Australia. Article History: Received 25 November 2020; Accepted 27 December 2021 Byline: Mojtaba Heydar [mojtaba.heydar@curtin.edu.au] (*,a,b), Elham Mardaneh [elham.mardaneh@curtin.edu.au] (a), Ryan Loxton [r.loxton@curtin.edu.au] (a)

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2010.05.016 Byline: E. Khorram, M. Zarepisheh, B.A. Ghaznavi-ghosoni Keywords: Multiple objective programming; Vector optimization; Preemptive priority; Lexicographic ordering; Sensitivity analysis Abstract: This paper deals with a class of multiple objective linear programs (MOLP) called lexicographic multiple objective linear programs (LMOLP). In this paper, by providing an efficient algorithm which employs the preceding computations as well, it is shown how we can solve the LMOLP problem if the priority of the objective functions is changed. In fact, the proposed algorithm is a kind of sensitivity analysis on the priority of the objective functions in the LMOLP problems. Author Affiliation: Faculty of Mathematics and Computer Science, Amirkabir University of Technology, 424, Hafez Avenue, 15914 Tehran, Iran Article History: Received 9 May 2008; Accepted 13 May 2010

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.11.034 Byline: Hamed Samarghandi, Kourosh Eshghi Keywords: Facilities planning and design; Linear ordering problem; Tabu search; Integer programming Abstract: The general goal of the facility layout problem is to arrange a given number of facilities to minimize the total cost associated with the known or projected interactions between them. One of the special classes of the facility layout problem is the Single Row Facility Layout Problem (SRFLP), which consists of finding an optimal linear placement of rectangular facilities with varying dimensions on a straight line. This paper first presents and proves a theorem to find the optimal solution of a special case of SRFLP. The results obtained by this theorem prove to be very useful in reducing the computational efforts when a new algorithm based on tabu search for the SRFLP is proposed in this paper. Computational results of the proposed algorithm on benchmark problems show the greater efficiency of the algorithm compared to the other heuristics for solving the SRFLP. Author Affiliation: Sharif University of Technology, Tehran, Iran Article History: Received 25 September 2008; Accepted 29 November 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.11.029 Byline: Jens Lysgaard Keywords: Routing; Pyramidal traveling salesman; Branch-and-cut-and-price Abstract: This paper introduces the pyramidal capacitated vehicle routing problem (PCVRP) as a restricted version of the capacitated vehicle routing problem (CVRP). In the PCVRP each route is required to be pyramidal in a sense generalized from the pyramidal traveling salesman problem (PTSP). A pyramidal route is defined as a route on which the vehicle first visits customers in increasing order of customer index, and on the remaining part of the route visits customers in decreasing order of customer index. Moreover, this paper develops an exact branch-and-cut-and-price (BCP) algorithm for the PCVRP. A main feature of the algorithm is that exact pricing over elementary routes are done in pseudo-polynomial time. Computational results suggest that PCVRP solutions are highly useful for obtaining near-optimal solutions to the CVRP. Furthermore, pricing of pyramidal routes may prove to be very useful in column generation for the CVRP. Author Affiliation: CORAL, Department of Business Studies, Aarhus School of Business, University of Aarhus, Fuglesangs Alle 4, DK-8210 Aarhus V, Denmark Article History: Received 29 April 2008; Accepted 21 November 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.06.033 Byline: Nguyen Huynh Tuong, Ameur Soukhal, Jean-Charles Billaut Keywords: Scheduling; Single machine; Parallel machines; Dynamic programming Abstract: This paper deals with a scheduling problem of independent tasks with common due date where the objective is to minimize the total weighted tardiness. The problem is known to be ordinary NP-hard in the case of a single machine and a dynamic programming algorithm was presented in the seminal work of Lawler and Moore [E.L. Lawler, J.M. Moore, A functional equation and its application to resource allocation and sequencing problems, Management Science 16 (1969) 77-84]. In this paper, this algorithm is described and discussed. Then, a new dynamic programming algorithm is proposed for solving the single machine case. These methods are extended for solving the identical and uniform parallel-machine scheduling problems. Author Affiliation: Laboratoire d'Informatique, Universite Francois Rabelais, Tours 64 Avenue Jean Portalis - 37200 Tours, France Article History: Received 29 July 2008; Accepted 22 June 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.03.048 Byline: Marie E. Matta (a), Salah E. Elmaghraby (b) Keywords: Scheduling; Sequencing; Deterministic; Proportionate multiprocessor open shop; Polynomial time algorithms Abstract: This paper describes a complex scheduling problem taken from a hospital diagnostic testing center that schedules hundreds of patients in an open shop environment consisting of multiple facilities and multiple processors. This scheduling problem, known as the multiprocessor open shop (MPOS) problem, is strongly NP-hard with few published results. Realizing that in many MPOS environments processing times are stage-dependent, not both job and stage-dependent, this paper examines a new class of problems for the MPOS -- proportionate ones. This paper exploits the structural nature of the proportionate MPOS and defines new terms. Despite the enormous complexity of the MPOS problem, this work demonstrates that polynomial time algorithms exist for two special cases. Since other applications of this problem exist in service and manufacturing environments, solving the proportionate MPOS problem is not only significant in the theory of optimization, but also in many real-world applications. Author Affiliation: (a) The George Washington University, School of Business, Department of Decision Sciences, Washington, DC 20052, USA (b) North Carolina State University, Department of Industrial Engineering and Operations Research, Raleigh, NC 27695, USA Article History: Received 30 January 2008; Accepted 26 March 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.03.020 Byline: V. Charles (a), A. Udhayakumar (b), V. Rhymend Uthariaraj (c) Keywords: Stochastic programming; Fractional programming; Multi-objective programming; Redundancy Abstract: Structural redundancies in mathematical programming models are nothing uncommon and nonlinear programming problems are no exception. Over the past few decades numerous papers have been written on redundancy. Redundancy in constraints and variables are usually studied in a class of mathematical programming problems. However, main emphasis has so far been given only to linear programming problems. In this paper, an algorithm that identifies redundant objective function(s) and redundant constraint(s) simultaneously in multi-objective nonlinear stochastic fractional programming problems is provided. A solution procedure is also illustrated with numerical examples. The proposed algorithm reduces the number of nonlinear fractional objective functions and constraints in cases where redundancy exists. Author Affiliation: (a) CENTRUM Catolica, Pontificia Universidad Catolica del Peru, Santiago de Surco, Peru (b) Department of Computer Applications, Hindustan College of Engineering, Chennai 603 103, India (c) Ramanujan Computing Center, Anna University, Chennai 600 025, India Article History: Received 2 May 2007; Accepted 19 March 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.03.011 Byline: Michael Short Keywords: Non-preemptive scheduling; Greedy heuristics; Periodic queries; Complexity Abstract: A recently published paper by Zeng et al. [Zeng, D.D., Dror, M., Chen, H., 2006. Efficient scheduling of periodic information monitoring requests. European Journal of Operational Research 173, 583-599] considers the non-preemptive scheduling of periodic server information requests for mission-critical monitoring applications such as policing and homeland security. In their paper, it was claimed that the decision version of the considered Periodic Monitoring (PM) problem was NP-Complete, and several greedy heuristics were developed to 'efficiently' solve the problem. The standard argument of polynomial-time solution verification was employed in their complexity proof. However, the present note points out that the PM problem is actually [SIGMA].sub.2.sup.p-Complete, and verification of a PM solution is coNP-Complete, in the strong sense. A consequence of these results is that the greedy heuristics proposed by Zeng et al. are all strongly coNP-Hard, invalidating the authors' claims of efficiency; since their algorithms are implemented on-line in a mission-critical application, this clearly needs to be taken into account. The final contributions of the present note are the description of an efficient algorithm for the underlying peak server load problem, and showing that equivalence classes in request start times can be efficiently detected and pruned prior to searching. These former elements - if incorporated into the original heuristics - can potentially improve stability and efficiency by large orders of magnitude. Author Affiliation: Embedded Systems Laboratory, University of Leicester, University Road, Leicester LE1 7RH, UK Article History: Received 3 September 2008; Accepted 9 March 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.01.014 Byline: Albert Corominas (a), Wieslaw Kubiak (b), Rafael Pastor (a) Keywords: Scheduling; Response time variability; Fair sequences; Optimization Abstract: The Response Time Variability Problem (RTVP) is a scheduling problem that has recently been defined in the literature. The RTVP has a broad range of real-life applications from manufacturing to services and information technology. A previous study developed a position exchange heuristic to apply to initial sequences for the RTVP, and a MILP (Mixed Integer Linear Programming) to obtain optimal solutions with a practical limit of 25 units to be scheduled. This paper aims to improve the best mathematical programming model developed thus far in order to solve larger instances up to 40 units to optimality. The contribution of this paper is 4-fold: (i) larger instances can be solved to optimality by the off the shelf standard software; (ii) the new optimal solutions of the RTVP can be used to compare the results of heuristic procedures; (iii) the importance of modeling is demonstrated, as well as the huge impact that reformulation, redundant constraints and the elimination of symmetries have on the efficiency of MILPs is clearly established; finally (iv) a challenge to develop a customized optimization algorithm to rival the MILP solution efficiency for the RTVP is put forward. Author Affiliation: (a) Institute of Industrial and Control Engineering (IOC), Catalonia University of Technology, Av. Diagonal 647 (Edificio ETSEIB), Planta 11, 08028 Barcelona, Spain (b) Faculty of Business Administration, Memorial University, St. John's, Canada Article History: Received 23 September 2007; Accepted 12 January 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.10.027 Byline: M.C. Goldbarg, L.B. Bagi, E.F.G. Goldbarg Keywords: Combinatorial optimization; Traveling Purchaser Problem; Evolutionary algorithm; Transgenetic algorithm Abstract: In this paper an evolutionary algorithm is presented for the Traveling Purchaser Problem, an important variation of the Traveling Salesman Problem. The evolutionary approach proposed in this paper is called transgenetic algorithm. It is inspired on two significant evolutionary driving forces: horizontal gene transfer and endosymbiosis. The performance of the algorithm proposed for the investigated problem is compared with other recent works presented in the literature. Computational experiments show that the proposed approach is very effective for the investigated problem with 17 and 9 new best solutions reported for capacitated and uncapacitated instances, respectively. Author Affiliation: Universidade Federal do Rio Grande do Norte, Campus Lagoa Nova, RN, Brazil Article History: Received 25 October 2006; Accepted 27 October 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.08.026 Byline: A. Akbalik, Y. Pochet Keywords: Integer programming; Single-item capacitated lot sizing problem; Flow cover inequalities; Cutting plane algorithm Abstract: This paper presents a new class of valid inequalities for the single-item capacitated lot sizing problem with step-wise production costs (LS-SW). Constant sized batch production is carried out with a limited production capacity in order to satisfy the customer demand over a finite horizon. A new class of valid inequalities we call mixed flow cover, is derived from the existing integer flow cover inequalities by a lifting procedure. The lifting coefficients are sequence independent when the batch sizes (V) and the production capacities (P) are constant and when V divides P. When the restriction of the divisibility is removed, the lifting coefficients are shown to be sequence independent. We identify some cases where the mixed flow cover inequalities are facet defining. We propose a cutting plane algorithm for different classes of valid inequalities introduced in the paper. The exact separation algorithm proposed for the constant capacitated case runs in polynomial time. Computational results show the efficiency of the new class mixed flow cover compared to the existing methods. Author Affiliation: CORE, Universite Catholique de Louvain, 34 Voie du Roman Pays, 1348 Louvain-la-Neuve, Belgium Article History: Received 7 November 2007; Accepted 29 August 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.03.033 Byline: Sara Morin, Caroline Gagne, Marc Gravel Keywords: Ant colony optimization; Pheromone trail; Scheduling; Car-sequencing problem Abstract: This paper studies the learning process in an ant colony optimization algorithm designed to solve the problem of ordering cars on an assembly line (car-sequencing problem). This problem has been shown to be NP-hard and evokes a great deal of interest among practitioners. Learning in an ant algorithm is achieved by using an artificial pheromone trail, which is a central element of this metaheuristic. Many versions of the algorithm are found in literature, the main distinction among them being the management of the pheromone trail. Nevertheless, few of them seek to perfect learning by modifying the internal structure of the trail. In this paper, a new pheromone trail structure is proposed that is specifically adapted to the type of constraints in the car-sequencing problem. The quality of the results obtained when solving three sets of benchmark problems is superior to that of the best solutions found in literature and shows the efficiency of the specialized trail. Author Affiliation: Departement d'informatique et de mathematique, Universite du Quebec a Chicoutimi, 555, Boul. de l'Universite, Chicoutimi, Quebec, Canada G7H 2B1

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.07.018 Byline: Ching-Jong Liao (a), Chien-Wen Chao (a), Chien-Hung Lin (b) Keywords: Parallel machine scheduling; Availability constraints; Branch and bound algorithm Abstract: This paper considers a scheduling problem with two identical parallel machines. One has unlimited capacity; the other can only run for a fixed time. A given set of jobs must be scheduled on the two machines with the goal of minimizing the sum of their completion times. The paper proposes an optimal branch and bound algorithm which employs three powerful elements, including an algorithm for computing the upper bound, a lower bound algorithm, and a fathoming condition. The branch and bound algorithm was tested on problems of various sizes and parameters. The results show that the algorithm is quite efficient to solve all the test problems. In particular, the total computation time for the hardest problem is less than 0.1second for a set of 100 problem instances. An important finding of the tests is that the upper bound algorithm can actually find optimal solutions to a quite large number of problems. Author Affiliation: (a) Department of Industrial Management, National Taiwan University of Science and Technology, 43, Keelung Road, Section 4, Taipei 106, Taiwan (b) Jinwen University of Science and Technology, Taipei County 231, Taiwan Article History: Received 28 October 2006; Accepted 14 July 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.03.023 Byline: Clara Novoa (a), Robert Storer (b) Keywords: Transportation; Stochastic vehicle routing; Approximate dynamic programming Abstract: This paper examines approximate dynamic programming algorithms for the single-vehicle routing problem with stochastic demands from a dynamic or reoptimization perspective. The methods extend the rollout algorithm by implementing different base sequences (i.e. a priori solutions), look-ahead policies, and pruning schemes. The paper also considers computing the cost-to-go with Monte Carlo simulation in addition to direct approaches. The best new method found is a two-step lookahead rollout started with a stochastic base sequence. The routing cost is about 4.8% less than the one-step rollout algorithm started with a deterministic sequence. Results also show that Monte Carlo cost-to-go estimation reduces computation time 65% in large instances with little or no loss in solution quality. Moreover, the paper compares results to the perfect information case from solving exact a posteriori solutions for sampled vehicle routing problems. The confidence interval for the overall mean difference is (3.56%, 4.11%). Author Affiliation: (a) Texas State University, Ingram School of Engineering, Industrial Engineering Program, San Marcos, TX 78666, USA (b) Industrial and Systems Engineering Department, Lehigh University, Bethlehem, PA 18015, USA Article History: Received 19 September 2007; Accepted 18 March 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.04.001 Byline: Xiaoming Liu, Zhaotong Lian Keywords: Inventory; Inventory-queue; Value-added production; Distributed manufacturing system Abstract: This paper considers the cost-effective inventory control of work-in-process (WIP) and finished products in a two-stage distributed manufacturing system. The first stage produces a common WIP, and the second stage consists of several production sites that produce differentiated products with different capacity and service level requirements. The unit inventory holding cost is higher at the second stage. This paper first uses a network of inventory-queue model to evaluate the inventory cost and service level achievable for given inventory control policy, and then derives a very simple algorithm to find the optimal inventory control policy that minimizes the overall inventory holding cost and satisfies the given service level requirements. Some managerial insights are obtained through numerical examples. Author Affiliation: FBA, University of Macau, Macau SAR, China Article History: Received 11 January 2007; Accepted 1 April 2008 Article Note: (footnote) [star] Both authors are supported by University of Macau through a Grant RG052/04-05S/LZT/FBA.