Authors:M. Pirhaji; M. Zangiabadi; H. Mansouri Pages: 111 - 131 Abstract: In this paper, we propose an infeasible interior-point algorithm for linear complementarity problems. In every iteration, the algorithm constructs an ellipse and searches an \(\varepsilon \) -approximate solution of the problem along the ellipsoidal approximation of the central path. The theoretical iteration-complexity of the algorithm is derived and the algorithm is proved to be polynomial with the complexity bound \(O\left(n\log \varepsilon ^{-1}\right)\) which coincides with the best known iteration bound for infeasible interior-point methods. PubDate: 2017-06-01 DOI: 10.1007/s10288-016-0325-z Issue No:Vol. 15, No. 2 (2017)
Authors:Qiao Zhang; Jianxiong Zhang; Wansheng Tang Pages: 133 - 162 Abstract: This paper addresses the channel coordination problem in a green supply chain consisting of a manufacturer and a retailer, in which the manufacturer controls green innovation and wholes price, while the retailer controls sales price. Pricing and green innovation strategies in integrated and decentralized channels are computed and compared, and a two-part tariff contract is designed to coordinate the decentralized supply chain. A Nash bargaining model is further developed to distribute the extra-profit between channel members. A numerical example is conducted to explore the impacts of green effectiveness and operational inefficiency effect on optimal/equilibrium solutions and coordination. The main results show that the green innovation investment, energy efficiency level and channel profit of integrated channel are larger than those of decentralized one, but the relationship of sales prices under two channel structures depends on system parameters. Green effectiveness exerts a positive effect on optimal/equilibrium solutions. The coordinator’s coordination capability is improved by green effectiveness, but weakened by operational inefficiency effect. PubDate: 2017-06-01 DOI: 10.1007/s10288-016-0327-x Issue No:Vol. 15, No. 2 (2017)
Authors:Xavier Fernandes; Joana Rebelo; João Gouveia; Rodrigo Maia; Nuno Bustorff Silva Pages: 163 - 181 Abstract: In this paper, we study the problem of establishing a dynamic charging schedule of electric vehicles (EVs) at a charging station, assuming that limited power implies that only a limited number of EVs can charge simultaneously. The only control we assume to be available to the charging station is the ability to (at any given time) turn on or off the power supply to any EV, with this tool we want to develop a charging schedule that will satisfy the energy demands of the EVs in their intended deadlines. We propose two distinct approaches to this problem: a discretized time version, based on a greedy-like algorithm, and a continuous time version, based on linear programming. We compare these two approaches and numerically study the improvement they yield in the efficiency of the charging procedure, when applied to simulated data based on real parking data. Finally, we illustrate the flexibility of the models by sketching several possible extensions. PubDate: 2017-06-01 DOI: 10.1007/s10288-016-0328-9 Issue No:Vol. 15, No. 2 (2017)
Authors:Michaël Gabay; Nadia Brauner; Vladimir Kotov Pages: 183 - 199 Abstract: We use game theory techniques to automatically compute improved lower bounds on the competitive ratio for the bin stretching problem. Using these techniques, we improve the best lower bound for this problem to 19/14. We explain the technique and show that it can be generalized to compute lower bounds for any online or semi-online packing or scheduling problem. PubDate: 2017-06-01 DOI: 10.1007/s10288-016-0330-2 Issue No:Vol. 15, No. 2 (2017)
Authors:Anna Arigliano; Gianpaolo Ghiani; Antonio Grieco; Emanuela Guerriero Pages: 201 - 215 Abstract: In this paper, we deal with single machine scheduling problems subject to time dependent effects. The main point in our models is that we do not assume a constant processing rate during job processing time. Rather, processing rate changes according to a fixed schedule of activities, such as replacing a human operator by a less skilled operator. The contribution of this paper is threefold. First, we devise a time-dependent piecewise constant processing rate model and show how to compute processing time for a resumable job. Second, we prove that any time-dependent continuous piecewise linear processing time model can be generated by the proposed rate model. Finally, we propose polynomial-time algorithms for some single machine problems with job independent rate function. In these procedures the job-independent rate effect does not imply any restriction on the number of breakpoints for the corresponding continuous piecewise linear processing time model. This is a clear element of novelty with respect to the polynomial-time algorithms proposed in previous contributions for time-dependent scheduling problems. PubDate: 2017-06-01 DOI: 10.1007/s10288-016-0333-z Issue No:Vol. 15, No. 2 (2017)
Authors:Yılmaz Delice; Emel Kızılkaya Aydoğan; Uğur Özcan; Mehmet Sıtkı İlkay Pages: 37 - 66 Abstract: In this paper, a new two-sided U-type assembly line balancing (TUALB) procedure and a new algorithm based on the particle swarm optimization algorithm to solve the TUALB problem are proposed. The proposed approach minimizes the number of stations for a given cycle time as the primary objective and it minimizes the number of positions as a secondary objective. The proposed approach is illustrated with an example problem. In order to evaluate the efficiency of the proposed algorithm, the test problems available in the literature are used. The experimental results show that the proposed approach performs well. PubDate: 2017-03-01 DOI: 10.1007/s10288-016-0320-4 Issue No:Vol. 15, No. 1 (2017)
Authors:Qingda Wei Pages: 67 - 84 Abstract: In this paper we study the continuous-time Markov decision processes with a denumerable state space, a Borel action space, and unbounded transition and cost rates. The optimality criterion to be considered is the finite-horizon expected total cost criterion. Under the suitable conditions, we propose a finite approximation for the approximate computations of an optimal policy and the value function, and obtain the corresponding error estimations. Furthermore, our main results are illustrated with a controlled birth and death system. PubDate: 2017-03-01 DOI: 10.1007/s10288-016-0321-3 Issue No:Vol. 15, No. 1 (2017)
Authors:Saman Babaie-Kafaki; Reza Ghanbari Pages: 85 - 92 Abstract: Minimizing the distance between search direction matrix of the Dai–Liao method and the scaled memoryless BFGS update in the Frobenius norm, and using Powell’s nonnegative restriction of the conjugate gradient parameters, a one-parameter class of nonlinear conjugate gradient methods is proposed. Then, a brief global convergence analysis is made with and without convexity assumption on the objective function. Preliminary numerical results are reported; they demonstrate a proper choice for the parameter of the proposed class of conjugate gradient methods may lead to promising numerical performance. PubDate: 2017-03-01 DOI: 10.1007/s10288-016-0323-1 Issue No:Vol. 15, No. 1 (2017)
Authors:S. K. Padhan; C. Nahak Pages: 93 - 105 Abstract: Third order dual of a primal nonlinear programming problem is established which involves the third order derivatives of the functions constituting the primal problem. Desired duality theorems are provided for the pair of primal and the corresponding third order dual problem. Numerical examples are illustrated to justify the efficiency of the proposed method. It is also observed that some of the existing results are obtained as special cases. PubDate: 2017-03-01 DOI: 10.1007/s10288-016-0326-y Issue No:Vol. 15, No. 1 (2017)
Authors:Berit Dangaard Brouer; Christian Vad Karsten; David Pisinger Abstract: Seaborne trade is the lynchpin in almost every international supply chain, and about 90% of non-bulk cargo worldwide is transported by container. In this survey we give an overview of data-driven optimization problems in liner shipping. Research in liner shipping is motivated by a need for handling still more complex decision problems, based on big data sets and going across several organizational entities. Moreover, liner shipping optimization problems are pushing the limits of optimization methods, creating a new breeding ground for advanced modelling and solution methods. Starting from liner shipping network design, we consider the problem of container routing and speed optimization. Next, we consider empty container repositioning and stowage planning as well as disruption management. In addition, the problem of bunker purchasing is considered in depth. In each section we give a clear problem description, bring an overview of the existing literature, and go in depth with a specific model that somehow is essential for the problem. We conclude the survey by giving an introduction to the public benchmark instances LINER-LIB. Finally, we discuss future challenges and give directions for further research. PubDate: 2017-03-03 DOI: 10.1007/s10288-017-0342-6
Authors:Kris Boudt; Edgars Jakobsons; Steven Vanduffel Abstract: Several problems in operations research, such as the assembly line crew scheduling problem and the k-partitioning problem can be cast as the problem of finding the intra-column rearrangement (permutation) of a matrix such that the row sums show minimum variability. A necessary condition for optimality of the rearranged matrix is that for every block containing one or more columns it must hold that its row sums are oppositely ordered to the row sums of the remaining columns. We propose the block rearrangement algorithm with variance equalization (BRAVE) as a suitable method to achieve this situation. It uses a carefully motivated heuristic—based on an idea of variance equalization—to find optimal blocks of columns and rearranges them. When applied to the number partitioning problem, we show that BRAVE outperforms the well-known greedy algorithm and the Karmarkar–Karp differencing algorithm. PubDate: 2017-03-02 DOI: 10.1007/s10288-017-0344-4
Authors:Sandra Ulrich Ngueveu; Stéphane Caux; Frédéric Messine; Mouloud Guemri Abstract: In hybrid electric vehicles, the electrical powertrain system has multiple energy sources that it can gather power from to satisfy the propulsion power requested by the vehicle at each instant. This paper focusses on the minimization of the fuel consumption of such a vehicle, taking advantage of the different energy sources. Based on global optimization approaches, the proposed heuristics find solutions that best split the power requested between the multi-electrical sources available. A lower bounding procedure is introduced to validate the quality of the solutions. Computational results show a significant improvement over previous results from the literature in both the computing time and the quality of the solutions. PubDate: 2017-03-01 DOI: 10.1007/s10288-017-0343-5
Authors:Gaia Nicosia; Andrea Pacifici; Ulrich Pferschy Abstract: In this work we address a class of deterministic scheduling problems in which k agents compete for the usage of a single machine. The agents have their own objective functions and submit their tasks in successive steps to an external coordination subject, who sequences them by selecting the shortest task in each step. We look at the problem in two different settings and consider different combinations of cost functions. In a centralized perspective, generalizing previous results for the case with \(k=2\) agents, we characterize the set of Pareto efficient solutions as for a classical multicriteria optimization problems. On one hand we determine the number of Pareto efficient solutions and on the other hand we study the computational complexity of the associated decision problem. Then, we consider the problem from a single agent perspective. In particular, we provide a worst-case analysis on the performance of two natural heuristic algorithms, SPT and WSPT, that suggest to an agent how to sequence its own tasks when its objective is makespan, sum of completion times, or sum of weighted completion times. PubDate: 2017-02-07 DOI: 10.1007/s10288-017-0341-7
Authors:Fátima M. de Souza Lima; Davi S. D. Pereira; Samuel V. da Conceição; Ricardo S. de Camargo Abstract: Four multi-objective meta-heuristic algorithms are presented to solve a multi-objective capacitated rural school bus routing problem with a heterogeneous fleet and mixed loads. Three objectives are considered: the total weighted traveling time of the students, the balance of routes among drivers, and the routing costs. The proposed methods were compared with one from the literature, and their performance assessed observing three multi-objective metrics: cardinality, coverage, and hyper-volume. All four devised methods outperformed the one from the literature. The algorithm with a path relinking procedure embedded during the crowding distance selection scheme had the best overall performance. PubDate: 2017-01-24 DOI: 10.1007/s10288-017-0340-8
Hybrid journal (It can contain Open Access articles)
[2345 journals]
