To see the other types of publications on this topic, follow the link: Dynamic scheduling.
Dissertations / Theses on the topic 'Dynamic scheduling'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Dynamic scheduling.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Burke, Peter. "Scheduling in dynamic environments." Thesis, University of Strathclyde, 1989. http://oleg.lib.strath.ac.uk:80/R/?func=dbin-jump-full&object_id=21291.
Full textAbstract:
Much of the work in the area of automated scheduling systems is based on the assumption that the intended execution environment is static and deterministic. The work presented in this thesis is motivated by recognition of the fact that most real world scheduling environments are dynamic and stochastic. It views the scheduling task as one of satisfaction rather than optimisation, and maintenance over creation. This thesis reviews existing work in the area and identifies an opportunity to combine recent advances in scheduling technology with the power of distributed processing. Within a suitable problem-solving architecture it is argued that this combination can help to address the fundamental problems of execudonal uncertainty, conflicting objectives and combinatorial complexity. A scheduling system, DAS, which employs such a problem-solving architecture, is presented. It is distributed, asynchronous and hierarchical, and requires careful management of problem-solving effort. DAS adopts an opportunistic approach to problem-solving and the management of problem-solving effort. The mechanisms which manage problem-solving effort within DAS are also presented. In conclusion it is argued that the architecture and mechanisms presented lend themselves very well to the view taken of the scheduling task.
2
Ellefsen, Kai Olav. "Dynamic Scheduling for Autonomous Robotics." Thesis, Norwegian University of Science and Technology, Department of Computer and Information Science, 2010. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-10857.
Full textAbstract:
This project report describes a hybrid genetic algorithm that works as a schedule generator for a complex robotic harvesting task. The task is set to a dynamic environment with a robotic opponent, making responsiveness of the planning algorithm particularly important. To solve this task, many previous scheduling algorithms were studied. Genetic algorithms have successfully been used in many dynamic scheduling tasks, due to their ability to incrementally adapt and optimize solutions when changes are made to the environment. Many of the previous approaches also used a separate heuristic to quicly adapt solutions to the new environment, making the algorithm more responsive. In addition, the study of previous work revealed the importance of population diversity when making a responsive genetic algorithm. Implementation was based on a genetic algorithm made as the author's fifth year specialization project for solving a static version of the same task. This algorithm was hybridized with a powerful local search technique that proved essential in generating good solutions for the complex harvesting task. When extending the algorithm to also work in a dynamically changing environment, several adaptations and extensions needed to be made, to make it more responsive. The extensions and adaptations include a fast-response heuristic for immediate adaptation to environmental changes, a decrease in genotype size to speed up local searches and a contingency planning module intending to solve problems before they arise. Experiments proved that the implemented dynamic planner successfully adapted its plans to a changing environment, clearly showing improvements compared to running a static plan. Further experiments also proved that the dynamic planner was able to deal with erroneous time estimates in its simulator module in a good way. Experiments on contingency planning gave no clear results, but indicated that using computational resources for planning ahead may be a good choice, if the contingency to plan for is carefully selected. As no unequivocal results were obtained, further studies of combining genetic algorithms and contingency planning may be an interesting task for future efforts.
3
Anagnostopoulos, Eleftherios. "Bus Scheduling including Dynamic Events." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-333029.
Full textAbstract:
Modern transportation systems should be designed according to the requirements of their passengers, while considering operational costs for the managing organizations,as well as being environmentally friendly. The main objective of this work is to provide a realistic simulation of a transportation system, capable of identifying connections among the road network of operation areas, creating bus lines composedof multiple connected bus stops, simulating travel requests registered by potential passengers, as well as generating routes and timetables for bus vehicles, while taking into consideration factors which could affect the predefined schedule, includingun predictable events (e.g., traffic accidents) or dynamic levels of traffic density.The implemented bus management system is able to generate timetables dynamically,introducing a reasoning mechanism capable of evaluating travel requests based on dynamic clustering techniques, while offering the opportunity to its administrator to make decisions regarding the number of generated timetables, operating bus vehicles,passengers per timetable, waiting time of passengers, and processing time. In addition,the routes of bus lines are generated or updated dynamically, while taking into consideration real-time traffic data and evaluating parameters, such as covered distance or travelling time, in order to identify the most effective connectionsbetween the bus stops of each bus line and make adjustments to the corresponding timetables. Finally, the number of operating bus vehicles that are required in order to transport the passengers of each bus line is estimated, leading to a more efficient distribution of available resources.
4
Ou, Jihong. "Dynamic scheduling of queueing networks." Thesis, Massachusetts Institute of Technology, 1991. http://hdl.handle.net/1721.1/13479.
Full text
5
Rosas, Ham Demian. "Dynamic scheduling in multicore processors." Thesis, University of Manchester, 2012. https://www.research.manchester.ac.uk/portal/en/theses/dynamic-scheduling-in-multicore-processors(c96d6641-ba16-44d2-9da5-34c41fd15956).html.
Full textAbstract:
The advent of multi-core processors, particularly with projections that numbers of cores will continue to increase, has focused attention on parallel programming. It is widely recognized that current programming techniques, including those that are used for scientific parallel programming, will not allow the easy formulation of general purpose applications. An area which is receiving interest is the use of programming styles which do not have side-effects. Previous work on parallel functional programming demonstrated the potential of this to permit the easy exploitation of parallelism. This thesis investigates a dynamic load balancing system for shared memory Chip Multiprocessors. This system is based on a parallel computing model called SLAM (Spreading Load with Active Messages), which makes use of functional language evaluation techniques. A novel hardware/software mechanism for exploiting fine grain parallelism is presented. This mechanism comprises a runtime system which performs dynamic scheduling and synchronization automatically when executing parallel applications. Additionally the interface for using this mechanism is provided in the form of an API. The proposed system is evaluated using cycle-level models and multithreaded applications running in a full system simulation environment.
6
Hsu, Chih-hua. "Dynamic scheduling of manufacturing systems /." Digital version accessible at:, 1998. http://wwwlib.umi.com/cr/utexas/main.
Full text
7
Heasley, McKay N. "Dynamic Appointment Scheduling in Healthcare." BYU ScholarsArchive, 2011. https://scholarsarchive.byu.edu/etd/3176.
Full textAbstract:
In recent years, healthcare management has become fertile ground for the scheduling theory community. In addition to an extensive academic literature on this subject, there has also been a proliferation of healthcare scheduling software companies in the marketplace. Typical scheduling systems use rule-based analytics that give schedulers advisory information from programmable heuristics such as the Bailey-Welch rule cite{B,BW}, which recommends overbooking early in the day to fill-in potential no-shows later on. We propose a dynamic programming problem formulation to the scheduling problem that maximizes revenue. We formulate the problem and discuss the effectiveness of 3 different algorithms that solve the problem. We find that the 3rd algorithm, which has smallest amount of nodes in the decision tree, has an upper bound given by the Bell numbers. We then present an alternative problem formulation that includes stochastic appointment lengths and no shows.
8
Khamooshi, H. "Heuristic network-based project scheduling : dynamic priority scheduling method; DPSM." Thesis, Lancaster University, 1994. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.267918.
Full text
9
Li, Caiwei. "Dynamic scheduling of multiclass queueing networks." Diss., Georgia Institute of Technology, 2000. http://hdl.handle.net/1853/24339.
Full text
10
Kreaseck, Barbara. "Dynamic autonomous scheduling on heterogeneous systmes /." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2003. http://wwwlib.umi.com/cr/ucsd/fullcit?p3102539.
Full text
11
Kazouris, Nicholas. "Dynamic scheduling on a network of workstations." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/mq22610.pdf.
Full text
12
Silvera-Munoz, Raul E. "Static instruction scheduling for dynamic issue processors." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape11/PQDD_0003/MQ44107.pdf.
Full text
13
Silvera, Muñoz Raúl E. "Static instruction scheduling for dynamic issue processors." Thesis, McGill University, 1997. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=20237.
Full textAbstract:
This thesis presents a novel approach to the instruction scheduling problem for dynamic issue processors. Our approach aims at generating an instruction sequence with a low register pressure and a high level of Instruction-Level Parallelism (ILP) exploitable by the dynamic issue mechanism of the processor. Our objective is to improve the performance of the program by taking advantage of the out-of-order execution and register renaming mechanisms of the processor to reduce the amount of spill code introduced by the register allocator.Our approach uses a traditional ILP scheduler to generate an initial schedule for the program, and then reorders its instructions to reduce the register pressure of the program. This reordering is performed carefully. to ensure that the dynamic issue mechanism of the processor is able to exploit from the reordered sequence as much parallelism as available on the original schedule.
We have proposed an approximate method to determine, for a given instruction sequence and a given instruction schedule, whether a particular dynamic issue superscalar processor can exploit from the sequence as much ILP as present in the schedule. (Abstract shortened by UMI.)
14
Kaler, Tim (Tim F. S. ). "Chromatic scheduling of dynamic data-graph computations." Thesis, Massachusetts Institute of Technology, 2013. http://hdl.handle.net/1721.1/85430.
Full textAbstract:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 67-73).
Data-graph computations are a parallel-programming model popularized by programming systems such as Pregel, GraphLab, PowerGraph, and GraphChi. A fundamental issue in parallelizing data-graph computations is the avoidance of races between computation occurring on overlapping regions of the graph. Common solutions such as locking protocols and bulk-synchronous execution often sacrifice performance, update atomicity, or determinism. A known alternative is chromatic scheduling which uses a vertex coloring of the conflict graph to divide data-graph updates into sets which may be parallelized without races. To date, however, only static data-graph computations, which do not schedule updates at runtime, have employed chromatic scheduling. I introduce PRISM, a work-efficient scheduling algorithm for dynamic data-graph computations that uses chromatic scheduling. For a collection of four application benchmarks on a modern multicore machine, chromatic scheduling approximately doubles the performance of the lock-based GraphLab implementation, and triples the performance of GraphChi's update execution phase when enforcing determinism. Chromatic scheduling motivates the development of efficient deterministic parallel coloring algorithms. New analysis of the Jones-Plassmann message-passing algorithm shows that only O([Delta] + In A in V/ In ln V) rounds are needed to color a graph G = (V, E) with max vertex degree [Delta], generalizing previous results for bounded degree graphs. A new log-degree ordering heuristic is described which can reduce the number of colors used in practice, while only increasing the number of rounds by a logrithmic factor. An efficient implementation for the shared-memory setting is described and analyzed using the CRQW contention model, showing that this algorithm performs [Theta](V + E) work and has expected span O([Delta] In [Delta]A + 1n 2[Delta] In V/In In V). Benchmarks on a set of real world graphs show that, in practice, these parallel algorithms achieve modest speedup over optimized serial code (around 4x on a 12-core machine).
by Tim Kaler.
M. Eng.
15
Puzović, Miloš. "Hardware/software interface for dynamic multicore scheduling." Thesis, University of Cambridge, 2013. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.648234.
Full text
16
Fahmy, Amer. "A dynamic scheduling model for construction enterprises." Thesis, Loughborough University, 2014. https://dspace.lboro.ac.uk/2134/16099.
Full textAbstract:
The vast majority of researches in the scheduling context focused on finding optimal or near-optimal predictive schedules under different scheduling problem characteristics. In the construction industry, predictive schedules are often produced in advance in order to direct construction operations and to support other planning activities. However, construction projects operate in dynamic environments subject to various real-time events, which usually disrupt the predictive optimal schedules, leading to schedules neither feasible nor optimal. Accordingly, the development of a dynamic scheduling model which can accommodate these real-time events would be of great importance for the successful implementation of construction scheduling systems. This research sought to develop a dynamic scheduling based solution which can be practically used for real time analysis and scheduling of construction projects, in addition to resources optimization for construction enterprises. The literature reviews for scheduling, dynamic scheduling, and optimization showed that despite the numerous researches presented and application performed in the dynamic scheduling field within manufacturing and other industries, there was dearth in dynamic scheduling literature in relation to the construction industry. The research followed two main interacting research paths, a path related to the development of the practical solution, and another path related to the core model development. The aim of the first path (or the proposed practical solution path) was to develop a computer-based dynamic scheduling framework which can be used in practical applications within the construction industry. Following the scheduling literature review, the construction project management community s opinions about the problem under study and the user requirements for the proposed solution were collected from 364 construction project management practitioners from 52 countries via a questionnaire survey and were used to form the basis for the functional specifications of a dynamic scheduling framework. The framework was in the form of a software tool fully integrated with current planning/scheduling practices with all core modelling which can support the integration of the dynamic scheduling processes to the current planning/scheduling process with minimal experience requirement from users about optimization. The second research path, or the dynamic scheduling core model development path, started with the development of a mathematical model based on the scheduling models in literature, with several extensions according to the practical considerations related to the construction industry, as investigated in the questionnaire survey. Scheduling problems are complex from operational research perspective; so, for the proposed solution to be functional in optimizing construction schedules, an optimization algorithm was developed to suit the problem's characteristics and to be used as part of the dynamic scheduling model's core. The developed algorithm contained few contributions to the scheduling context (such as schedule justification heuristics, and rectification to schedule generation schemes), as well as suggested modifications to the formulation and process of the adopted optimization technique (particle swarm optimization) leading to considerable improvement to this techniques outputs with respect to schedules quality. After the completion of the model development path, the first research path was concluded by combining the gathered solution's functional specifications and the developed dynamic scheduling model into a software tool, which was developed to verify & validate the proposed model s functionalities and the overall solution s practicality and scalability. The verification process started with an extensive testing of the model s static functionality using several well recognized scheduling problem sets available in literature, and the results showed that the developed algorithm can be ranked as one of the best state-of-the-art algorithms for solving resource-constrained project scheduling problems. To verify the software tool and the dynamic features of the developed model (or the formulation of data transfers from one optimization stage to the next), a case study was implemented on a construction entity in the Arabian Gulf area, having a mega project under construction, with all aspects to resemble an enterprise structure. The case study results showed that the proposed solution reasonably performed under large scale practical application (where all optimization targets were met in reasonable time) for all designed schedule preparation processes (baseline, progress updates, look-ahead schedules, and what-if schedules). Finally, to confirm and validate the effectiveness and practicality of the proposed solution, the solution's framework and the verification results were presented to field experts, and their opinions were collected through validation forms. The feedbacks received were very positive, where field experts/practitioners confirmed that the proposed solution achieved the main functionalities as designed in the solution s framework, and performed efficiently under the complexity of the applied case study.
17
Maesano, Ariele. "Bayesian dynamic scheduling for service composition testing." Thesis, Paris 6, 2015. http://www.theses.fr/2015PA066100/document.
Full textAbstract:
Aujourd'hui la connectivité entre les systèmes se standardise. Il supprime l'intervention humaine et permet aux systèmes distribués d'accomplir des tâches longues et complexes. La SOA est une approche fondée sur le modèle qui s'appuie sur des contrats et qui permet aux systèmes existants de collaborer par échange de messages. De multiples organisations peuvent, automatiser des échanges de services sans risquer leur confidentialité. Cette collaboration est à l'origine des difficultés concernant le test, parce que si il a des échanges entre les différents partenaires, le fonctionnement interne de processus résultant dans l'information échangé est limité à certains partenaires/testeurs. Ceci nous place dans un cadre de tests boîte grise où les systèmes sont des boîtes noires et seulement l'échange de message est visible. C'est pourquoi nous proposons une approche probabiliste en utilisant l'inférence bayésienne pour tester les SOA. Le deuxième défi est leur taille. Etant donné que les systèmes sont connectés de manière lâche en les couplant deux par deux selon les spécifications, une SOA peut contenir un nombre très important de participants et donc une grande taille. La taille des SOA se reflète dans la complexité de l'inférence bayésienne. Cette seconde contrainte pousse à chercher de meilleure solution pour l'inférence bayésienne. Afin de faire face à la taille et la densité de la BN, même pour de petits services architectures, les techniques d'inférence par compilation dirigée par les modèles qui permet la génération rapide de circuits arithmétiques directement à partir du modèle de l'architecture des services et de la suite de tests sont en cours d'élaborationIn present times connectivity between systems becomes more common. It removes human mediation and allows complex distributed systems to autonomously complete long and complex tasks. SOA is a model driven contract based approach that allows legacy systems to collaborate by messages exchange. Collaboration, here, is a key word in the sense that multiple organisation can, with this approach, automate services exchanges between them without putting at risks their confidentiality. This cause to encounter the first difficulty, because if there are exchanges between the different partners, the inner-processes resulting in the exchange information is restricted to some partners and therefor to some of the testers. That put us in a grey-box testing case where the systems are black-boxes and only the message exchange is visible. That is why we propose a probabilistic approach using Bayesian Inference to test the architectures. The second Challenge is the size of the SOA. Since the systems are connected by loosely coupling them two by two according to SOA Specifications, SOA can contain a very important number of participants. In Fact most of the existing SOA are very important in there size. The size of the SOA is reflected in the complexity of the Bayesian inference. This second challenge constraints us to search for better solution for the Bayesian Inference. In order to cope with the size and density of the BN for even small services architectures, techniques of model-driven inference by compilation that allows quick generation of arithmetic circuits directly from the services architecture model and the test suite are being developed
18
Clem, Doyne Damian. "Logistically-constrained asset scheduling in maritime security operations." Thesis, Monterey, Calif. : Naval Postgraduate School, 2008. http://edocs.nps.edu/npspubs/scholarly/theses/2008/Sept/08Sep%5FClem.pdf.
Full textAbstract:
Thesis (M.S. in Operations Research)--Naval Postgraduate School, September 2008.Thesis Advisor(s): Royset, Johannes O. "September 2008." Description based on title screen as viewed on November 5, 2008. Includes bibliographical references (p. 37-38). Also available in print.
19
Meier, Tobias, Michael Ernst, Andreas Frey, and Wolfram Hardt. "Enhancing Task Assignment in Many-Core Systems by a Situation Aware Scheduler." Universitätsbibliothek Chemnitz, 2017. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-227009.
Full textAbstract:
The resource demand on embedded devices is constantly growing. This is caused by the sheer explosion of software based functions in embedded systems, that are growing far faster than the resources of the single-core and multi-core embedded processors. As one of the limitation is the computing power of the processors we need to explore ways to use this resource more efficiently. We identified that during the run-time of the embedded devices the resource demand of the software functions is permanently changing dependent on the device situation. To enable an embedded device to take advantage of this dynamic resource demand, the allocation of the software functions to the processor must be handled by a scheduler that is able to evaluate the resource demand of the software functions in relation to the device situation. This marks a change in embedded devices from static defined software systems to dynamic software systems. Above that we can increase the efficiency even further by extending the approach from a single device to a distributed or networked system (many-core system). However, existing approaches to deal with dynamic resource allocation are focused on individual devices and leave the optimization potential of manycore systems untouched. Our concept will extend the existing Hierarchical Asynchronous Multi-Core Scheduler (HAMS) concept for individual devices to many-core systems. This extension introduces a dynamic situation aware scheduler for many-core systems which take the current workload of all devices and the system-situation into account. With our approach, the resource efficiency of an embedded many-core system can be increased. The following paper will explain the architecture and the expected results of our concept.
20
Grünert, Tore. "Multi-level sequence dependent dynamic lotsizing and scheduling /." Aachen : Shaker, 1998. http://bvbr.bib-bvb.de:8991/F?func=service&doc_library=BVB01&doc_number=008024324&line_number=0001&func_code=DB_RECORDS&service_type=MEDIA.
Full text
21
Charrier, Ghislain. "Scheduling and Dynamic Management of Applications over Grids." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2010. http://tel.archives-ouvertes.fr/tel-00590292.
Full textAbstract:
Les travaux présentés dans cette thèse portent sur l'ordonnancement d'applications au sein d'un environnement de grille de calcul. Nous étudions comment mieux gérer les tâches au sein des intergiciels de grille, ceci dans l'objectif d'améliorer les performances globales de la plateforme. Les solutions que nous proposons se situent dans l'intergiciel, ce qui permet de conserver les architectures sous-jacentes sans les modifier. Dans un premier temps, nous proposons un mécanisme de réallocation permettant de prendre en compte dynamiquement les erreurs d'ordonnancement commises lors de la soumission de calculs. En effet, lors de la soumission sur une machine parallèle, il est souvent nécessaire de fournir une estimation du temps d'exécution afin que celle-ci puisse effectuer un ordonnancement. Cependant, les estimations ne sont pas précises et les décisions d'ordonnancement sont sans cesse remises en question. Le mécanisme de réallocation proposé permet de prendre en compte ces changements en déplaçant des calculs d'une machine parallèle à une autre. Le second point auquel nous nous intéressons dans cette thèse est l'ordonnancement d'une application de climatologie sur la grille. Afin de fournir les meilleures performances possibles nous avons modélisé l'application puis proposé des heuristiques spécifiques. Pour exécuter l'application sur une grille de calcul, l'intergiciel utilise ces connaissances sur l'application pour fournir le meilleur ordonnancement possible.
22
Weilnau, Gregory P. "A dynamic scheduling monitor for a manufacturing process /." Online version of thesis, 1990. http://hdl.handle.net/1850/10600.
Full text
23
Sauré, Antoine. "Approximate dynamic programming methods for advance patient scheduling." Thesis, University of British Columbia, 2012. http://hdl.handle.net/2429/43448.
Full textAbstract:
This dissertation studies an advance multi-priority patient scheduling problem. Patrick et al. (2008) formulated a version of this problem as a discounted infinite-horizon Markov decision process (MDP) and studied it using a linear programming method based on an affine value function approximation. This thesis starts by presenting an alternative solution approach for this problem based on the use of simulation, a policy iteration framework and a non-linear value function approximation. It then extends the dynamic multi-priority patient scheduling model and solution approach developed by Patrick et al. by considering patients who receive service across multiple days and for irregular lengths of time, and by allowing the possibility of using overtime on different days of the booking horizon. The research described in this dissertation is based on the hypothesis that some patients can be booked further into the future allowing the appointments for urgent patients to be scheduled earlier, and it seeks to identify effective policies for allocating available service capacity to incoming demand while reducing patient wait times in a cost-effective manner. Through the use of approximate dynamic programming techniques, it illustrates the importance of adequately assessing the future impact of today's decisions in order to more intelligently allocate capacity. Chapter 1 provides an overview of the multi-priority patient scheduling problem and a review of the literature relevant to it. Chapter 2 describes a simulation-based algorithm for solving a version of this problem and compares the performance of the resulting appointment scheduling policies against the performance of four other policies, including the one derived from the linear programming method. Chapter 3 extends the dynamic multi-priority patient scheduling model and solution approach developed by Patrick et al. It presents a discounted infinite-horizon MDP model for scheduling cancer treatments in radiation therapy units and a linear programming method for solving it. The benefits from the proposed method are evaluated by simulating its performance for a practical example based on data provided by the British Columbia Cancer Agency. Chapter 4 describes a teaching tool developed to illustrate advance patient scheduling practices to health care professionals and students. Finally, this dissertation concludes with additional discussion, extensions and further applications.
24
马俊 and Jun Ma. "Dynamic production scheduling in virtual cellular manufacturing systems." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2012. http://hdl.handle.net/10722/193066.
Full textAbstract:
Manufacturing companies must constantly improve productivity to respond to dynamic changes in customer demand in order to maintain their competitiveness and marketshares. This requires manufacturers to adopt more efficient methodologies to design and control their manufacturing systems. In recent decades, virtual cellular manufacturing (VCM), as an advanced manufacturing concept, has attracted increasing attention in the research community, because traditional cellular manufacturing is inadequate when operating in a highly dynamic manufacturing environment. Virtual cellular manufacturing temporarily and dynamically groups production resources to form virtual cells according to production requirements, thus enjoying high production efficiency and flexibility simultaneously. The objective of this research is to develop cost-effective methodologies for manufacturing cell formation and production scheduling in virtual cellular manufacturing systems (VCMSs), operating in single-period/multi-period, and dynamic manufacturing environments.
In this research, two mathematical models are developed to describe the characteristics of VCMSs operating under a single-period and a multi-period manufacturing environment respectively. These models aim to develop production schedules to minimize the total manufacturing cost incurred in manufacturing products for the entire planning horizon, taking into consideration many practical constraints such as workforce requirements, effective capacities of production resources, and delivery due dates of orders. In the multi-period case, worker training is also considered and factors affecting worker training are analyzed in detail.
This research also develops a novel hybrid algorithm to solve complex production scheduling problems optimally for VCMSs. The hybrid algorithm is based on the techniques of discrete particle swarm optimization, ant colony system and constraint programming. Its framework is discrete particle swarm optimization which can locate good production schedules quickly. To prevent the optimization process being trapped into a local optimum, concepts of ant colony system and constraint programming are incorporated into the framework to greatly enhance the exploration and exploitation of the solution space, thus ensuring better quality production schedules. Sensitivity analyses of the key parameters of the hybrid algorithm are also conducted in detail to provide a theoretical foundation which shows that the developed hybrid algorithm is indeed an excellent optimization tool for production scheduling in VCMSs.
In practice, the occurrence of unpredictable events such as breakdown of machines, change in the status of orders and absenteeism of workers will make the current production schedule infeasible. A new feasible production schedule may therefore need to be generated rapidly to ensure smooth manufacturing operations. This research develops several cost-effective production rescheduling strategies for VCMSs operating under different dynamic manufacturing environments. These strategies facilitates the determination of when-to and how-to take rescheduling actions. To further enhance the performance of such strategies in generating new production schedules, especially for large-scale manufacturing systems, a parallel approach is established to implement the developed hybrid algorithm on GPU with compute unified device architecture.
The convergence characteristics of the proposed hybrid algorithm are also studied theoretically by using probability theory and Markov chain model. The analysis results show that the optimization process will eventually converge to the global optimal solution.published_or_final_version
Industrial and Manufacturing Systems Engineering
Doctoral
Doctor of Philosophy
25
Hatcher, P. "Dynamic scheduling of functional programs on MIMD computers." Thesis, University of York, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.362063.
Full text
26
Salgame, Rangnath R. "A knowlege-based system approach for dynamic scheduling." Thesis, Virginia Tech, 1987. http://hdl.handle.net/10919/45907.
Full textAbstract:
Scheduling is one of the most important functions in a factory and it is determining when and with what resources jobs should be accomplished. An important factor that affects the scheduling of jobs is the dynamic variation of factory status. Existing computer based scheduling systems do not address the need of making effective decisions dynamically with the variations in factory status. Traditionally, Operations Research techniques have provided an effective tool in solving manufacturing planning problems. But these methods have not been able to effectively address real time control problems in the manufacturing environment.
To address some of these problems, this research investigates applying an expert system approach to develop an interactive real time dynamic scheduling system. Specifically, a knowledge base structure is developed and applied to a case study representing a two stage production system.
A Blackboard concept has been utilized to organize and maintain the dynamic data base. The major knowledge representation schemes used in the system include, frame structures, relational tables, and production rules. The system was tested on a case study, by conducting a sample interactive session on a set of simulated dynamic situations. The test demonstrated the viability of implementing knowledge based systems for dynamic scheduling at the operational level of a plant.
Master of Science
27
Khanna, Sankalp. "Distributed Constraint Optimization and Scheduling in Dynamic Environments." Thesis, Griffith University, 2010. http://hdl.handle.net/10072/365689.
Full textAbstract:
Effcient scheduling of resources in a complex dynamic environment poses a significant
research challenge. The problem is compounded in the case of a distributed
real world environment where several departments are working at optimizing their
own resources. Multiple departmental schedules thus need to be optimized simultaneously
to ensure proper utilization of resources.
Much of the current eorts at solving scheduling problems with these characteristics
fail to model the inherent complexity and dynamism, leaving the task of making
the actual scheduling decisions to the user. The work described in this thesis aims
to provide a multi-agent framework, driven by a distributed constraint optimization
strategy, to model and eciently solve this class of problems.
The foundation case studied in this thesis is the elective surgery scheduling problem,
as it is an intrinsically distributed and complex real world problem. Ecient
scheduling of elective surgery is of critical importance to the optimum utilization of
the public health system, a topical issue with an aging population.
A summary of the main contributions of this study is as follows:
We present an intelligent agent based approach for solving complex distributed
scheduling problems in dynamic environments. Motivated by the challenge of
solving the real world problem of scheduling elective surgery in an underresourced
and encumbered health system, we propose a methodology which
can be used to build intelligent software agents that generate optimal schedules
on behalf of their respective departments. In our solution, each agent,
trained with the appropriate constraints, preferences and priorities, optimizes
schedules for their respective department and then negotiates to resolve interagent
constraints. The architecture of each agent incorporates an interface
module to handle internal and external communication, an intelligence modi
ule to perform decision making and learning, and a Distributed Constraint
Optimization Problem (DCOP) engine to drive the optimization. [Part of
this work was published at the MedInfo 2007 World Congress (Khanna et al.,
2007b)].
We propose an algorithm, the Dynamic Complex Distributed Constraint Optimization
Problem (DCDCOP) algorithm, for solving Dynamic Complex DCOP
problems. DCDCOP does not rely on the static organization of agents into
depth first search trees for problem solving, and is capable of handling complex
sub-problems, found in many real world DCOP problems, without using
decomposition or compilation. Further, it allows each agent the
exibility to choose its own local solver. We also introduce a novel metric called Degree of
Unsatisfaction (DU) and use it for guiding inter-agent negotiation for problem
solving in the DCDCOP algorithm. Empirical evaluation of the DCDCOP algorithm
and the DU metric is reported to establish their suitability for the class of problem we seek to address. [Parts of this work were published at the AAMAS 2009 conference (Khanna et al., 2009c) and the WI/IAT 2009 conference (Khanna et al., 2009c)].
We introduce ASES, an Automated Scheduler for Elective Surgery. Developed
as a proof-of-concept prototype application, ASES represents the novel marriage
of rational agency and distributed constraint optimization necessitated
by the problem domain. It aptly demonstrates the suitability of using our
proposed methodology for providing ongoing schedule optimization and can
also be used to study the eect of
uctuation in stang or resource levels
on theatre utilization. [Part of this work was published at the PRIMA 2010
Conference (Khanna et al., 2010)].
iiThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Information and Communication Technology
Science, Environment, Engineering and Technology
Full Text
28
Corbalán, González Julita. "Coordinated Scheduling and Dynamic Performance Analysis in Multiprocessors Systems." Doctoral thesis, Universitat Politècnica de Catalunya, 2002. http://hdl.handle.net/10803/5968.
Full textAbstract:
El rendimiento de los actuales sistemas multiprocesador de memoria compartida depende tanto de la utilización eficiente de todos los componentes del sistema (procesadores, memoria, etc), como de las características del conjunto de aplicaciones a ejecutar. Esta Tesis tiene como principal objetivo mejorar la ejecución de conjuntos de aplicaciones paralelas en sistemas multiprocesador de memoria compartida mediante la utilización de información sobre el rendimiento de las aplicaciones para la planificación de los procesadores.Es una práctica común de los usuarios de un sistema multiprocesador reservar muchos procesadores para ejecutar sus aplicaciones asumiendo que cuantos más procesadores utilicen mejor rendimiento sacarán sus aplicaciones. Sin embargo, normalmente esto no es cierto. Las aplicaciones paralelas tienen diferentes características respecto a su escalabilidad. Su rendimiento depende además de parámetros que sólo son conocidos en tiempo de ejecución, como por ejemplo el conjunto de datos de entrada o la influencia que pueden ejercer determinadas aplicaciones que se ejecutan de forma concurrente.
En esta tesis proponemos que el sistema no base sus decisiones solamente en las peticiones de recursos de los usuarios sino que él, dinámicamente, mida el rendimiento que están consiguiendo las aplicaciones y base, o ajuste, sus decisiones teniendo en cuenta esa información.
El rendimiento de las aplicaciones paralelas puede ser medido por el sistema de forma dinámica y automática sin introducir una sobrecarga significativa en la ejecución de las aplicaciones. Utilizando esta información, la planificación de procesadores puede ser decidida, o ajustada, siendo mucho más robusta a requerimientos incorrectos por parte de los usuarios, que otras políticas que no consideran este tipo de información. Además de considerar el rendimiento, proponemos imponer una eficiencia objetivo a las aplicaciones paralelas. Esta eficiencia objetivo determinará si la aplicación está consiguiendo un rendimiento aceptable o no, y será usada para ajustar la asignación de procesadores. La eficiencia objetivo de un sistema podrá ser un parámetro ajustable dinámicamente en función del estado del sistema: número de aplicaciones ejecutándose, aplicaciones encoladas, etc.
También proponemos coordinar los diferentes niveles de planificación que intervienen en la planificación de procesadores: Nivel librería de usuario, planificador de procesadores (en el S.O), y gestión del sistema de colas. La idea es establecer una interficie entre niveles para enviar y recibir información entre niveles, así como considerar esta información para tomar las decisiones propias de cada nivel.
La evaluación de esta Tesis ha sido realizada utilizando un enfoque práctico. Hemos diseñado e implementado un entorno de ejecución completo para ejecutar aplicaciones paralelas que siguen el modelo de programación OpenMP. Hemos introducido nuestras propuestas modificando los tres niveles de planificación mencionados.
Los resultados muestran que las ideas propuestas en esta tesis mejoran significativamente el rendimiento del sistema. En aquellos casos en que tanto las aplicaciones como los parámetros del sistema han sido previamente optimizados, las propuestas realizadas introducen una penalización del 5% en el peor de los casos, comparado con el mejor de los resultados obtenidos por otras políticas evaluadas. Sin embargo, en otros casos evaluados, las propuestas realizadas en esta tesis han mejorado el rendimiento del sistema hasta un 400% también comparado con el mejor resultado obtenido por otras políticas evaluadas.
Las principales conclusiones que podemos obtener de esta Tesis son las siguientes:
- El rendimiento de las aplicaciones paralelas puede ser medido en tiempo de ejecución. Los requisitos para aplicar el mecanismo de medida propuesto en esta Tesis son que las aplicaciones sean maleables y estar en un entorno de ejecución multiprocesador de memoria compartida.
- El rendimiento de las aplicaciones paralelas debe ser considerado para decidir la asignación de procesadores a aplicaciones. El sistema debe utilizar la información del rendimiento para auto-ajustar sus decisiones. Además, el sistema debe imponer una eficiencia objetivo para asegurar el uso eficiente de procesadores.
- Los diferentes niveles de planificación deben estar coordinados para evitar interferencias entre ellos
The performance of current shared-memory multiprocessor systems depends on both the efficient utilization of all the architectural elements in the system (processors, memory, etc), and the workload characteristics.
This Thesis has the main goal of improving the execution of workloads of parallel applications in shared-memory multiprocessor systems by using real performance information in the processor scheduling.
It is a typical practice of users in multiprocessor systems to request for a high number of processors assuming that the higher the processor request, the higher the number of processors allocated, and the higher the speedup achieved by their applications. However, this is not true.
Parallel applications have different characteristics with respect to their scalability. Their speedup also depends on run-time parameters such as the influence of the rest of running applications.
This Thesis proposes that the system should not base its decisions on the users requests only, but the system must decide, or adjust, its decisions based on real performance information calculated at run-time.
The performance of parallel applications is information that the system can dynamically measure without introducing a significant penalty in the application execution time. Using this information, the processor allocation can be decided, or modified, being robust to incorrect processor requests given by users. We also propose that the system use a target efficiency to ensure the efficient use of processors. This target efficiency is a system parameter and can be dynamically decided as a function of the characteristics of running applications or the number of queued applications.
We also propose to coordinate the different scheduling levels that operate in the processor scheduling: the run-time scheduler, the processor scheduler, and the queueing system. We propose to establish an interface between levels to send and receive information, and to take scheduling decisions considering the information provided by the rest of levels.
The evaluation of this Thesis has been done using a practical approach. We have designed and implemented a complete execution environment to execute OpenMP parallel applications. We have introduced our proposals, modifying the three scheduling levels (run-time library, processor scheduler, and queueing system).
Results show that the ideas proposed in this Thesis significantly improve the system performance. If the evaluated workload has been previously tuned, in the worst case, we have introduced a slowdown around 5% in the workload execution time compared with the best execution time achieved. However, in some extreme cases, with a workload and a system configuration not previously tuned, we have improved the system performance in a 400%, also compared with the next best time.
The main results achieved in this Thesis can be summarized as follows:
- The performance of parallel applications can be measured at run-time. The requirements to apply the mechanism proposed in this Thesis are to have malleable applications and shared-memory multiprocessor architectures.
- The performance of parallel applications 1must be considered to decide the processor allocation. The system must use this information to self-adjust its decisions based on the achieved performance. Moreover, the system must impose a target efficiency to ensure the efficient use of processors.
- The different scheduling levels must be coordinated to avoid interferences between levels.
29
Martorell, Bofill Xavier. "Dynamic Scheduling of Parallel Applications on Shared-Memory Multiprocessors." Doctoral thesis, Universitat Politècnica de Catalunya, 1999. http://hdl.handle.net/10803/6010.
Full text
30
Gurumurthy, Prakash. "Dynamic stochastic vehicle routing model in home healthcare scheduling /." free to MU campus, to others for purchase, 2004. http://wwwlib.umi.com/cr/mo/fullcit?p1426064.
Full text
31
Villebonnet, Violaine. "Scheduling and Dynamic Provisioning for Energy Proportional Heterogeneous Infrastructures." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSEN057/document.
Full textAbstract:
La consommation énergétique des centres de calculs et de données, aussi appelés « data centers », représentait 2% de la consommation mondiale d'électricité en 2012. Leur nombre est en augmentation et suit l'évolution croissante des objets connectés, services, applications, et des données collectées. Ces infrastructures, très consommatrices en énergie, sont souvent sur-dimensionnées et les serveurs en permanence allumés. Quand la charge de travail est faible, l'électricité consommée par les serveurs inutilisés est gaspillée, et un serveur inactif peut consommer jusqu'à la moitié de sa consommation maximale. Cette thèse s'attaque à ce problème en concevant un data center ayant une consommation énergétique proportionnelle à sa charge. Nous proposons un data center hétérogène, nommé BML pour « Big, Medium, Little », composé de plusieurs types de machines : des processeurs très basse consommation et des serveurs classiques. L'idée est de profiter de leurs différentes caractéristiques de performance, consommation, et réactivité d'allumage, pour adapter dynamiquement la composition de l'infrastructure aux évolutions de charge. Nous décrivons une méthode générique pour calculer les combinaisons de machines les plus énergétiquement efficaces à partir de données de profilage de performance et d'énergie acquis expérimentalement considérant une application cible, ayant une charge variable au cours du temps, dans notre cas un serveur web.Nous avons développé deux algorithmes prenant des décisions de reconfiguration de l'infrastructure et de placement des instances de l'application en fonction de la charge future. Les différentes temporalités des actions de reconfiguration ainsi que leur coûts énergétiques sont pris en compte dans le processus de décision. Nous montrons par simulations que nous atteignons une consommation proportionnelle à la charge, et faisons d'importantes économies d'énergie par rapport aux gestions classiques des data centersThe increasing number of data centers raises serious concerns regarding their energy consumption. These infrastructures are often over-provisioned and contain servers that are not fully utilized. The problem is that inactive servers can consume as high as 50% of their peak power consumption.This thesis proposes a novel approach for building data centers so that their energy consumption is proportional to the actual load. We propose an original infrastructure named BML for "Big, Medium, Little", composed of heterogeneous computing resources : from low power processors to classical servers. The idea is to take advantage of their different characteristics in terms of energy consumption, performance, and switch on reactivity to adjust the composition of the infrastructure according to the load evolutions. We define a generic methodology to compute the most energy proportional combinations of machines based on hardware profiling data.We focus on web applications whose load varies over time and design a scheduler that dynamically reconfigures the infrastructure, with application migrations and machines switch on and off, to minimize the infrastructure energy consumption according to the current application requirements.We have developed two different dynamic provisioning algorithms which take into account the time and energy overheads of the different reconfiguration actions in the decision process. We demonstrate through simulations based on experimentally acquired hardware profiles that we achieve important energy savings compared to classical data center infrastructures and management
32
Dalakoti, Animesh. "Enhanced quality of service in Internet using dynamic scheduling." Online access for everyone, 2007. http://www.dissertations.wsu.edu/Thesis/Summer2007/A_Dalakoti_072307.pdf.
Full text
33
Svärd, Petter. "Dynamic Cloud Resource Management : Scheduling, Migration and Server Disaggregation." Doctoral thesis, Umeå universitet, Institutionen för datavetenskap, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-87904.
Full textAbstract:
A key aspect of cloud computing is the promise of infinite, scalable resources, and that cloud services should scale up and down on demand. This thesis investigates methods for dynamic resource allocation and management of services in cloud datacenters, introducing new approaches as well as improvements to established technologies.Virtualization is a key technology for cloud computing as it allows several operating system instances to run on the same Physical Machine, PM, and cloud services normally consists of a number of Virtual Machines, VMs, that are hosted on PMs. In this thesis, a novel virtualization approach is presented. Instead of running each PM isolated, resources from multiple PMs in the datacenter are disaggregated and exposed to the VMs as pools of CPU, I/O and memory resources. VMs are provisioned by using the right amount of resources from each pool, thereby enabling both larger VMs than any single PM can host as well as VMs with tailor-made specifications for their application. Another important aspect of virtualization is live migration of VMs, which is the concept moving VMs between PMs without interruption in service. Live migration allows for better PM utilization and is also useful for administrative purposes. In the thesis, two improvements to the standard live migration algorithm are presented, delta compression and page transfer reordering. The improvements can reduce migration downtime, i.e., the time that the VM is unavailable, as well as the total migration time. Postcopy migration, where the VM is resumed on the destination before the memory content is transferred is also studied. Both userspace and in-kernel postcopy algorithms are evaluated in an in-depth study of live migration principles and performance.Efficient mapping of VMs onto PMs is a key problem for cloud providers as PM utilization directly impacts revenue. When services are accepted into a datacenter, a decision is made on which PM should host the service VMs. This thesis presents a general approach for service scheduling that allows for the same scheduling software to be used across multiple cloud architectures. A number of scheduling algorithms to optimize objectives like revenue or utilization are also studied. Finally, an approach for continuous datacenter consolidation is presented. As VM workloads fluctuate and server availability varies any initial mapping is bound to become suboptimal over time. The continuous datacenter consolidation approach adjusts this VM-to-PM mapping during operation based on combinations of management actions, like suspending/resuming PMs, live migrating VMs, and suspending/resuming VMs. Proof-of-concept software and a set of algorithms that allows cloud providers to continuously optimize their server resources are presented in the thesis.
34
Crawford, L. M. "A dynamic scheduling algorithm for open and programmable networks." Thesis, Queen's University Belfast, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.426801.
Full text
35
Haramabadi, Hassan Rashidi. "Dynamic scheduling of automated guided vehicles in container terminals." Thesis, University of Essex, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.425938.
Full text
36
Al, Behadili Mohanad Riyadh Saad. "Robust dynamic and stochastic scheduling in permutation flow shops." Thesis, University of Portsmouth, 2018. https://researchportal.port.ac.uk/portal/en/theses/robust-dynamic-and-stochastic-scheduling-in-permutation-flow-shops(fc525bc5-7626-4b6d-9cfc-976185526a5b).html.
Full textAbstract:
The Permutation Flow Shop Scheduling Problem (PFSP) is a fundamental problem underlying many operational challenges in the field of logistic and supply chain management. The PFSP is a well-known NP-hard problem whereby the processing sequence of the jobs is the same for all machines. The dynamic and stochastic PFSP arise in practice whenever a number of different types of disruptions or uncertainties interrupt the system. Such disruptions could lead to deviate the disrupted schedule from its initial plan. Thus, it is important to consider different solution methods including: an optimisation model that minimise different objectives that take into account stability and robustness, efficient rescheduling approach, and algorithms that can handle large size and complex dynamic and stochastic PFSP, under different uncertainties. These contributions can be described as follows: 1. Develop a multi-objective optimisation model to handle different uncertainties by minimising three objectives namely; utility, instability and robustness. 2. Propose the predictive-reactive approach to accommodate the unpredicted uncertainties. 3. Adapt the Particle Swarm Optimisation (PSO), the Iterated Greedy (IG) algorithm and the Biased Randomised IG algorithm (BRIG) to reschedule the PFSP at the reactive stage of the predictive-reactive approach. 4. Apply the Simulation-Optimisation (Sim-Opt) approach for the Stochastic PFSP (SPFSP)under different uncertainties. This approach consists of two methods, which are: the novel approach that hybridise the Monte Carlo Simulation (MCS) with the PSO (Sim-PSO)and the Monte Carlo Simulation (MCS) with the BRIG (Sim-BRIG). The main aim of using the multi-objective optimisation model with different solution methods is to minimise the instability and keep the solution as robust as possible. This is to handle uncertainty as well as to optimise against any worst instances that might arise due to data uncertainty. Several approaches have been proposed for the PFSP under dynamic and stochastic environments, where the PSO, IG and BRIG are developed for the PFSP under different uncertainties. Also, hybridised the PSO and the BRIG algorithms with the MCS to deal with SPFSP under different uncertainties. In our version of the approach, the first one is a PSO algorithm step after which an MCS is incorporated in order to improve the final solutions of problem. The second approach proposed the hybridisation of the BRIG algorithm with MCS to be applied on the SPFSP under different uncertainties. The developed multi-objective model and proposed approaches are tested on benchmark instances proposed by (Katragjini et al.,2013) in order to evaluate the effectiveness of the proposed methodologies, this benchmark is based on the well-known instances of Taillard’s (Taillard, 1993). The computational results showed that the proposed methodologies are capable of finding good solutions for the PFSP under different uncertainties and that they are robust for the dynamic and stochastic nature of the problem instances. We computed the best solutions and found that they could be highly promising in minimising the total completion time. The results obtained are quite competitive when compared to the other models found in the literature. Also, some proposed algorithms show better performance when compared to others.
37
Tan, Ceryen (Ceryen C. ). "A hybrid static/dynamic approach to scheduling stream programs." Thesis, Massachusetts Institute of Technology, 2009. http://hdl.handle.net/1721.1/61291.
Full textAbstract:
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.Cataloged from PDF version of thesis.
Includes bibliographical references (p. 95-97).
Streaming languages such as Streamlt are often utilized to write stream programs that execute on multicore processors. Stream programs consist of actors that operate on streams of data. To execute on multiple cores, actors are scheduled for parallel execution while satisfying data dependencies between actors. In StreamIt, the compiler analyzes data dependencies between actors at compile-time and generates a static schedule that determines where and when actors are executed on the available cores. Statically scheduling actors onto cores results in no scheduling overhead at runtime and allows for sophisticated compile-time scheduling optimizations. Unfortunately, static scheduling has a number of severe limitations. The generated static schedule is inflexible and cannot be adapted to run-time conditions, such as cores that are unexpectedly unavailable. Static scheduling may also incorrectly load-balance cores due to inaccurate static work estimates. This thesis contributes a hybrid static/dynamic scheduling approach that attempts to address the limitations of static scheduling. Dynamic load-balancing is utilized to adjust the static schedule to run-time conditions and to correct load imbalances that might exist after static scheduling. Dynamic load-balancing is designed to add very little run-time overhead.
by Ceryen Tan.
M.Eng.
38
Jiang, Hai 1979. "Dynamic airline scheduling and robust airline schedule de-peaking." Thesis, Massachusetts Institute of Technology, 2006. http://hdl.handle.net/1721.1/37976.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering, 2006.Includes bibliographical references (p. 151-156).
Demand stochasticity is a major challenge for the airlines in their quest to produce profit maximizing schedules. Even with an optimized schedule, many flights have empty seats at departure, while others suffer a lack of seats to accommodate passengers who desire to travel. Recognizing that demand forecast quality for a particular departure date improves as the date comes close, we tackle this challenge by developing a dynamic scheduling approach that re-optimizes elements of the flight schedule during the passenger booking period. The goal is to match capacity to demand, given the many operational constraints that restrict possible assignments. We introduce flight re-timing as a dynamic scheduling mechanism and develop a re-optimization model that combines both flight re-timing and flight re-fleeting. Our re-optimization approach, re-designing the flight schedule at regular intervals, utilizes information from both revealed booking data and improved forecasts available at later re-optimizations. Experiments are conducted using data from a major U.S. airline. We demonstrate that significant potential profitability improvements are achievable using this approach.
(cont.) We complement this dynamic re-optimization approach with models and algorithms to de-peak existing hub-and-spoke flight schedules so as to maximize future dynamic scheduling capabilities. In our robust de-peaking approach, we begin by solving a basic de-peaking model to provide a basis for comparison of the robust de-peaked schedule we later generate. We then present our robust de-peaking model to produce a schedule that maximizes the weighted sum of potentially connecting itineraries and attains at least the same profitability as the schedule produced by the basic de-peaking model. We provide several reformulations of the robust de-peaking model and analyze their properties. To address the tractability issue, we construct a restricted model through an approximate treatment of the profitability requirement. The restricted model is solved by a decomposition based solution approach involving a variable reduction technique and a new form of column generation. We demonstrate, through experiments using data from a major U.S. airline, that the schedule generated by our robust de-peaking approach achieves improved profitability.
by Hai Jiang.
Ph.D.
39
Vlk, Marek. "Dynamic Scheduling." Master's thesis, 2014. http://www.nusl.cz/ntk/nusl-336598.
Full textAbstract:
One of the problems of real-life production scheduling is dynamics of manufacturing environments with new production demands and breaking machines during the schedule execution. Simple rescheduling from scratch in response to unexpected events occurring on the shop floor may require excessive computation time. Moreover, the recovered schedule may be prohibitively deviated from the ongoing schedule. This thesis reviews existing approaches in the field of dynamic scheduling and proposes techniques how to modify a schedule to accommodate disturbances such as resource failure, hot order arrival or order cancellation. The importance is put on the speed of suggested procedures as well as on a minimum modification from the original schedule. The scheduling model is motivated by the FlowOpt project, which is based on the Temporal Networks with Alternatives. The algorithms are written in the C# language.
40
Litwin, Marek Szymon. "Dynamic household activity scheduling processes." 2005. http://link.library.utoronto.ca/eir/EIRdetail.cfm?Resources__ID=370910&T=F.
Full text
41
Hung, Lin Chiang, and 林健鴻. "Dynamic Demand Lot Size Scheduling." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/26467415732768653122.
Full textAbstract:
碩士國立清華大學
工業工程與工程管理學系
90
The goal of a Just-in-time production system is to minimize the inventory cost. However, it is difficulty to make lot size decisions under a dynamic demand environment, whose demands vary with time. To achieve the goal of JIT, this study considers multi-machine dynamic-demand capacitated lot size scheduling problem with the objective of minimizing the inventory cost. We divide the overall production decision into two kinds of decisions: “discrete decisions” and “continuous decisions”. Discrete decisions include the product type for each of the production runs, the beginning period of each run, the ending period of each run, and product on the machines. The continuous decisions suggest the precise beginning epoch and ending epoch of each run. We will utilize tabu search and simulated annealing to determine the discrete decisions. Then, by using the discrete decisions, a mathematical programming model, proposed herein, will be used to solve the continuous decisions. The above procedure will be iterated to solve our problem. Experimental results indicate that such a methodology can effectively obtain a production schedule for each type of product to reduce total inventory costs and eliminate backorders. Experimental designs and statistical methods are used to evaluate and analyze the performance of tabu search and simulated annealing. As a result, tabu search performs significantly better than simulated annealing. Therefore, we suggest that tabu search is utilized to search for discrete decisions.
42
XIE, HONG-SHENG, and 謝弘昇. "Dynamic task scheduling in NIXE." Thesis, 1992. http://ndltd.ncl.edu.tw/handle/07727249371613531141.
Full text
43
Reddy, K. Rama Bhupal, Na Xie, and Velusamy Subramaniam. "Dynamic Scheduling of Flexible Manufacturing Systems." 2003. http://hdl.handle.net/1721.1/3903.
Full textAbstract:
To date, group scheduling research has primarily focused on examining the performance of different group heuristics under various experimental conditions. However, the dynamic selection of group heuristics has not received sufficient attention from researchers. The objective of this paper is to demonstrate a mechanism for the dynamic selection of group heuristics from several candidate alternatives by exploiting real time information from the Flexible Manufacturing System (FMS). In this regard, two tools, viz., Analytic Hierarchy Process (AHP) and Simple Multi-Attribute Rating Technique Exploiting Ranks (SMARTER), are used to develop models for part type and family selection. The experimental results indicate that the performance of the proposed models are better than the common group scheduling heuristics under varied experimental conditions.Singapore-MIT Alliance (SMA)
44
Chang, Yu-Jen, and 張育仁. "A Self-Adaptive Dynamic Scheduling Methodology." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/66420940094096685349.
Full textAbstract:
博士國立交通大學
工業工程與管理系
88
Scheduling plays an important role in a complex and dynamic manufacturing environment. To enhance scheduling performance, a systematic approach that effectively integrates order release and dispatching decisions is necessary. In addition, to incorporate with planners'' or shop supervisors'' knowledge and experiences, vague information and events of a manufacturing system can be efficiently managed. Besides, operation sequence of bottleneck is the core of scheduling activities and the primary key of improving system performance. In this study, a self-adaptive dynamic scheduling methodology focusing on the above intentioned characteristics is proposed. This methodology uses a modified Tabu search method to optimize the operation sequence of bottleneck. Order release and dispatching decisions are made, thereafter, according to scheduling information of bottleneck. Fuzzy theory incorporated with genetic algorithm is applied to construct a knowledge base with planners'' knowledge and experiences which can improve the proceeding shop''s scheduling decisions. Although the proposed self-adaptive dynamic scheduling methodology still has some unsolved problems, simulation results show that both knowledge base and bottleneck schedule can be used to effectively improve performance of manufacturing systems.
45
Wu, Chung-Ming, and 吳仲銘. "A Study on Dynamic List Scheduling." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/33799137814752646741.
Full textAbstract:
碩士國立臺灣科技大學
資訊管理系
101
Until now, task scheduling problem has been extensively studied, but the studies about processors with different capabilities are limited. In the studies about processors with different capabilities, most of them are using static methods, such as Scheduling workflow applications on processors with Different Capabilities (SDC) algorithm and Duplication-based scheduling algorithm with Different Capabilities (DDC) algorithm. The schedule lists of static methods cannot be changed, we may lose the opportunity of finding the better schedule lists. Therefore, in this thesis, we present a new list scheduling algorithm, called Dynamic List scheduling algorithm with Different Capabilities (DLDC). In DLDC algorithm, we use the concepts of Heterogeneous Earliest-Finish-Time (HEFT) algorithm and Longest Dynamic Critical Path (LDCP) algorithm to obtain better scheduling list. And, in the select processor phase, we consider whether or not successors can be scheduled in the same processor, and then a suitable processor will be chose. Finally, experimental results reveal that DLDC algorithm outperforms those of the others.
46
CHIANG, TE-WEI, and 蔣德威. "Intelligent Scheduling System for Dynamic Environment." Thesis, 1997. http://ndltd.ncl.edu.tw/handle/91898786350981778644.
Full textAbstract:
博士國立臺灣大學
電機工程學系
85
This dissertation investigates the job-shop scheduling and railway scheduling problems. The elements of a job shop scheduling problem consists of a set of machines and a collection of jobs to be scheduled. Operation precedence constraints give the order in which the operations that comprise each job must be processed. The job shop scheduling problem thus can be defined as the allocation of machines over time to perform a collection of jobs to minimize/maximize a performance measure while satisfying the operation precedence constraints, machine capacity constraints, processing time requirements, and ready time requirements. On the other hand, in railway systems, the timetable containing the arrival/ departure times and the track assignments of all trains at each station is the most essential schedule for day-to-day operations. Similar to conventional job-shop scheduling problem, the railway scheduling problem is the decision of the arrival/departure times and the assigning of tracks to all trains while minimizing a particular objective function and satisfying some specified constraints. The main differences between job-shop scheduling problems and railway scheduling problems are the constraints that must be satisfied. In this dissertation, we propose an approach for general scheduling problems based on iterative repair. This approach starts with a heuristically generated schedule which may be infeasible, then applies local search techniques to generate a good conflict- free schedule. Since cycles may exist among a sequence of repair operations during the repair process, we also propose a cycle detection and resolution scheme in this dissertation. This approach is not only suitable for static schedule generation but also for dynamic rescheduling. Furthermore, this approach is very flexible, it can be adapted to different scheduling applications. Experimental results show that the proposed system can not only generate a good feasible static schedule but also react to the dynamic and stochastic environment in an efficient manner.
47
Patrick, Jonathan. "Dynamic patient scheduling for a diagnostic resource." Thesis, 2006. http://hdl.handle.net/2429/18620.
Full textAbstract:
We take an in-depth look at the scheduling of patients for a diagnostic resource. Our aim is to schedule patients in order to maintain reasonable waiting times for minimal cost. We assume a fixed capacity with stochastic demand coming from multiple priority classes. We further assume that it is the lower priority patients that must be booked first, therefore requiring the resource manager to implement a booking policy to assure room for later arriving higher priority patients. If too much capacity is reserved for higher priority patients then there will inevitably be unused capacity resulting in longer waiting times than might otherwise be the case. If not enough capacity is reserved then higher priority patients will have to be served through overtime or forced to wait longer than recommended. We begin, in Chapter 1, with an international overview of efforts to reduce waiting times. Chapter 2 proposes a scheduling policy assuming only two priority classes and a fixed limit on expected overtime. The higher priority class are inpatients who must be served the day the demand for a scan is placed. The lower priority class consists of outpatients who may be booked weeks in advance. We present a model that gives the optimal reservation policy and examine the benefit of introducing some flexibility into the higher priority (inpatient) class. Chapter 3 then restricts the modeling to outpatients where demand is divided into multiple priority classes. We present a Markov Decision Process that we solve through approximate dynamic programming in order to derive an approximately optimal booking policy that maintains reasonable waiting times for minimal cost. Chapter 4 presents some strong theoretical results as to the nature of the optimal policy from chapter 3 as well as providing bounds on the "deviation from optimality" associated with our approximation. Chapter 5 then adds inpatients to the model in chapter 3 and compares the results of the full model to those given in chapter 2. Finally, we conclude with possible enhancements to the model and policy insights for the resource manager.Business, Sauder School of
Graduate
48
"Integrated and dynamic vehicle and crew scheduling." [Amsterdam : Rotterdam : Thela Thesis] ; Erasmus University [Host], 2004. http://hdl.handle.net/1765/6779.
Full text
49
Chang, Hung-Wei, and 張宏瑋. "DYNAMIC CRITERIA EVALUATION FOR TOUR SCHEDULING OPTIMIZATION." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/px7hbx.
Full textAbstract:
碩士大同大學
資訊經營學系(所)
95
People always make decisions in their daily life. However, the most problems are easy to solve. So it can make a property decision. But the more complex problems, the more criteria we have to care about. The decisions become more and more difficult. It forms the Multi-Criteria Decision Making Problems (MCDM). The criteria may be altered by the time. Owing to this reason, it must consider the viewpoint of time into the decision-making process. This research is based on the dynamic multi-criteria decision-making concept. Adopting co-evolutionary genetic algorithms to solve decision-making problems, it combines the general genetic algorithm with co-evolutionary mechanism to simulate the human thinking to provide the solutions. This paper uses northern Taiwan traveling scheduling for demonstration, and make use of the advantage of genetic algorithms (implicated parallel processing ability and the auto-adjusting capacity) to modify the drawback of traditional methods. After making a serious of experiment to simulate the tour planning that can test the suitable of using co-evolutionary genetic algorithms. This paper test some tour planning problems and it can find some advantages of co-evolutionary mode. Such as it can not only simulate the thought how people to figure out the problem but also accelerate to find the satisfied answers. So this research provides some reference on decision system developing and design in the future.
50
Li, Hsiao-Chien, and 李曉茜. "Dynamic User Equipment Scheduling in Cloud-RAN." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/rm2zyt.
Full textAbstract:
碩士國立交通大學
電信工程研究所
103
In this thesis, we consider the dynamic user scheduling in each time slot based on maximizing the minimum rate among all the selected users such that the scheduling time is as short as possible in a Cloud-RAN with multiple single antenna RRHs and multiple single antenna MUs framework. Without doing beamforming, the framework becomes a point-to-point wireless network, where a MU treats the interference from other RRHs, not its serving RRH, as noise. Then we need to choose MUs and decide the pairing relationship between RRHs and UE appropriately such that the max-min SINR is as high as possible. And we propose two heuristic ways to schedule. With doing beamforming, although all the MUs can be served simultaneous in a time slot, some MUs with bad channel conditions may suppress the total throughput and may be a burden to shorter scheduling time. Hence, we somehow abandon the burden in a time slot for better total throughput. It brings to the shorter scheduling time at most of time.