In this doctoral thesis, four questions related to computational geometry are considered. The first is an extremal combinatorics question regarding triangles with vertices taken from a set of n points in convex position. More precisely, two such triangles can exhibit eight distinct configurations and, for each subset of these configurations, we are interested in the asymptotics of how many triangles one can have while avoiding configurations in the subset (as a function of n). For most of these subsets, we answer this question optimally up to a logarithmic factor in the form of several Turán-type theorems. The answers for the remaining few were in turn tied to that of a long-standing open problem which appeared in the literature in the contexts of monotone matrices, tripod packing and 2-comparable sets. The second problem, called Line Segment Covering (LSC), is about covering the cells of an arrangement of line segments with these line segments, where a segment covers the cells it is incident to. Recently, a PTAS, an APX -hardness proof and a FPT algorithm for variants of this problem have been shown. This paper and a new slight generalization of one of its results is included as a chapter. The third problem has been posed in the Sixth Annual Workshop on Geometry and Graphs and concerns the design of road networks to minimize the maximum travel time between two point sets in the plane. Traveling outside the roads costs more time per unit of distance than traveling on the roads and the total length of the roads can not exceed a budget. When the point sets are the opposing sides of a unit square and the budget is at most √2, we were able to come up with a few network designs that cover all possible cases and are provably optimal. Furthermore, when both point sets are the boundary of a unit circle, we managed to disprove the natural conjecture that a concentric circle is an optimal design. Finally, we consider collision-avoiding schedules of unit-velocity axis-aligned trains departing and arriving from points in the integer lattice. We prove a few surprising results on the existence of constant upper bounds on the maximum delay that are independent of the train network. In particular, these upper bounds are shown to always exist in two dimensions and to exist in three dimensions for unit-length trains. We also showed computationally that, for several scenarios, these upper bounds are tight.

Although the construction industry has been evolving for centuries and researchers have been seeking innovative solutions for decades, diverse challenges still exist in making the construction process faster, safer, cheaper and more accurate. It is believed that Building Information Modeling (BIM) can lead to greater efficiency through the incremental collaboration. The data in BIM system is extremely useful and can be generated to optimize the project delivery processes. However, since BIM increases the project design cost and requires a big learning curve, project participants are concerned about the cost of project, which has hindered the adoption of BIM for the project delivery. This paper, using a case study, describes how BIM functions to help cut down costs, optimize schedule, and benefit the project participants. The analysis of project cost and time control focuses on life cycle. The recommendations for the future use of BIM are made generally.

Diploma thesis focuses on creation of scheduling system for production processes and labour within heat pump manufacturing line in Daikin Device Czech Republic, connected with modification of production and warehouse layout. First part analyzes products, assembly line and its current state of layout. Furthermore it deals with measurement and analysis of work performed by operatives. Proposal part describes layout changes, whereupon line balancing is processed for different production levels and finally comes creation of scheduling system itself.

Master of Engineering

<p>This report identifies the activities of the Peninsula Center (P.C.) located 1n Hampton, Virginia and defines the dynamic system that exists at this facility. It explains the functions and responsibilities of the personnel, and ultimately details the site's activities throughout the semester. This is done in an effort to illustrate the opportunity for improvements in efficiency and enhancement of system capabilities.</p> / Master of Science

