The management of large-scale transportation infrastructure is becoming a very complex task for the urban areas of this century which are covering bigger geographic spaces and facing the inclusion of connected and self-controlled vehicles. This new system paradigm can leverage many forms of sensing and interaction, including a high-scale mobile sensing approach. To obtain a high penetration sensing system on urban areas more practical and scalable platforms are needed, combined with estimation algorithms suitable to the computational capabilities of these platforms. The purpose of this work was to develop a transportation framework that is able to handle different kinds of sensing data (e.g., connected vehicles, loop detectors) and optimize the traffic state on a defined traffic network. The framework estimates the traffic on road networks modeled by a family of Lighthill-Whitham-Richards equations. Based on an equivalent formulation of the problem using a Hamilton-Jacobi equation and using a semi-analytic formula, I will show that the model constraints resulting from the Hamilton-Jacobi equation are linear, albeit with unknown integer variables. This general framework solve exactly a variety of problems arising in transportation networks: traffic estimation, traffic control (including robust control), cybersecurity and sensor fault detection, or privacy analysis of users in probe-based traffic monitoring systems. This framework is very flexible, fast, and yields exact results. The recent advances in sensors (GPS, inertial measurement units) and microprocessors enable the development low-cost dedicated devices for traffic sensing in cities, 5 which are highly scalable, providing a feasible solution to cover large urban areas. However, one of the main problems to address is the privacy of the users of the transportation system, the framework presented here is a viable option to guarantee the privacy of the users by design.

In the past decades, linear programming (LP) has been successfully used to develop approximation algorithms for various optimization problems. In particular, the so-called assignment LP has lead to substantial progress for various allocation problems, including scheduling unrelated parallel machines. However, we have reached its limits for many problems, since the best-known approximation algorithms match the integrality gap of the assignment LP for these problems. The natural question is then whether a different LP formulation can lead to better algorithms. We answer this question positively for variants of two allocation problems: max-min fair allocation and maximum budgeted allocation. This is achieved by using a more powerful LP formulation called the configuration LP that has an exponential number of variables, but can be approximated in polynomial time. The restricted max-min fair allocation problem, also known as the restricted Santa Claus problem, is one of few problems that have a better polynomial estimation algorithm than approximation algorithm. An estimation algorithm estimates the value of the optimal solution, but is not necessarily able to find the optimal solution. The configuration LP can be used to estimate the optimal value within a factor of 1/(4+ɛ) for any ɛ&gt;0, but it is only known how to efficiently find a solution achieving this value in exponential time. We give an approximation algorithm with the same approximation ratio but improve the running time to quasi-polynomial: n^O(log n). Our techniques also have the interesting property that although we use the rather complex configuration LP in the analysis, we never actually solve it and therefore the resulting algorithm is purely combinatorial. For the maximum budgeted allocation (MBA) the integrality gap of the assignment LP is exactly 3/4. We prove that the integrality gap of the configuration LP is strictly better than 3/4 and provide corresponding polynomial time rounding algorithms for two variants of the problem: the restricted MBA and the graph MBA. Finally, we improve the best-known upper bound on the integrality gap for the general case from 0.833 to 0.828 and also show hardness of approximation results for both variants studied. / Under de senaste decennierna har linjärprogrammering (LP) framgångsrikt använts för att utveckla approximeringsalgoritmer. I synnerhet har det så kallade tilldelnings-LP lett till betydande framsteg för olika allokeringsproblem, som scheduling unrelated parallel machines. Vi verkar dock ha nått dess gräns, eftersom de bästa approximeringsalgoritmerna har samma kvalitet som heltalsgapet för dessa problem. Den naturliga frågan är då om någon annan LP-formulering kan leda till bättre algoritmer. Vi besvarar denna fråga positivt för varianter av två fördelningsproblem: max-min fair allocation och maximal budgeted allocation. Vi använder en mer kraftfull LP-formulering som kallas konfigurations-LP och har ett exponentiellt antal variabler men kan approximeras i polynomisk tid. Problemet restricted max-min fair allocation, som är även känt som restricted Santa Claus problem, är ett av få problem som har en bättre polynomisk värderingsalgoritm än approximeringsalgoritm. En värderingsalgoritm approximerar det optimala värdet, men hittar inte nödvändigtvis den optimala lösningen. Konfigurations-LP kan användas för att approximera det optimala värdet inom en faktor 1 / (4 + ɛ) för något ɛ &gt; 0, men man vet bara hur man hittar en lösning med sådan kvalitet i exponentiellt tid. Vi ger en approximeringsalgoritm med samma approximeringskvalitet men förbättrar tidskomplexitet till kvasipolynomisk: n^O(log n). Våra tekniker har också den intressanta egenskapen att även om vi använder det ganska komplext konfigurations-LP:t i analysen, löser vi aldrig det och vår algoritm är rent kombinatorisk. För maximal budgeted allocation (MBA) är heltalsgapet av tilldelnings-LP:et är precis 3/4. Vi bevisar att heltalsgapet av konfiguration-LP är strikt bättre än 3/4 och vi ger en motsvarande polynomisk avrundningsalgoritm för två varianter av problemet: restricted MBA och graph MBA. Slutligen förbättrar vi den bäst kända övre gränsen på heltalsgapet för det allmänna fallet från 0.833 till 0.828 samt ger approximeringssvårighetsresultat för båda två studerade varianter. / <p>QC 20150305</p> / ERC APPROXNP 226203

