This dissertation explores mathematical programming optimization models and algorithms for routing and scheduling ships in a maritime transportation system. Literature surveyed on seaborne transportation systems indicates that there is a scarcity of research on ship routing and scheduling problems. The complexity and the overwhelming size of a typical ship routing and scheduling problem are the primary reasons that have resulted in the scarcity of research in this area. The principal thrust of this research effort is focused at the Kuwait Petroleum Corporation (KPC) Problem. This problem is of great economic significance to the State of Kuwait, whose economy has been traditionally dominated to a large extent by the oil sector. Any enhancement in the existing ad-hoc scheduling procedure has the potential for significant savings. A mixed-integer programming model for the KPC problem is constructed in this dissertation. The resulting mathematical formulation is rather complex to solve due to (1) the overwhelming problem size for a typical demand contract scenario, (2) the integrality conditions, and (3) the structural diversity in the constraints. Accordingly, attempting to solve this formulation for a typical demand contract scenario without resorting to any aggregation or partitioning schemes is theoretically complex and computationally intractable. Motivated by the complexity of the above model, an aggregate model that retains the principal features of the KPC problem is formulated. This model is computationally far more tractable than the initial model, and consequently, it is utilized to construct a good quality heuristic solution for the KPC problem. The initial formulation is solved using CPLEX 4.0 mixed integer programming capabilities for a number of relatively small-sized test cases, and pertinent results and computational difficulties are reported. The aggregate formulation is solved using CPLEX 4.0 MIP in concert with specialized rolling horizon solution algorithms and related results are reported. The rolling horizon solution algorithms enabled us to handle practical sized problems that could not be handled by directly solving the aggregate problem. The performance of the rolling horizon algorithms may be enhanced by increasing the physical memory, and consequently, better solutions can be extracted. The potential saving and usefulness of this model in negotiation and planning purposes strongly justifies the acquisition of more computing power to tackle practical sized test problems. An ad-hoc scheduling procedure that is intended to simulate the current KPC scheduling practice is presented in this dissertation. It is shown that results obtained via the proposed rolling horizon algorithms are at least as good, and often substantially better than, results obtained via this ad-hoc procedure. / Ph. D.

As 4/4 block scheduling was implemented in North Carolina, many public schools offered staff development to help teachers make the transition from a six- or seven- period school schedule, but little is known about the staff development provided. The purposes of this study were to determine the Stages of Concern of North Carolina public school teachers related to 4/4 block scheduling, their perceived professional development needs, and the relationships among their Stages of Concern, professional development needs, and selected characteristics. By calling each school district's central office, the researcher determined that 248 North Carolina high schools had implemented 4/4 block scheduling as of fall 1998. A list was developed of 73 schools that implemented block scheduling in the fall of 1996, 1997, and 1998. From this list, five schools were randomly selected for each of the three years, resulting in a sample of 15 schools. At each school, five teachers were selected from each of three teaching areas: academic, workforce development, and special subjects. Thus, of the1086 teachers employed at the 15 participating schools, 225 teachers were included in the sample. The questionnaire for this study contained three parts: (a) the Hall and Loucks (1979) Stages of Concern questionnaire, (b) a professional development needs section, and (c) a teacher characteristics section. Results of the study indicated that the teachers were concerned about the success of students in the classroom and the impact of 4/4 block scheduling on their students. Consequence was the peak Stage of Concern for the largest percentage of responders, and collaboration was the peak for the second-largest percentage. Teachers with less experience had higher informational concerns than their peers with more teaching experience. On four of the nine professional development needs, more recent adopters of 4/4 block scheduling indicated significantly less need for professional development than those whose schools adopted this schedule in previous years. Thus, as teachers became more experienced with 4/4 block scheduling, they may have had problems that were unforeseen when this schedule was initially adopted. Implications for practice and further research based on the results of the study were suggested. / Ph. D.

Scheduling is one of the most important issues in the planning of manufacturing systems. This research focuses on solving the test scheduling problem which arises in semiconductor manufacturing environment. Semiconductor wafer devices undergo a series of test processes conducted on computer-controlled test stations at various temperatures. A test process consists of both setup operations and processing operations on the test stations. The test operations occur in a specified order on the wafer devices, resulting in precedence constraints for the schedule. Furthermore, the assignment of the wafer devices to test stations and the sequence in which they are processed affects the time required to finish the test operations, resulting in sequence dependent setup times. The goal of this research is to develop a realistic model of the semiconductor wafer test scheduling problem and provide heuristics for scheduling the precedence constrained test operations with sequence dependent setup times. A mathematical model is presented and two heuristics are developed to solve the scheduling problem with the objective of minimizing the makespan required to test all wafer devices on a set of test stations. The heuristic approaches generate a sorted list of wafer devices as a dispatching sequence and then schedule the wafer lots on test stations in order of appearance on the list. An experimental analysis and two case studies are presented to validate the proposed solution approaches. In the two case studies, the heuristics are applied to actual data from a semiconductor manufacturing facility. The results of the heuristic approaches are compared to the actual schedule executed in the manufacturing facility. For both the case studies, the proposed solution approaches decreased the makespan by 23-45% compared to the makespan of actual schedule executed in the manufacturing facility. The solution approach developed in this research can be integrated with the planning software of a semiconductor manufacturing facility to improve productivity. / Master of Science