Memoria para optar al título de Ingeniero Civil Industrial / La gestión en deportes es una creciente y muy productiva área para aplicaciones de Gestión de Operaciones. Dentro de una liga deportiva existen múltiples factores tanto económicos y logísticos que la transforman en un interesante elemento de estudio. Hasta la fecha, los investigadores de esta disciplina, conocida mundialmente como Sports Scheduling, se han centrado principalmente en resolver el problema de la programación de partidos o fixtures considerando diversas condiciones, que lo suelen convertir en un problema combinatorial de difícil solución con múltiples aproximaciones. Estas condiciones se refieren a conseguir mayores beneficios económicos tanto para los equipos participantes como para las entidades organizadoras, mayor equidad deportiva, espectáculos más seguros y torneos más atractivos para el público, entre otros objetivos. Por lo tanto, crear un torneo para una gran cantidad de equipos y muchas solicitudes se convierte en una tarea engorrosa, que dará como resultado una solución poco óptima si no se realiza de la manera adecuada. El presente Trabajo de Memoria tiene por objetivo diseñar un calendario deportivo para la Liga Metropolitana y V región de balonmano temporada 2019, organizado por la Federación Chilena de Balonmano, en las versiones Oro y Plata, categorías dama y varón. Para esto, se utilizan herramientas de modelamiento con programación entera. Esta se basa en restricciones, indicando cómo las variables se relacionan entre sí. Todas las variables del problema tienen un dominio finito y se selecciona un valor de su dominio finito para cada una de las variables, de tal manera que se cumplan todas las restricciones. Para encontrar el calendario que mejor se ajuste a las necesidades de los equipos y de la federación se modela como un problema de programación lineal. Se cuenta con información de los clubes pertenecientes a los torneos, además de sus preferencias y las condiciones impuestas por la federación chilena de balonmano que permitirán esclarecer las restricciones. Esto complementado con la función objetivo resultado de la detección de necesidades en el transcurso de la investigación. Los modelos utilizan entre 3 a 7 familias de variables binarias y alrededor de 30 restricciones cada uno. Si se intenta dar solución a estos problemas en un computador con 4 GB de memoria RAM y procesador Intel Core 2 Duo 2.20 GHz utilizando Gurobi con Python y como solver Simplex, no hay solución de más de 30 horas. Los 3 modelos planteados resuelven el problema principal, sin embargo, se opta por sugerir el último modelo que logra decidir sobre horarios y categorías por cada fecha, ya que es el que mejor se adapta a las necesidades del organizador y que vela por un mejor funcionamiento de una liga de carácter aficionado que se fusiona con otra región.

The distribution of tasks to a heterogeneous work force at libraries and other service institutions is a time consuming task for manual schedulers. In this thesis, we study the possibility of making the assignment using operations research techniques. The problem studied concerns seven days per week, five types of tasks, two types of staff qualifications and around 100 tasks per week to be assigned to the staff. Staff member satisfaction is also taken into account in the scheduling process. The main objective is to create an optimal ten week rotating schedule, in which the stand-in staff members are evenly distributed. Such a schedule is considered to be robust, since stand-in staff can replace the regular staff when there is unforseen absence. A mathematical model is formulated for the problem and is solved using the commercial solver CPLEX. We also present two different large neighbourhood search heuristic implementations for this problem. The first heuristic assigns complete week blocks to the staff members, while the second one distributes one task at a time. The latter heuristic works better than the former and achieves results comparable to those of the commercial solver. Our conclusion is that the second heuristic works better because it focuses on finding a good weekend distribution before creating the rest of the schedule. A conclusion from our work is that the weekend-worker constellation is the most significant degree of freedom in the problem.

This thesis focuses on two central classes of problems in discrete optimization: matching and scheduling. Matching problems lie at the intersection of different areas of mathematics, computer science, and economics. In two-sided markets, Gale and Shapley's model has been widely used and generalized to assign, e.g., students to schools and interns to hospitals. The goal is to find a matching that respects a certain concept of fairness called stability. This model has been generalized in many ways. Relaxing the stability condition to popularity allows to overcome one of the main drawbacks of stable matchings: the fact that two individuals (a blocking pair) can prevent the matching from being much larger. The first part of this thesis is devoted to understanding the complexity of various problems around popular matchings. We first investigate maximum weighted popular matching problems. In particular, we show various NP-hardness results, while on the other hand prove that a popular matching of maximum weight (if any) can be found in polynomial time if the input graph has bounded treewidth. We also investigate algorithmic questions on the relationship between popular, stable, and Pareto optimal matchings. The last part of the thesis deals with a combinatorial scheduling problem arising in cyber-security. Moving target defense strategies allow to mitigate cyber attacks. We analyze a strategic game, PLADD, which is an abstract model for these strategies.