The major purpose of this study was to determine the least- cost method of producing red meat in Kenya. Linear programming was used in the study. A simulated reduction of grazing land available in one of the settlement areas was carried out to indicate what effect this had on the overall regional production pattern of meat in the country. Kenya was divided into eleven livestock producing and consuming regions. 1979 was used as the base year, and the demand projection was based on the 1979 population. Input and output coefficients, livestock unit requirements, and market prices were developed. A linear programming model was then used to generate the optimal production and marketing of both cattle and small stock .

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第21130号 / 工博第4494号 / 新制||工||1698(附属図書館) / 京都大学大学院工学研究科化学工学専攻 / (主査)教授 長谷部 伸治, 教授 大嶋 正裕, 教授 佐野 紀彰 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

No description available.

Transportation underlines the vehicle industry's critical role in a country's economic future.The amount of goods moved, specically by trucks, is only expected to increase inthe near future. This work attempts to tackle the problem of optimizing fuel consumptionin Volvo trucks, when there are hard constraints on the delivery time and speed limits.Knowledge of the truck such as position, state, conguration etc., along with the completeroute information of the transport mission is used for fuel optimization.Advancements in computation, storage, and communication on cloud based systems, hasmade it possible to easily incorporate such systems in assisting modern eet. In this work,an algorithm is developed in a cloud based system to compute a speed plan for the completemission for achieving fuel minimization. This computation is decoupled from thelocal control operations on the truck such as prediction control, safety, cruise control, etc.;and serves as a guide to the truck driver to reach the destination on time by consumingminimum fuel.To achieve fuel minimization under hard constraints on delivery (or arrival) time andspeed limits, a non-linear optimization problem is formulated for the high delity modelestimated from real-time drive cycles. This optimization problem is solved using a Nonlinearprogramming solver in Matlab.The optimal policy was tested on two drive cycles provided by Volvo. The policy wascompared with two dierent scenarios, where the mission demands hard constraints ontravel time and the speed limits in addition to no trac uncertainties (deterministic). with a cruise controller running at a constant set speed throughout the mission. Itis observed that there is no signicant fuel savings. with maximum possible fuel consumption; achieved without the help of optimalspeed plan (worst case). It is seen that there is a notable improvement in fuelsaving.In a real world scenario, a transport mission is interrupted by uncertainties such as trac ow, road blocks, re-routing, etc. To this end, a stochastic optimization algorithm is proposedto deal with the uncertainties modeled using historical trac ow data. Possiblesolution methodologies are suggested to tackle this stochastic optimization problem.