The education spectrum includes many different modes of instruction or organizational models. The following are examples of organizational models available to school leaders: self-contained, departmentalized, team-teaching, collaboration, changing classes, and rotating classes. In this spectrum, the self-contained classroom and the departmentalized classroom are the most frequently used organizational models. The self-contained classroom involves one teacher instructing a group of students in all academic subjects. In contrast, the departmentalized classroom is a setting where educators teach in one area of specialization and students move from one classroom to another for instruction. When considering effective organizational models, it is imperative for administrators to pay attention not only to the quality and content of a lesson but also to the organizational structure in which the instruction is presented. This study included 94 schools using either a self-contained or a departmentalized classroom organization model. The purpose of the study was to identify the organizational model, either departmentalized or self-contained, that had a significant difference in measures of students' academic performance on reading and mathematics VSL pass rates for fourth graders in Region II of Virginia. Analysis of variance (ANOVA) was used to test the hypothesis and results revealed that there is no evidence of a significant difference between the two classroom organizational models on either reading or math VSL test pass rates for fourth graders. The findings suggest that no significant differences in reading and math VSL pass rates existed among schools with the two different classroom organizational models. Controlling for school size and the presence or absence of school Title I status (40% or more of its students come from families who qualify as low income under U.S. Census definitions) did not have an effect on the comparison related to fourth-grade general education students' pass rates on the 2009–2010 school year reading and math VSL pass rates. / Ed. D.

Research in job shop scheduling has concentrated on sequencing simple, single component jobs that require no coordination of multiple parts for assembly. However, since most jobs in reality involve some assembly work, scheduling multiple component jobs through an assembly shop, where both serial and parallel operations take place, represents a more realistic and practical problem. The scheduling environment for multiple component jobs in terms of routing, sequencing, and the pacing of common components may be quite complex, and, as such, requires special scheduling considerations. The purpose of this research is to evaluate scheduling policies for the production of assembled products in a job shop environment, termed "assembly shop". The specific scheduling policies examined include duedate assignment procedures, labor assignment procedures, and item sequencing rules. The sensitivity of these policies to product structure is also addressed. / Ph. D.

Within manufacturing systems, process planning and scheduling are two interrelated problems that are often treated independently. Process planning involves deciding which operations are required to produce a finished product and which resources will perform each operation. Scheduling involves deciding the sequence that operations should be processed by each resource, where process planning decisions are known a priori. Integrating process planning and scheduling offers significant opportunities to reduce bottlenecks and improve plant performance, particularly for complex job shops. This research is motivated by the coating and laminating (CandL) system of a film manufacturing facility, where more than 1,000 product types are regularly produced monthly. The CandL system can be described as a complex job shop with sequence dependent setups, operation re-entry, minimum and maximum wait time constraints, and a due date performance measure. In addition to the complex scheduling environment, products produced in the CandL system have multiple feasible process plans. The CandL system experiences significant issues with schedule generation and due date performance. Thus, an integrated process planning and scheduling approach is needed to address large scale industry problems. In this research, a novel proxy measure based local search (PBLS) approach is proposed to address the integrated process planning and scheduling for a complex job shop. PBLS uses a proxy measure in conjunction with local search procedures to adjust process planning decisions with the goal of reducing total tardiness. A new dispatching heuristic, OU-MW, is developed to generate feasible schedules for complex job shop scheduling problems with maximum wait time constraints. A regression based proxy approach, PBLS-R, and a neural network based proxy approach, PBLS-NN, are investigated. In each case, descriptive statistics about the active process plan set are used as independent variables in the model. The resulting proxy measure is used to evaluate the effect of process planning local search moves on the objective function sum of total tardiness. Using the proxy measure to guide a local search reduces the number of times a detailed schedule is generated reducing overall runtime. In summary, the proxy measure based local search approach involves the following stages: • Generate a set of feasible schedules for a set of jobs in a complex job shop. • Evaluate the parameters and results of the schedules to establish a proxy measure that will estimate the effect of process planning decisions on objective function performance. • Apply local search methods to improve upon feasible schedules. Both PBLS-R and PBLS-NN are integrated process planning and scheduling heuristics capable of addressing the challenges of the CandL problem. Both approaches show significant improvement in objective function performance when compared to local search guided by random walk. Finally, an optimal solution approach is applied to small data sets and the results are compared to those of PBLS-R and PBLS-NN. Although the proxy based local search approaches investigated do not guarantee optimality, they provide a significant improvement in computational time when compared to an optimal solution approach. The results suggest proxy based local search is an appealing approach for integrated process planning and scheduling in complex job shop environment where optimal solution approaches are not viable due to processing time. / Ph. D.