Much effort today in the Internet research community isaimed at providing network services for applications that werenot under consideration when the Internet was originallydesigned. Nowadays the network has to support real-timecommunication services that allow clients to transportinformation with expectations on network performance in termsof loss rate, maximum end-to-end delay, and maximum delayjitter. Today there exist two quality of service (QoS)architecture for the Internet: The integrated services, whichis usually referred to as intserv, and the differentiatedservices referred to as diffserv. Although the intserv clearlydefines the quality levels for each of its three serviceclasses, the limited scalability of this QoS architecture is acontinuous topic for discussion among the researchers. Theanalysis of the tradeoffs of the two QoS architecturesmotivated us to design a new QoS architecture which will takethe strength of the existing approaches and will combine themin a simpler, efficient and more scalable manner. In this LicentiateThesis we introduce a guaranteed servicefor the Internet, which definition is similar to the one inintserv: The guaranteed service (GS) is a network servicerecommended for applications with firm requirements on qualityof end-to-end communication. The service should provide zeropacket loss in routers and tightly bound the end-to-end delay.The capacity for a GS connection should be explicitly reservedin every router along a path of a connection. However, incontrary to intserv the necessary quality level will beprovided without per-flow scheduling in the core routers, whichis the major drawback of the intserv architecture. We use thediffserv principle of dealing with aggregates in the corenetwork since this approach is proven to be scalable andefficient. The thesis considers two major building blocks of the newarchitecture: The packet scheduling and the signaling protocol.We have developed a special scheduling algorithm. Our formaland experimental analysis of its delay properties shows thatthe maximum end-to-end delay is acceptable for real-timecommunication. Moreover, our scheme provides a fair service tothe traffic of other service classes. In order to achieve thedesired QoS level, a sufficient amount of capacity should bereserved for the GS connections in all intermediate routersend-to-end. We have developed a both simple and robustsignaling protocol. The realization of our protocol shows thatrouters are able to process up to 700,000 signaling messagesper second without overloading the processor. / NR 20140805

The purpose of this study was to describe the current schedules employed, teaming practices, and curricula used by the middle-level schools in the Commonwealth of Virginia, and it was conducted through the use of descriptive statistics. A questionnaire was sent to experts in the area of middle school education for review and field-tested with practicing administrators in middle-level education. The questionnaire was revised and mailed to 237 principals of the public schools in Virginia which have at least three grade levels drawn from five, six, seven, or eight but not grade levels four or nine. Principals from 134 schools, 57 percent of middle schools in Virginia, returned the questionnaire. Data collected from these questionnaires were used to describe the types of schedules employed, teaming practices, and curricula utilized by the participating middle schools. The number of middle schools in Virginia has continued to grow since their reported existence in the 1970's and the Virginia Department of Education's emphasis on the use of middle school practices in 1986. In 1985, Jessie Charles Zedd reported that there were 110 middle schools in the state. By 1996, the Virginia Educational Directory listed 237 middle schools, a percentage gain of 46. An increased use of middle school flexible scheduling and interdisciplinary teaming has occurred since that study. Most of the middle-level schools that participated in this study were mid-sized schools with 501 to 1,000 students and housing grades six, seven, and eight. The majority of middle-level schools in the Commonwealth of Virginia was found to utilize interdisciplinary teaming and a core curriculum. Flexible scheduling is utilized in most middle schools at grades six and seven but traditional schedules are used more frequently at grade eight. The use of flexible scheduling and teaming decreases from the sixth grade to the eighth grade in middle schools in the Commonwealth of Virginia. Ability grouping was reportedly used in more than 75 percent of middle schools participating in the study. Students are required to take all core subjects in most middle-level schools in Virginia and are offered high school level classes even before the eighth grade. The emphasis on the importance of middle-level education continues to be stressed nationally as well as within the Commonwealth of Virginia. Middle-level practices such as flexible scheduling and interdisciplinary teaming have served as examples of effective practices being considered and utilized by high schools. Advocates, practitioners, administrators, and teachers of the middle-level schools need to continue their emphasis on effective middle-level programs and practices for the continued improvement and success of middle schools. Improvement in the use of flexible scheduling, interdisciplinary teaming, and fewer grouping practices should be a goal of many middle-level schools to become exemplary schools. Middle schools should have high expectations for all and make their programs accessible to all students. Recommendations and data reported from this study may be used as a resource by administrators and other interested practitioners to restructure their programs in order to better serve middle-level children. / Ed. D.