Matching Items (4)

150733-Thumbnail Image.png

Single machine scheduling: comparison of MIP formulations and heuristics for interfering job sets

Description

This research by studies the computational performance of four different mixed integer programming (MIP) formulations for single machine scheduling problems with varying complexity. These formulations are based on (1) start and completion time variables, (2) time index variables, (3) linear

This research by studies the computational performance of four different mixed integer programming (MIP) formulations for single machine scheduling problems with varying complexity. These formulations are based on (1) start and completion time variables, (2) time index variables, (3) linear ordering variables and (4) assignment and positional date variables. The objective functions that are studied in this paper are total weighted completion time, maximum lateness, number of tardy jobs and total weighted tardiness. Based on the computational results, discussion and recommendations are made on which MIP formulation might work best for these problems. The performances of these formulations very much depend on the objective function, number of jobs and the sum of the processing times of all the jobs. Two sets of inequalities are presented that can be used to improve the performance of the formulation with assignment and positional date variables. Further, this research is extend to single machine bicriteria scheduling problems in which jobs belong to either of two different disjoint sets, each set having its own performance measure. These problems have been referred to as interfering job sets in the scheduling literature and also been called multi-agent scheduling where each agent's objective function is to be minimized. In the first single machine interfering problem (P1), the criteria of minimizing total completion time and number of tardy jobs for the two sets of jobs is studied. A Forward SPT-EDD heuristic is presented that attempts to generate set of non-dominated solutions. The complexity of this specific problem is NP-hard. The computational efficiency of the heuristic is compared against the pseudo-polynomial algorithm proposed by Ng et al. [2006]. In the second single machine interfering job sets problem (P2), the criteria of minimizing total weighted completion time and maximum lateness is studied. This is an established NP-hard problem for which a Forward WSPT-EDD heuristic is presented that attempts to generate set of supported points and the solution quality is compared with MIP formulations. For both of these problems, all jobs are available at time zero and the jobs are not allowed to be preempted.

Contributors

Agent

Created

Date Created
2012

153345-Thumbnail Image.png

Improving deterministic reserve requirements for security constrained unit commitment and scheduling problems in power systems

Description

Traditional deterministic reserve requirements rely on ad-hoc, rule of thumb methods to determine adequate reserve in order to ensure a reliable unit commitment. Since congestion and uncertainties exist in the system, both the quantity and the location of reserves are

Traditional deterministic reserve requirements rely on ad-hoc, rule of thumb methods to determine adequate reserve in order to ensure a reliable unit commitment. Since congestion and uncertainties exist in the system, both the quantity and the location of reserves are essential to ensure system reliability and market efficiency. The modeling of operating reserves in the existing deterministic reserve requirements acquire the operating reserves on a zonal basis and do not fully capture the impact of congestion. The purpose of a reserve zone is to ensure that operating reserves are spread across the network. Operating reserves are shared inside each reserve zone, but intra-zonal congestion may block the deliverability of operating reserves within a zone. Thus, improving reserve policies such as reserve zones may improve the location and deliverability of reserve.

As more non-dispatchable renewable resources are integrated into the grid, it will become increasingly difficult to predict the transfer capabilities and the network congestion. At the same time, renewable resources require operators to acquire more operating reserves. With existing deterministic reserve requirements unable to ensure optimal reserve locations, the importance of reserve location and reserve deliverability will increase. While stochastic programming can be used to determine reserve by explicitly modelling uncertainties, there are still scalability as well as pricing issues. Therefore, new methods to improve existing deterministic reserve requirements are desired.

One key barrier of improving existing deterministic reserve requirements is its potential market impacts. A metric, quality of service, is proposed in this thesis to evaluate the price signal and market impacts of proposed hourly reserve zones.

Three main goals of this thesis are: 1) to develop a theoretical and mathematical model to better locate reserve while maintaining the deterministic unit commitment and economic dispatch structure, especially with the consideration of renewables, 2) to develop a market settlement scheme of proposed dynamic reserve policies such that the market efficiency is improved, 3) to evaluate the market impacts and price signal of the proposed dynamic reserve policies.