The recent trend of migrating legacy computer systems to a virtualized, cloud-based environment has expanded to real-time systems. Unfortunately, modern hypervisors have no mechanism in place to guarantee the real-time performance of applications running on virtual machines. Past solutions to this problem rely on either spatial or temporal resource partitioning, both of which under-utilize the processing capacity of the host system. Paravirtualized solutions in which the guest communicates its real-time needs have been proposed, but they cannot support legacy operating systems. This thesis demonstrates the shortcomings of resource partitioning using temporally-isolated servers, presents an alternative solution to the scheduling problem called the KairosVM Flattening Scheduling Algorithm, and provides an implementation of the algorithm based on Linux and KVM. The algorithm is analyzed theoretically and an exact schedulability test for the algorithm is derived. Simulations show that the algorithm can schedule more than 90% of all randomly generated tasksets with a utilization less than 0.95. In comparison to the state-of-the-art server based approach, the KairosVM Flattening Scheduling Algorithm is able to schedule more than 20 times more tasksets with utilization of 0.95. Experimental results demonstrate that the Linux-based implementation is able to match the deadline satisfaction ratio of a state-of-the-art server-based approach when the taskset is schedulable using the state-of-the-art approach. When tasksets are unschedulable, the implementation is able to increase the deadline satisfaction ratio of Vanilla KVM by up to 400%. Furthermore, unlike paravirtualized solutions, the implementation supports legacy systems through the use of introspection. / Master of Science

No

The practical applications of scheduling generally involve the optimization of more than one criterion. This thesis focuses on the bicriteria optimization problem of scheduling jobs on single and two machines. The optimization criteria that are considered are those of minimization of maximum tardiness and minimization of the total number of tardy jobs in the schedule. The former is considered as the primary criterion while the latter is considered as the secondary criterion. For the single machine problem, a search tree method is presented which is based on the implementation of some new dominance rules. Computational results presented show that the performance of this algorithm is better than that of an earlier work reported in the literature. For the two machine problem, a heuristic algorithm is developed to minimize maximum tardiness. Computational results are presented regarding the performance of this heuristic. A search tree method is developed for the optimization of the secondary criterion. This search tree method is similar to that for the single machine problem except that it does not use the dominance rules that were developed for the single machine case. Computational experience is presented for this algorithm. / Master of Science

Real-Time systems are defined not only by their logical correctness but also timeliness. Modern real-time systems, such as those controlling industrial plants or the flight controller on UAVs, are no longer isolated. The same computing resources are shared with a variety of other systems and software. Further, these systems are increasingly being connected and made available over the internet with the rise of Internet of Things and the need for automation. Many real-time systems contain sensitive code and data, which not only need to be kept confidential but also need protection against unauthorized access and modification. With the cheap availability of hardware supported Trusted Execution Environments (TEE) in modern day microprocessors, securing sensitive information has become easier and more robust. However, when applied to real-time systems, the overheads of using TEEs make scheduling untenable. However, this issue can be mitigated by judiciously utilizing TEEs and capturing TEE operation peculiarities to create better scheduling policies. This thesis provides a new task model and scheduling approach, Split-TEE task model and a scheduling approach ST-EDF. It also presents simulation results for 2 previously proposed approaches to scheduling TEEs, T-EDF and CT-RM. / Master of Science / Real-Time systems are computing systems that not only maintain the traditional purpose of any computer, i.e, to be logically correct, but also timeliness, i.e, guaranteeing an output in a given amount of time. While, traditionally, real-time systems were isolated to reduce interference which could affect the timeliness, modern real-time systems are being increasingly connected to the internet. Many real-time systems, especially those used for critical applications like industrial control or military equipment, contain sensitive code or data that must not be divulged to a third party or open to modification. In such cases, it is necessary to use methods to safeguard this information, regardless of the extra processing time/resource consumption (overheads) that it may add to the system. Modern hardware support Trusted Execution Environments (TEEs), a cheap, easy and robust mechanism to secure arbitrary pieces of code and data. To effectively use TEEs in a real-time system, the scheduling policy which decides which task to run at a given time instant, must be made aware of TEEs and must be modified to take as much advantage of TEE execution while mitigating the effect of its overheads on the timeliness guarantees of the system. This thesis presents an approach to schedule TEE augmented code and simulation results of two previously proposed approaches.