Operations Research, Systems Engineering and Industrial Engineering Commons^™

Master Physician Scheduling Problem, Aldy Gunawan, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We study a real-world problem arising from the operations of a hospital service provider, which we term the master physician scheduling problem. It is a planning problem of assigning physicians’ full range of day-to-day duties (including surgery, clinics, scopes, calls, administration) to the defined time slots/shifts over a time horizon, incorporating a large number of constraints and complex physician preferences. The goals are to satisfy as many physicians’ preferences and duty requirements as possible while ensuring optimum usage of available resources. We propose mathematical programming models that represent different variants of this problem. The models were tested on a real …

Vehicle Minimization For The Multimodal Pickup And Delivery Problem With Time Windows, Benjamin A . Clapp

Theses and Dissertations

The algorithm proposed here is used for heuristic solutions for the Multimodal Multiple Vehicle Routing Problem with Unloading Capacity, Pickup and Dropoff, and Time Windows, solved so as to minimize the number of vehicles used, subject to varying objective function values for each vehicle. The MVRP is simplified and split into a routing problem and a scheduling problem. The routing problem is addressed by Dijkstra's Algorithm. This generates a new network for the second stage of the algorithm. It is assumed that the shortest path is the correct path to use, and shipments each travel unimodally. The scheduling problem is …

Meta-Heuristics Analysis For Technologically Complex Programs: Understanding The Impact Of Total Constraints For Schedule, Quality And Cost, Henry Darrel Webb

Engineering Management & Systems Engineering Projects for D. Eng. Degree

Program management data associated with a technically complex radio frequency electronics base communication system has been collected and analyzed to identify heuristics which may be utilized in addition to existing processes and procedures to provide indicators that a program is trending to failure. Analysis of the collected data includes detailed schedule analysis, detailed earned value management analysis and defect analysis within the framework of a Firm Fixed Price (FFP) incentive fee contract.

This project develops heuristics and provides recommendations for analysis of complex project management efforts such as those discussed herein. The analysis of the effects of the constraints on …

A New Metaheuristic Algorithm Motivated By The Rooting Phenomena In Plants, Behzad Nemati

All Theses

In this thesis, we present a new metaheuristic algorithm for analyzing challenging optimization problems. Initial testing reveals the potential for the algorithm, which is based on the rooting phenomena found in plants in nature, to quickly produce effective solutions to challenging combinatorial optimization problems in the class NP. We present computational results describing the proposed metaheuristic's efficacy for an important class of scheduling problems and discuss areas of future work and application.

Implementation Of Evolutionary Algorithms On The Power Industry And Aviation Security, Anuar Jesus Aguirre

Open Access Theses & Dissertations

The main objective of the power electric power grid is to supply reliable electricity to all the customers. Customers could be industrial, commercial, household, transportation and others. The power grid is a complex and large, and it formed by the conjunction of the generation, transmission and distribution system. The present research is focused in power distribution system. A new component replacement analysis method to solve component replacement problems for complex electricity distribution systems using Genetic Algorithms is developed. In the present model a Taylor series expansion is used to approximate the associated opportunity cost for each component in the system. …

Robust Distributed Scheduling Via Time Period Aggregation, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinatorial auction that is built on a general equilibrium framework. We adopt the general equilibrium framework and the particular combinatorial auction design from the literature, and we investigate the benefits and the limitation of time-period aggregation when demand-side uncertainties are introduced. By using simulation experiments on a real-life resource allocation problem from a container port, we show that, under stochastic conditions, the performance variation …

Finding Robust-Under-Risk Solutions For Flowshop Scheduling, Steven O. Kimbrough, Ann Kuo, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We propose and explore, in the context of benchmark problems for flowshop scheduling, a risk-based concept of robustness for optimization problems. This risk-based concept is in distinction to, and complements, the uncertainty-based concept employed in the field known as robust optimization. Implementation of our concept requires problem solution methods that sample the solution space intelligently and that produce large numbers of distinct sample points. With these solutions to hand, their robustness scores are easily obtained and heuristically robust solutions found. We find evolutionary computation to be effective for this purpose on these problems.

Optimization Models And Approximate Algorithms For The Aerial Refueling Scheduling And Rescheduling Problems, Sezgin Kaplan

Engineering Management & Systems Engineering Theses & Dissertations

The Aerial Refueling Scheduling Problem (ARSP) can be defined as determining the refueling completion times for fighter aircrafts (jobs) on multiple tankers (machines) to minimize the total weighted tardiness. ARSP can be modeled as a parallel machine scheduling with release times and due date-to-deadline window. ARSP assumes that the jobs have different release times, due dates, and due date-to-deadline windows between the refueling due date and a deadline to return without refueling. The Aerial Refueling Rescheduling Problem (ARRP), on the other hand, can be defined as updating the existing AR schedule after being disrupted by job related events including the …