Contributors

Agent

Created

Date Created
2015

154536-Thumbnail Image.png

Efficient formulations for next-generation choice-based network revenue management for airline implementation

Description

Revenue management is at the core of airline operations today; proprietary algorithms and heuristics are used to determine prices and availability of tickets on an almost-continuous basis. While initial developments in revenue management were motivated by industry practice, later developments

Revenue management is at the core of airline operations today; proprietary algorithms and heuristics are used to determine prices and availability of tickets on an almost-continuous basis. While initial developments in revenue management were motivated by industry practice, later developments overcoming fundamental omissions from earlier models show significant improvement, despite their focus on relatively esoteric aspects of the problem, and have limited potential for practical use due to computational requirements. This dissertation attempts to address various modeling and computational issues, introducing realistic choice-based demand revenue management models. In particular, this work introduces two optimization formulations alongside a choice-based demand modeling framework, improving on the methods that choice-based revenue management literature has created to date, by providing sensible models for airline implementation.

The first model offers an alternative formulation to the traditional choice-based revenue management problem presented in the literature, and provides substantial gains in expected revenue while limiting the problem’s computational complexity. Making assumptions on passenger demand, the Choice-based Mixed Integer Program (CMIP) provides a significantly more compact formulation when compared to other choice-based revenue management models, and consistently outperforms previous models.

Despite the prevalence of choice-based revenue management models in literature, the assumptions made on purchasing behavior inhibit researchers to create models that properly reflect passenger sensitivities to various ticket attributes, such as price, number of stops, and flexibility options. This dissertation introduces a general framework for airline choice-based demand modeling that takes into account various ticket attributes in addition to price, providing a framework for revenue management models to relate airline companies’ product design strategies to the practice of revenue management through decisions on ticket availability and price.

Finally, this dissertation introduces a mixed integer non-linear programming formulation for airline revenue management that accommodates the possibility of simultaneously setting prices and availabilities on a network. Traditional revenue management models primarily focus on availability, only, forcing secondary models to optimize prices. The Price-dynamic Choice-based Mixed Integer Program (PCMIP) eliminates this two-step process, aligning passenger purchase behavior with revenue management policies, and is shown to outperform previously developed models, providing a new frontier of research in airline revenue management.

Contributors

Agent

Created

Date Created
2016

158069-Thumbnail Image.png

Stacked-Value of Battery Storage: Effect of Battery Storage Penetration on Power Dispatch

Description

In this work, the stacked values of battery energy storage systems (BESSs) of various power and energy capacities are evaluated as they provide multiple services such as peak shaving, frequency regulation, and reserve support in an ‘Arizona-based test system’ -

In this work, the stacked values of battery energy storage systems (BESSs) of various power and energy capacities are evaluated as they provide multiple services such as peak shaving, frequency regulation, and reserve support in an ‘Arizona-based test system’ - a simplified, representative model of Salt River Project’s (SRP) system developed using the resource stack information shared by SRP. This has been achieved by developing a mixed-integer linear programming (MILP) based optimization model that captures the operation of BESS in the Arizona-based test system. The model formulation does not include any BESS cost as the objective is to estimate the net savings in total system operation cost after a BESS is deployed in the system. The optimization model has been formulated in such a way that the savings due to the provision of a single service, either peak shaving or frequency regulation or spinning reserve support, by the BESS, can be determined independently. The model also allows calculation of combined savings due to all the services rendered by the BESS.

The results of this research suggest that the savings obtained with a BESS providing multiple services are significantly higher than the same capacity BESS delivering a single service in isolation. It is also observed that the marginal contribution of BESS reduces with increasing BESS energy capacity, a result consistent with the law of diminishing returns. Further, small changes in the simulation environment, such as factoring in generator forced outage rates or projection of future solar penetration, can lead to changes as high as 10% in the calculated stacked value.

Contributors

Agent

Created

Date Created
2020