On speed scaling via integer programming
We consider a class of convex mixed-integer nonlinear programs motivated by speed scaling of heterogeneous parallel processors with sleep states and convex power consumption curves. We show that the problem is NP-hard and identify some polynomially solvable classes. Furthermore, a dynamic programming and a greedy approximation algorithms are proposed to obtain a fully polynomial-time approximation scheme for a special case. For the general case, we implement an outer approximation algorithm.
This is the first book on the U.S. presidential election system to analyze the basic principles underlying the design of the existing system and those at the heart of competing proposals for improving the system. The book discusses how the use of some election rules embedded in the U.S. Constitution and in the Presidential Succession Act may cause skewed or weird election outcomes and election stalemates. The book argues that the act may not cover some rare though possible situations which the Twentieth Amendment authorizes Congress to address. Also, the book questions the constitutionality of the National Popular Vote Plan to introduce a direct popular presidential election de facto, without amending the Constitution, and addresses the plan’s “Achilles’ Heel.” In particular, the book shows that the plan may violate the Equal Protection Clause from the Fourteenth Amendment of the Constitution. Numerical examples are provided to show that the counterintuitive claims of the NPV originators and proponents that the plan will encourage presidential candidates to “chase” every vote in every state do not have any grounds. Finally, the book proposes a plan for improving the election system by combining at the national level the “one state, one vote” principle – embedded in the Constitution – and the “one person, one vote” principle. Under this plan no state loses its current Electoral College benefits while all the states gain more attention of presidential candidates.
This volume contains two types of papers—a selection of contributions from the “Second International Conference in Network Analysis” held in Nizhny Novgorod on May 7–9, 2012, and papers submitted to an "open call for papers" reflecting the activities of LATNA at the Higher School for Economics.
This volume contains many new results in modeling and powerful algorithmic solutions applied to problems in
- vehicle routing
- single machine scheduling
- modern financial markets
- cell formation in group technology
- brain activities of left- and right-handers
- speeding up algorithms for the maximum clique problem
- analysis and applications of different measures in clustering
The broad range of applications that can be described and analyzed by means of a network brings together researchers, practitioners, and other scientific communities from numerous fields such as Operations Research, Computer Science, Bioinformatics, Medicine, Transportation, Energy, Social Sciences, and more. The contributions not only come from different fields, but also cover a broad range of topics relevant to the theory and practice of network analysis. Researchers, students, and engineers from various disciplines will benefit from the state-of-the-art in models, algorithms, technologies, and techniques including new research directions and open questions.
In recent years, as a result of the increase in environmental problems, green logistics has become a focus of interest by researchers, governments, policy makers, and investors. In this study, a cumulative multi-trip vehicle routing problem with limited duration (CumMTVRP-LD) is modelled by taking into account the reduction of CO 2 emissions. In classical vehicle routing problems (VRP), each vehicle can perform only one trip. Because of the high investment costs of additional vehicles, organizations allow the vehicles to perform multiple trips as in multi-trip vehicle routing problems (MTVRP), which reflects the real requirements better than the classical VRP. This study contributes to the literature by using a mixed integer programming (MIP) formulation and a simulated annealing (SA) based solution methodology for CumMTVRP-LD, which considers the minimization of fuel consumption as the objective function. According to preliminary computational results using benchmark problems in the literature, the proposed methodology obtained promising results in terms of solution quality and computational time.
This paper investigates a three-stage supply chain scheduling problem in the application area of aluminium production. Particularly, the first and the third stages involve two factories, i.e., the extrusion factory of the supplier and the aging factory of the manufacturer, where serial batching machine and parallel batching machine respectively process jobs in dierent ways. In the second stage, a single vehicle transports jobs between the two factories. In our research, both setup time and capacity constraints are explicitly considered. For the problem of minimizing the makespan, we formalize it as a mixed integer programming model and prove it to be strongly NP-hard. Considering the computational complexity, we develop two heuristic algorithms applied in two different cases of this problem. Accordingly, two lower bounds are derived, based on which the worst case performance is analyzed. Finally, dierent scales of random instances are generated to test the performance of the proposed algorithms. The computational results show the effectiveness of the proposed algorithms, especially for large-scale instances.