Matching Items (26)
Description
Scheduling is critical in various industrial applications, ensuring the timely achievement and the efficient utilization of resources. While typically studied in production and manufacturing, scheduling problems have broader relevance. This dissertation presents scalable algorithms for large-scale scheduling problems in production planning and hydropower. The proposed Mathematical programming techniques help solve three problems: hydropower scheduling in single- and multiple-reservoir river systems, and a dual-resource scheduling problem. For hydropower scheduling, models optimize water release at reservoirs and dams to maximize power generation. The model includes socioeconomic dynamic goals for food, energy, and water demand, while also considering realistic potential factors like reservoir characteristics, water routing rules, and power production laws, among others. The approach discretizes water levels, simplifies nonconvex dynamics, and produces user-friendly operational curves for release guidance. Solutions employ large-scale integer linear programs and scalable decomposition algorithms. Real data from the Lower Mekong Basin is used to test these approaches. The dual-resource problem focuses on scheduling jobs requiring both machine and worker resources. Skilled workers handle one job at a time and travel within the facility. Formulated as a mixed-integer linear program with disjunctive constraints, the model prevents simultaneous task execution on the same machine or by the same worker. A decomposition approach treats disjunctive constraints as feasibility cuts added when violated. Acceleration techniques construct upper bounds using partial schedules from the branch-and-bound tree, which are also used to generate optimality cuts. These cuts progressively tighten the formulation, aiming to reduce the solution time. This dissertation presents scalable algorithms for large-scale scheduling problems in production planning and hydropower. Mathematical programming techniques, including decomposition and cutting plane algorithms, solve these problems effectively. The hydropower scheduling models optimize water release for maximum generation, while the dual-resource problem ensures efficient allocation of machine and worker resources. Real data and acceleration techniques enhance the solutions' practicality and efficiency.
ContributorsKaramyar, Fatemeh (Author) / Sefair, Jorge A. JS (Thesis advisor) / Askin, Ronald RA (Committee member) / Mirchandani, Pitu PM (Committee member) / Sabo, John L. JS (Committee member) / Arizona State University (Publisher)
Created2023
Description
This Master’s thesis includes the design, integration on-chip, and evaluation of a set of imitation learning (IL)-based scheduling policies: deep neural network (DNN)and decision tree (DT). We first developed IL-based scheduling policies for heterogeneous systems-on-chips (SoCs). Then, we tested these policies using a system-level domain-specific system-on-chip simulation framework [11]. Finally, we transformed them into efficient code using a cloud engine [1] and implemented on a user-space emulation framework [61] on a Unix-based SoC. IL is one area of machine learning (ML) and a useful method to train artificial intelligence (AI) models by imitating the decisions of an expert or Oracle that knows the optimal solution. This thesis's primary focus is to adapt an ML model to work on-chip and optimize the resource allocation for a set of domain-specific wireless and radar systems applications. Evaluation results with four streaming applications from wireless communications and radar domains show how the proposed IL-based scheduler approximates an offline Oracle expert with more than 97% accuracy and 1.20× faster execution time. The models have been implemented as an add-on, making it easy to port to other SoCs.
ContributorsHolt, Conrad Mestres (Author) / Ogras, Umit Y. (Thesis advisor) / Chakrabarti, Chaitali (Committee member) / Akoglu, Ali (Committee member) / Arizona State University (Publisher)
Created2020
Description
Ramping up a semiconductor wafer fabrication facility is a challenging endeavor. One of the key components of this process is to schedule a large number of activities in installing and qualifying (Install/Qual) the capital intensive and sophisticated manufacturing equipment. Activities in the Install/Qual process share multiple types of expensive and scare resources and each activity might potentially have multiple processing options. In this dissertation, the semiconductor capital equipment Install/Qual scheduling problem is modeled as a multi-mode resource-constrained project scheduling problem (MRCPSP) with multiple special extensions. Three phases of research are carried out: the first phase studies the special problem characteristics of the Install/Qual process, including multiple activity processing options, time-varying resource availability levels, resource vacations, and activity splitting that does not allow preemption. A modified precedence tree-based branch-and-bound algorithm is proposed to solve small size academic problem instances to optimality. Heuristic-based methodologies are the main focus of phase 2. Modified priority rule-based simple heuristics and a modified random key-based genetic algorithm (RKGA) are proposed to search for Install/Qual schedules with short makespans but subject to resource constraints. Methodologies are tested on both small and large random academic problem instances and instances that are similar to the actual Install/Qual process of a major semiconductor manufacturer. In phase 3, a decision making framework is proposed to strategically plan the Install/Qual capacity ramp. Product market demand, product market price, resource consumption cost, as well as the payment of capital equipment, are considered. A modified simulated annealing (SA) algorithm-based optimization module is integrated with a Monte Carlo simulation-based simulation module to search for good capacity ramping strategies under uncertain market information. The decision making framework can be used during the Install/Qual schedule planning phase as well as the Install/Qual schedule execution phase when there is a portion of equipment that has already been installed or qualified. Computational experiments demonstrate the effectiveness of the decision making framework.
ContributorsCheng, Junzilan (Author) / Fowler, John W (Thesis advisor) / Kempf, Karl (Thesis advisor) / Mason, Scott J. (Committee member) / Zhang, Muhong (Committee member) / Arizona State University (Publisher)
Created2015
Description
Woodland/Alloy Casting, Inc. is an aluminum foundry known for providing high-quality molds to their customers in industries such as aviation, electrical, defense, and nuclear power. However, as the company has grown larger during the past three years, they have begun to struggle with the on-time delivery of their orders. Woodland prides itself on their high-grade process that includes core processing, the molding process, cleaning process, and heat-treat process. To create each mold, it has to flow through each part of the system flawlessly. Throughout this process, significant bottlenecks occur that limit the number of molds leaving the system. To combat this issue, this project uses a simulation of the foundry to test how best to schedule their work to optimize the use of their resources. Simulation can be an effective tool when testing for improvements in systems where making changes to the physical system is too expensive. ARENA is a simulation tool that allows for manipulation of resources and process while also allowing both random and selected schedules to be run through the foundry’s production process. By using an ARENA simulation to test different scheduling techniques, the risk of missing production runs is minimized during the experimental period so that many different options can be tested to see how they will affect the production line. In this project, several feasible scheduling techniques are compared in simulation to determine which schedules allow for the highest number of molds to be completed.
ContributorsAdams, Danielle Renee (Author) / Pavlic, Theodore (Thesis director) / Montgomery, Douglas (Committee member) / Industrial, Systems & Operations Engineering Prgm (Contributor) / Barrett, The Honors College (Contributor)
Created2019-05
Description
Transportation around campus on time is crucial for in-person college students looking to succeed in their studies. Unfortunately, inequities have arisen between the ability of able-bodied students to get to and from class and permanently or temporarily disabled students looking to do the same. ASU’s solution to this problem, the Disability Access and Resource Transportation (DART) service, does adequately address the needs of its targeted customers properly. Unfortunately, student surveys and anecdotal evidence from students’ lived experiences have demonstrated that DART often leaves students waiting for more than half an hour for a ride, causes students to miss class, and is altogether unreliable in today’s age where punctuality is key to success. Our goal in our thesis project was to create an equal on-campus transportation playing field for students with and without mobility issues so that a students’ ability to get around campus would never serve as a hindrance to his/her ability to, at a minimum, earn a degree; ideally empowering all students to thrive regardless of their personal circumstances.
ContributorsLu, Sharon (Author) / Vohs, Grace (Co-author) / Habelt, Mark (Co-author) / Pham, Benjamin (Co-author) / Byrne, Jared (Thesis director) / Larson, Wiley (Committee member) / Balven, Rachel (Committee member) / Barrett, The Honors College (Contributor) / Department of Supply Chain Management (Contributor) / Department of Information Systems (Contributor)
Created2022-05
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 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.
ContributorsKhowala, Ketan (Author) / Fowler, John (Thesis advisor) / Keha, Ahmet (Thesis advisor) / Balasubramanian, Hari J (Committee member) / Wu, Teresa (Committee member) / Zhang, Muhong (Committee member) / Arizona State University (Publisher)
Created2012