Random Keys Genetic Algorithms Scheduling And Rescheduling Systems For Common Production Systems, Elkin Rodriguez-Velasquez

Engineering Management & Systems Engineering Theses & Dissertations

The majority of scheduling research deals with problems in specific production environments with specific objective functions. However, in many cases, more than one problem type and/or objective function exists, resulting in the need for a more generic and flexible system to generate schedules. Furthermore, most of the published scheduling research focuses on creating an optimal or near optimal initial schedule during the planning phase. However, after production processes start, circumstances like machine breakdowns, urgent jobs, and other unplanned events may render the schedule suboptimal, obsolete or even infeasible resulting in a "rescheduling" problem, which is typically also addressed for a …

Decentralized Resource Allocation And Scheduling Via Walrasian Auctions With Negotiable Agents, Huaxing Chen, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

This paper is concerned with solving decentralized resource allocation and scheduling problems via auctions with negotiable agents by allowing agents to switch their bid generation strategies within the auction process, such that a better system wide performance is achieved on average as compared to the conventional walrasian auction running with agents of fixed bid generation strategy. We propose a negotiation mechanism embedded in auctioneer to solicit bidders’ change of strategies in the process of auction. Finally we benchmark our approach against conventional auctions subject to the real-time large-scale dynamic resource coordination problem to demonstrate the effectiveness of our approach.

Project Scheduling To Maximize Positive Impacts Of Reconstruction Operations, Andrew D. Chaney

Theses and Dissertations

Since the decline of the Cold War, the risk of major conflict between powerful industrialized nations has significantly decreased. Insecurity in the twenty-first century is forecast to arise rather from the debris of imploding states. Such situations may require intervention | military or otherwise | by concerned states, and the frequency with which these interventions occur is increasing. To meet this new operational challenge, the US military must adapt its planning procedures to account for Security, Stabilization, Transition, and Reconstruction Operations (SSTRO). This research develops a project scheduling based framework for post-conflict reconstruction that prioritizes and schedules reconstruction activities in …

Summer Sessions Breakdown Of Course Dates And Time, Paul Savory

Department of Industrial and Management Systems Engineering: Faculty Publications

This report highlights an exhaustive analysis of the hundreds of Summer Session courses to develop an understanding of when they occur during the day and during which of the four academic terms. The analysis shows that the most popular time for scheduling courses is between 9:30 am and noon for each of the four summer session terms. Given the limited number of general purpose classrooms on campus, accommodating faculty preference for rooms, buildings, and computer equipment is sometimes not possible during the most in demand course times. The results also showcase the potential for having summer courses four-day per week …

Modeling Systems For Optimal Resource Allocation, Scheduling, And Decision Making, Esengul Tayfur

All Dissertations

This dissertation focuses on the resource requirements and scheduling problem for logistic systems. We investigate solutions to this problem in two different logistic systems: logistic system of the health care facilities during emergency evacuations and delivery and distribution system of production industries. All hospitals must have an evacuation plan to ensure the safety of patients and prevent the loss of life. However, hospital operators have not been able to quantify how resource availability, the cost of acquiring those resources, and evacuation completion time are related. This research addresses this problem and contributes two methodologies to solve this problem. In the …

Dynamic Allocation Of Airline Check-In Counters: A Queueing Optimisation Approach, Mahmut Parlar, Sharafali Moosa

Research Collection Lee Kong Chian School Of Business

This paper was motivated by an observation in an international airport with regard to allocation of resources for check-in counters. In an exclusive check-in counter system, each flight has a dedicated number of counters that will be open until at least a half-hour before the scheduled departure of that flight. Currently, in many of the airports around the world, the decision to open or close check-in counters is done on an ad hoc basis by human schedulers. In doing so, the schedulers are almost always forced to perform a balancing act in meeting the quality of service stipulated by the …

In-House Development Of Scheduling Decision Support Systems: Case Study For Scheduling Semiconductor Device Test Operations, Tali Freed, K. H. Doerr, T. Chang

Industrial and Manufacturing Engineering

Most manufacturing processes can benefit from an automated scheduling system. However;: the design of a fast, computerised scheduling system that achieves high-quality results and requires minimal resources is a difficult undertaking. Efficient .. scheduling of a semiconductor device test facility requires an information system that provides good schedules quickly. Semiconductor device testing-is the last stage of the long semiconductor manufacturing process, and therefore. is subjected to customer service pressures. The cost of an off-the-shelf computerised scheduling system may he prohibitive for many companies. In addition, many companies are taken aback by other characteristics of off-the-shelf scheduling systems, such as code …

Efficient Algorithms For Machine Scheduling Problems With Earliness And Tardiness Penalties, Guang Feng, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