Since the beginning of project management, people have been asked to perform "more with less" in expeditious time while attempting to balance the inevitable challenge of the time/cost tradeoff. This is especially true within the Department of Defense today in prosecuting the Global War on Terrorism both in Afghanistan and Iraq. An unprecedented and consistent level of Operational Tempo has generated heavy demands on current equipment and has subsequently forced the need to recapitalize several legacy systems until suitable replacements can be implemented. This paper targets the UH-60A:A Recapitalization Program based at the Corpus Christi Army Depot in Corpus Christi, Texas. More specifically, we examine one of the nine existing project sub-networks within the UH-60A:A program, the structural/electrical upgrade phase. In crashing (i.e. adding manpower or labor hours) the network, we determine the minimal cost required to reduce the total completion time of the 68 activities within the network before a target completion time. A linear programming model is formulated and then solved for alternative scenarios. The first scenario is prescribed by the program manager and consists of simply hiring additional contractors to augment the existing personnel. The second and third scenarios consist of examining the effects of overtime, both in an aggressive situation (with limited longevity) and a more moderate situation (displaying greater sustainability over time). The initial linear programming model (Scenario 1) is crashed using estimates given from the program scheduler. The overtime models are crashed using reduced-time crash estimates. For Scenarios 2 and 3, the crashable times themselves are reduced by 50% and 75%, respectively. Initial results indicate that a completion time of 79.5 days is possible without crashing any activities in the network. The five-year historical average completion time is 156 days for this network. We continue to crash the network in each of the three scenarios and determine that the absolute shortest feasible completion times, 73 days for Scenario 1, 76 days for Scenario 2, and 77.5 days for Scenario 3. We further examine the models to observe similarities and differences in which activities get targeted for crashing and how that reduction affects the critical path of the network. These results suggests an in-depth study of using linear programming and applying it to project networks to grant project managers more critical insight that may help them better achieve their respective objectives. This work may also be useful as the groundwork for further refinement and application for maintenance managers conducting day-to-day unit level maintenance operations.

An Optimization Approach to Employee Scheduling Using Fuzzy Logic William G. Spence Selection of sales employees is critical because the sales employees represent the company’s image, competitive advantage, technology, and values. In many service systems the majority of consumer contact is with the sales department. Since there are different types of customers, scheduling quality salespersons who can adequately help consumers may affect revenue. This thesis proposes a new methodology for the scheduling of employees in a service system. The methodology uses Fuzzy Logic to calculate possible sales and Linear Programming to create an optimal schedule. This approach enables the rating of sales employees with respect to three customer’s types (Lookie Lou, Price Shopper and Buyer). The salesperson rating, along with customer arrival distribution is then used to optimize sale person scheduling, with the objective of revenue maximization. The uniqueness of this thesis lies in the combination of Fuzzy Logic and Linear Programming. The combination of these two disciplines provides an adaptive tool that can be used to optimize employee scheduling based on personality traits.

This study provides an environmental and economic analysis of the ability to reduce potential nitrogen loadings to water bodies through the implementation of nutrient management plans on livestock farms. Study results indicate that nutrient management plans do result in significant reductions while maintaining or increasing farm income. Nutrient management plans on the four case farms reduced mean nitrogen losses by 23 to 45 percent per acre while increasing net farm income from $395 to $7,249. While reducing excess nitrogen applications with the implementation of nutrient management plans achieved significant reductions in potential nitrogen losses, further reductions may be achieved through farm level planning. After achieving initial reductions through the elimination of excessive nutrient applications, variation in application rates of organic and inorganic fertilizers across soils may become important in achieving further reductions in nitrogen loss. Study results suggest that it may be beneficial to apply higher rates of manure on soils and slopes less susceptible to nitrogen losses in order to reduce applications elsewhere. Increased nutrient losses on such fields may be more than offset by reductions on soils more susceptible to nutrient losses. Linear programming results for the Shenandoah Valley Dairy show that nitrogen losses could be reduced up to 44 percent below pre-plan losses with no impact on farm net economic returns. However, if nitrogen loss restrictions were instituted beyond this level, the impact on farm income increases significantly. After-plan nitrogen losses can reduced up to 52 percent, but farm returns decrease by 56 percent. / Master of Science

<p> An emerging trend in computing is to use distributed heterogeneous computing (HC) systems to execute a set of tasks. Cluster computer systems, grids, and Desktop Grids are three popular kinds of HC systems. An important component of an HC system is its resource management system (RMS). The main responsibility of an RMS is assigning resources to tasks in order to satisfy certain performance requirements. </p> <p> For cluster computer systems, we propose a new mapping heuristic which requires less state information than current heuristics. For Desktop Grids, we propose a new scheduling policy that exploits knowledge of the effective computing power delivered by the machines and the distribution of their fault times in order to improve performance. Finally, for grids, we propose a new decentralized load balancing policy which dramatically cuts down the communication overhead incurred in state information update. </p> <p> The proposed resource management policies utilize the solution to a linear programming problem (LP) which maximizes the system capacity. Our simulation experiments show that these policies perform very competitively, especially in highly heterogeneous systems. </p> / Thesis / Doctor of Philosophy (PhD)