<p>Mitrionics is a company based in Lund, Sweden. They develop a platform for FPGA-based acceleration, the platform includes a virtual processor, the Mitrion Virtual Processor, that can be custom built to fit the application that is to be accelerated. The purpose of this thesis is to investigate the possible benefits of using a centralized scheduler for the Mitrion Virtual Processor instead of the current solution which is a distributed scheduler. A centralized scheduler has been implemented and evaluated using a set of benchmark applications. It has been found that the centralized scheduler can decrease the number of registers used to implement the Mitrion Virtual Processor on an FPGA. The size of the decrease depends on the application, and certain applications are more suitable than others. It has also been found that the introduction of a centralized scheduler makes it more difficult for the place and route tool to fit a design on the FPGA resulting in failed timing constraints for the largest benchmark application.</p> / <p>Mitrionics är ett företag i Lund. De utvecklar en platform för FPGA-baserad acceleration av applikationer. Platformen innehåller bland annat en virtuell processor, Mitrion Virtual Processor, vilken kan specialanpassas till applikationen som ska accelereras. Syftet med detta arbete är att implementera en centraliserad schedulerare för Mitrion Virtual Processor och utvärdera vilka möjliga fördelar det kan finnas jämfört med att använda den nuvarande lösningen vilket är en distribuerad skedulerare. En centraliserad skedulerare har implementerats och utvärderas genom att avända en uppsättning testapplikationer. Det har funnits att användandet av en centraliserad skedulerare kan minska antalet register som behövs för att implementera Mitrion Virtual Processor på en FPGA. Vidare har det funnits att storleken på minskningen beror på applikationen och att vissa applikationer lämpar sig bättre än andra. Det har även visat sig att processen att placera logik på FPGAn blir svårare om man använder en centraliserad skedulerare, detta har resulterat i att vissa timing krav inte har mötts när den största testapplikation har syntetiserats.</p>

An evaluation of scheduling heuristics for non-identical parallel processors was performed. There has been limited research that has focused on scheduling of parallel processors. This research generalizes the results from prior work in this area and examines complex scheduling rules in terms of flow time, tardiness, and proportion of tardy jobs. Several factors affecting the system were examined and scheduling heuristics were developed. These heuristics combine job allocation and job sequencing functions. A number of system features were considered in developing these heuristics, including setup times and processor utilization spread. The heuristics used different sequencing rules for job sequencing including random, Shortest Process Time (SPT), Earlier Due Date (EDD), and Smaller Slack (SS). A simulation model was developed and executed to study the system. The results of the study show that the effect of the number of machines, the number of products, system loading, and setup times were significant for all performance measures. The effect of number of machines was also found to be significant on flow time and tardiness. Several two-factor interactions were identified as significant for flow time and tardiness. The SPT-based heuristic resulted in minimum job flow times. For tardiness and proportion of tardy jobs, the EDD-based heuristic gave the best results. Based on these conclusions, a "Hybrid" heuristic that combined SPT and EDD considerations was developed to provide tradeoff between flow time and due date based measures. / Graduation date: 1995

We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on a time-indexed formulation, the other on a completiontime formulation. We show their equivalence by proving that a O(n log n) greedy algorithm leads to optimal solutions to both relaxations. The proof relies on the notion of mean busy times of jobs, a concept which enhances our understanding of these LP relaxations. Based on the greedy solution, we describe two simple randomized approximation algorithms, which are guaranteed to deliver feasible schedules with expected objective value within factors of 1.7451 and 1.6853, respectively, of the optimum. They are based on the concept of common and independent a-points, respectively. The analysis implies in particular that the worst-case relative error of the LP relaxations is at most 1.6853, and we provide instances showing that it is at least e/(e - 1) 1.5819. Both algorithms may be derandomized, their deterministic versions running in O(n2 ) time. The randomized algorithms also apply to the on-line setting, in which jobs arrive dynamically over time and one must decide which job to process without knowledge of jobs that will be released afterwards.

We present an optimal methodology for synchronized scheduling of production assembly with air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain (CESC). This problem was motivated by a major PC manufacturer in consumer electronics industry, where it is required to schedule the delivery requirements to meet the customer needs in different parts of South East Asia. The overall problem is decomposed into two sub-problems which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as a Linear Programming Problem with earliness tardiness penalties for job orders. For the assembly scheduling problem, it is basically required to sequence the job orders on the assembly stations to minimize their waiting times before they are shipped by flights to their destinations. Hence the second sub-problem is modelled as a scheduling problem with earliness penalties. The earliness penalties are assumed to be independent of the job orders. / Singapore-MIT Alliance (SMA)

We address the problem of jointly determining shipment planning and scheduling decisions with the presence of multiple shipment modes. We consider long lead time, less expensive sea shipment mode, and short lead time but expensive air shipment modes. Existing research on multiple shipment modes largely address the short term scheduling decisions only. Motivated by an industrial problem where planning decisions are independent of the scheduling decisions, we investigate the benefits of integrating the two sets of decisions. We develop sequence of mathematical models to address the planning and scheduling decisions. Preliminary computational results indicate improved performance of the integrated approach over some of the existing policies used in real-life situations. / Singapore-MIT Alliance (SMA)

Thesis (Ph. D.)--Carnegie-Mellon University, 1983. / Bibliography: p. 147-153.

Thesis (Ph. D.)--Ohio State University, 2006. / Title from first page of PDF file. Includes bibliographical references (p. 148-154).

Thesis (M. Phil.)--University of Hong Kong, 2006. / Title proper from title frame. Also available in printed format.

Thesis (M. Phil.)--University of Hong Kong, 2006. / Title proper from title frame. Also available in printed format.

The central thesis of this dissertation is that insight from queueing analysis can effectively guide standard (combinatorial) scheduling algorithms in dynamic environments. Scheduling is generally concerned with complex combinatorial decisions for static problems, whereas queueing theory simplifies the combinatorics and focuses on dynamic systems. We examine a queueing network with flexible servers under queueing and scheduling techniques. Based on the strengths of queueing analysis and scheduling, we develop a hybrid model that guides scheduling with results from the queueing model. In order to include setup times, we create a logic-based Benders decomposition model for a static representation of the queueing network. Our model is able to find optimal schedules up to 5 orders of magnitude faster than the only other model in the literature. A hybrid model is then developed for the dynamic problem and shown to achieve the best mean flow time while also guaranteeing maximal capacity.