In this paper, we study the multi-machine scheduling problem with earliness and tardiness penalties and sequence dependent setup times. This problem can be decomposed into two subproblems—sequencing and timetabling. Sequencing focuses on assigning each job to a fixed machine and determine the job sequence on each machine. We call such assignment a semi-schedule. Timetabling focuses on finding an executable schedule from the semi-schedule via idle-time insertion. Sequencing is strongly NP-hard in general. Although timetabling is polynomial-time solvable, it can become a computational bottleneck if the procedure is executed many times within a larger framework. This paper makes two contributions. We …

Exact And Heuristic Algorithms For The Job Shop Scheduling Problem With Earliness And Tardiness Over A Common Due Date, Leonardo Bedoya-Valencia

Engineering Management & Systems Engineering Theses & Dissertations

Scheduling has turned out to be a fundamental activity for both production and service organizations. As competitive markets emerge, Just-In-Time (JIT) production has obtained more importance as a way of rapidly responding to continuously changing market forces. Due to their realistic assumptions, job shop production environments have gained much research effort among scheduling researchers. This research develops exact and heuristic methods and algorithms to solve the job shop scheduling problem when the objective is to minimize both earliness and tardiness costs over a common due date. The objective function of minimizing earliness and tardiness costs captures the essence of the …

A Robust Reactive Scheduling System With Application To Parallel Machine Scheduling, Jean-Paul M. Arnaout

Engineering Management & Systems Engineering Theses & Dissertations

In this turbulent world, scheduling role has become crucial in most manufacturing production, and service systems. It allows the allocation of limited resources to activities with the objective of optimizing one performance measure or more. Resources may be machines in a factory, operating rooms in a hospital, or employees in a company, while activities can be jobs in a manufacturing plant, surgeries in a hospital, or paper work in a company. The goal of each schedule is to optimize some performance measures, which could be the minimization of the schedule makespan, the jobs' completion times, jobs' earliness and tardiness, among …

Optimization Model For Base-Level Delivery Routes And Crew Scheduling, Young-Ho Cha

Theses and Dissertations

In the U.S. Air Force, a Logistic Readiness Squadron (LRS) provides material management, distribution, and oversight of contingency operations. Dispatchers in the LRS must quickly prepare schedules that meet the needs of their customers while dealing with real-world constraints, such as time windows, delivery priorities, and intermittent recurring missions. Currently, LRS vehicle operation elements are faced with a shortage of manpower and lack an efficient scheduling algorithm and tool. The purpose of this research is to enhance the dispatchers' capability to handle flexible situations and produce "good" schedules within current manpower restrictions. In this research, a new scheduling model and …

Evaluation Of Scheduling Strategies On The Performance Of A Flexible Manufacturing Cell:A Simulation Study, Amr Arisha, Paul Young, Mohie El Baradie

Conference papers

The current trend in semiconductor manufacturing is characterized by expanding product variety, decreasing lead times from order to delivery, exacting standards of quality, and competitive prices. One possible means of achieving this is in the form of increased flexibility. Providing flexibility is typically an expensive proposition so, industrial engineers aim to provide more economic approaches to enable flexible manufacturing cells and related equipment to operate appropriately in an efficient manner. It is essential to characterize these tools in detail before the production plans are finalized. Using state-of-the-art computer simulation, a generic model of photolithography tools has been developed. The model …

A Combined Adaptive Tabu Search And Set Partitioning Approach For The Crew Scheduling Problem With An Air Tanker Crew Application, Todd E. Combs

Theses and Dissertations

This research develops the first metaheuristic approach to the complete air crew scheduling problem. It develops the first dynamic, integrated, set-partitioning based vocabulary scheme for metaheuristic search. Since no benchmark flight schedules exist for the tanker crew scheduling problem, this research defines and develops a Java™ based flight schedule generator. The robustness of the tabu search algorithms is judged by testing them using designed experiments. An integer program is developed to calculate lower bounds for the tanker crew scheduling problem objectives and to measure the overall quality of solutions produced by the developed algorithms.

A Value Focused Thinking Approach To Academic Course Scheduling, Shane A. Knighton

Theses and Dissertations

In 1997, the School of Engineering of the United States Air Force Institute of Technology began exploring ways of automating the academic course scheduling process. The administration desired an expedient approach for course scheduling which supports the institute's mission of "providing scientific and technological education" to officers from all branches of military service, as well as international military forces. The scheduling approach needed to be flexible, efficient, and represent the institute's values and principles. Decision Analysis (DA) and specifically, Value Focused Thinking (VFT), is used to decompose the complex problem of academic course scheduling and determine the factors that are …

A Transmission-Constrained Unit Commitment Method, Chung-Li Tseng, Chao-An Li, S. S. Oren, C. S. Cheng, A. J. Svoboda, R. B. Johnson

Engineering Management and Systems Engineering Faculty Research & Creative Works

The paper presents a transmission-constrained unit commitment method using a Lagrangian relaxation approach. The transmission constraints are modeled as linear constraints based on a DC power flow model. The transmission constraints, as well as the demand and spinning reserve constraints, are relaxed by attaching Lagrange multipliers. The authors take a new approach in the algorithmic scheme. A three-phase algorithm is devised including dual optimization, a feasibility phase and unit decommitment. A test problem involving more than 2500 transmission lines and 2200 buses is tested along with other test problems

A Robust Unit Commitment Algorithm For Hydro-Thermal Optimization, Chao-An Li, R. B. Johnson, A. J. Svoboda, Chung-Li Tseng, E. Hsu

Engineering Management and Systems Engineering Faculty Research & Creative Works

This paper presents a unit commitment algorithm which combines the Lagrangian relaxation (LR), sequential unit commitment (SUC), and optimal unit decommitment (UD) methods to solve a general hydro-thermal optimization (HTO) problem. We argue that this approach retains the advantages of the LR method while addressing the method''s observed weaknesses to improve overall algorithm performance and quality of solution. The proposed approach has been implemented in a version of PG&E''s HTO program, and test results are presented.

Scheduling And Sequencing Arrivals To A Stochastic Service System, Peter M. Vanden Bosch

Theses and Dissertations

Optimization of scheduled arrival times to an appointment system is approached from the perspectives of both queueing and scheduling theory. The appointment system is modeled as a one-server, first-come-first-served, transient queue with independent, distinctly distributed service times and no-show rates. If a customer does show, it is assumed to be punctual. The cost of operating the appointment system is a convex combination of customers' waiting times and the server's overtime. While techniques for finding the optimal static and dynamic schedules of arrivals have been proposed by other researchers, they mainly have focused on identical customers and strictly punctual arrivals. This …

Short-Term Resource Scheduling With Ramp Constraints [Power Generation Scheduling], Chung-Li Tseng, Chao-An Li, A. J. Svoboda, R. B. Johnson

Engineering Management and Systems Engineering Faculty Research & Creative Works

This paper describes a Lagrangian relaxation-based method to solve the short-term resource scheduling (STRS) problem with ramp constraints. Instead of discretizing the generation levels, the ramp rate constraints are relaxed with the system demand constraints using Lagrange multipliers. Three kinds of ramp constraints, startup, operating and shutdown ramp constraints are considered. The proposed method has been applied to solve the hydro-thermal generation scheduling problem at PG&E. An example alone with numerical results is also presented

Procedures For Testing Deterministic Scheduling Models: A Dakota Case Study, Keith H. Mccready

Theses and Dissertations

The DAKOTA scheduling system has been proposed for use in the United States Air Forces Europe's (USAFE's) Operational Support Airlift (OSA) scheduling. This thesis examines the OSA scheduling topic and reviews the relevant literature on vehicle routing, concluding that exact methods are intractable for large problem sizes. Consequently, heuristic methods must be considered. This thesis takes a detailed look at the DAKOTA heuristic. It examines the concepts of Validation, Verification and Accreditation (VV&A), particularly as they apply to heuristics and algorithms. It then defines what measures of performance may prove useful in judging heuristics and algorithms in general, and details …

An Improved Heuristic For Intercontinental Ballistic Missile Crew Scheduling, Michael D. Shirley Jr.

Theses and Dissertations

Creating monthly schedules for missile crews is a complex and time-consuming problem. Thousands of events must be scheduled for several hundred missile officers. The rules and regulations governing the problem are numerous, and there are currently no established measures for missile crew schedules. The scheduling software currently available only schedules a fraction of the events. The objectives of this research were to create a rule-based heuristic which could quickly produce feasible or near-feasible schedules, to make the scheduling process paperless, and to develop possible measures of effectiveness for missile crew schedules. The research was successful in each of these areas. …

Automated Manpower Rostering: Techniques And Experience, C. M. Khoong, Hoong Chuin Lau, L. W. Chew

Research Collection School Of Computing and Information Systems

We present ROMAN, a comprehensive, generic manpower rostering toolkit that successfully handles a wide spectrum of work policies found in service organizations. We review the use of various techniques and methodologies in the toolkit that contribute to its robustness and efficiency, and relate experience gained in addressing manpower rostering problems in industry.

Automating Satellite Range Scheduling, S. Michael Schalck

Theses and Dissertations

The objective of this study was to develop a computer based satellite range scheduling SRS algorithm to create a 24 hour satellite support schedule. The algorithms goal was to schedule as many satellite support requests as possible. An iterative heuristic approach was used to schedule satellite support requests in three successive sub problems. The first sub problem involves scheduling low altitude satellite support requests using a mixed integer programming approach. The next two sub problems each involve scheduling 12 hour blocks of medium and high altitude satellite support requests, again using a mixed integer programming approach. Fourteen 24 hour schedules …