No description available.

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)

No description available.

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.

Scientific and engineering problems are often large, complex, irregular and data-parallel. The performance of many parallel applications is affected by factors such as irregular nature of the problem, the difference in processor characteristics and runtime loads, the non-uniform distribution of data, and the unpredictable system behavior. These factors give rise to load imbalance. In general, in order to achieve high performance, dynamic load balancing strategies are embedded into solution algorithms. Over time, a number of dynamic load balancing algorithms have been implemented into software tools and successfully used in scientific applications. However, most of these dynamic load balancing tools use an iterative static approach that does not address irregularities during the application execution, and the scheduling overhead incurred is high. During the last decade, a number of dynamic loop scheduling strategies have been proposed to address causes of load imbalance in scientific applications running in parallel and distributed environments. However, there is no single strategy that works well for all scientific applications, and it is up to the user to select the best strategy and integrate it into the application. In most applications using dynamic load balancing, the load balancing algorithm is directly embedded in the application, with close coupling between the data structures of the application and the load balancing algorithm. This typical approach leads to two disadvantages. First, the integration of each newly developed load balancing algorithm into the application needs to be performed from scratch. Second, it is unlikely that the user has incorporated the optimal load balancing algorithm into the application. Moreover, in a certain application (of various problem sizes and number of processors), it is difficult to assess in advance the advantage of incorporating one load balancing algorithm versus another. To overcome these drawbacks, there is a need for developing an application programming interface (API) for dynamic load balancing scientific applications using the recently developed dynamic loop scheduling algorithms. This thesis describes the design and development of such an API, called ProLAS, which is scalable, and independent of data structures of a host application. ProLAS performance is evaluated theoretically and experimentally (after being used in scientific applications). A qualitative and quantitative analysis of ProLAS is presented by comparing its performance with the state of the art technology in dynamic load balancing tools (e.g. CHARM++ library) for parallel applications. The analysis of the experimental results of using ProLAS in a few scientific aplications indicate that it consistently outperforms the existing technology in dynamic load balancing.

No description available.

The recent manufacturing environment is characterized as having diverse products due to mass customization, short production lead-time, and unstable customer demand. Today, the need for flexibility, quick responsiveness, and robustness to system uncertainties in production scheduling decisions has increased significantly. In traditional job shops, tooling is usually assumed as a fixed resource. However, when tooling resource is shared among different machines, a greater product variety, routing flexibility with a smaller tool inventory can be realized. Such a strategy is usually enabled by an automatic tool changing mechanism and tool delivery system to reduce the time for tooling setup, hence allows parts to be processed in small batches. In this research, a dynamic scheduling problem under flexible tooling resource constraints is studied. An integrated approach is proposed to allow two levels of hierarchical, dynamic decision making for job scheduling and tool flow control in Automated Manufacturing Systems. It decomposes the overall problem into a series of static sub-problems for each scheduling window, handles random disruptions by updating job ready time, completion time, and machine status on a rolling horizon basis, and considers the machine availability explicitly in generating schedules. Two types of manufacturing system models are used in simulation studies to test the effectiveness of the proposed dynamic scheduling approach. First, hypothetical models are generated using some generic shop flow structures (e.g. flexible flow shops, job shops, and single-stage systems) and configurations. They are tested to provide the empirical evidence about how well the proposed approach performs for the general automated manufacturing systems where parts have alternative routings. Second, a model based on a real industrial flexible manufacturing system was used to test the effectiveness of the proposed approach when machine types, part routing, tooling, and other production parameters closely mimic to the real flexible manufacturing operations. The study results show that the proposed scheduling approach significantly outperforms other dispatching heuristics, including Cost Over Time (COVERT), Apparent Tardiness Cost (ATC), and Bottleneck Dynamics (BD), on due-date related performance measures under both types of manufacturing systems models. It is also found that the performance difference between the proposed scheduling approach and other heuristics tend to become more significant when the number of machines is increased. The more operation steps a system has, the better the proposed method performs, relative to the other heuristics. This research also investigates in what conditions (e.g. the number of machines, the number of operation steps, and shop load conditions) the proposed approach works the best, and how the performance of this proposed approach changes when these conditions change. When tooling resource is shared, parts can be routed to machines that do not have all the required tools. This may result in higher routing flexibility. However, research work to date in sharing of tooling resources often places more emphasis on the real-time control and manipulation of tools, and pays less attention to the loading of machines and initial tool allocation at the planning stage. In this research, a machine-loading model with shared tools is proposed to maximize routing flexibility while maintaining minimum resident tools. The performance of the proposed loading heuristic is compared to that of a random loading method using hypothetically generated single stage system models. The study result indicates that better system performances can be obtained by taking into account the resident tooling ratio in assigning part types and allocating tools to machines at the initial planning stage. / Ph. D.

ABSTRACT Broadcasting data delivery is rapidly becoming the good choice for disseminating information to a massive user population in many new application areas where the client-to-server communication is limited. There are two different ways of data dissemination. One is called push-based that the data items are broadcasted periodically in the channels, another one is called pull-based that the client requests a piece of data on the uplink channel and the server responds by sending this piece of data to the client. In push-based, most of the previous researches assume that each mobile client needs only one data item. However, in many situations, a mobile client might need more than one data item. In pull-based, the data items were broadcasted dynamically. Most of the previous researches assume that the data items which requested by the clients are of the same size. However, the data items may of different sizes in reality. In this thesis, we propose Improved QDS Expansion Method (Improved-QEM) and Heuristic On-line Algorithm to overcome the above two weaknesses, respectively. The issue of scheduling the broadcast data for the situation that each client may access multiple data items can not be simply considered as multiple subissues. There have been two methods was proposed, Query Expansion Method (QEM) and Modified Query Expansion Methods (Modified-QEM). These two methods are heuristic-based algorithm and do not provide the optimal solution. To improve the performance, our Improved-QEM is an efficient scheduling for query-set-based broadcasting, which is integrated with Query Expansion Method (QEM) and mining association rules technique. The mining association rules can globally find the data item sets (large itemsets) which are requested by clients, frequently. From our simulation results, we show that, as compared to the local optimal approach in the previous methods, our Improved-QEM can construct the schedule with the smaller TQD than that constructed by QEM and Modified-QEM, where TQD is denotes Total Query Distance and is proportional to the average access time. The on-line (push-based) algorithms are easy to adapt to time varying demands for the data items, which uses some decision-making mechanism to determine which data item is to be broadcasted next. Hence, when the number of data items is huge, it is important to schedule broadcasting program such that, it can provide the small overall mean access time. Therefore, Vaidya and Hameed have proposed two on-line algorithms, On-line Algorithm and On-line with Bucketing Algorithm. The main disadvantage of On-line Algorithm is the heavy run-time overhead and the main disadvantage of On-line Algorithm with Bucketing is the poor performance of the overall mean access time. Therefore, we propose the heuristic on-line algorithm to solve these two problems. From our simulation results, we show that our heuristic algorithm provides the performance that closes to the overall mean access time and has with low run-time overhead.

The number and scope of data driven streaming applications is growing. Such streaming applications are promising targets for effectively utilizing multi-cores because of their inherent amenability to pipelined parallelism. While existing methods of orchestrating streaming programs on multi-cores have mostly been static, real-world applications show ample variations in execution time that may cause the achieved speedup and throughput to be sub-optimal. One of the principle challenges for moving towards dynamic pipeline balancing has been the lack of approaches that can predict upcoming dynamic variations in execution efficiently, well before they occur. In this thesis, we propose an automated dynamic execution behavior prediction approach based on compiler analysis that can be used to efficiently estimate the time to be spent in different pipeline stages for upcoming inputs. Our approach first uses dynamic taint analysis to automatically generate an input-based execution characterization of the streaming program, which identifies the key control points where variation in execution might occur with respect to the associated input elements. We then automatically generate a light-weight emulator from the program using this characterization that can predict the execution paths taken for new streaming inputs and provide execution time estimates and possible dynamic variations. The main challenge in devising such an approach is the essential trade-off between accuracy and overhead of dynamic analysis. We present experimental evidence that our technique can accurately and efficiently estimate dynamic execution behaviors for several benchmarks with a small error rate. We also showed that the error rate could be lowered with the trade-off of execution overhead by implementing a selective symbolic expression generation for each of the complex conditions of control-flow operations. Our experiments show that dynamic pipeline balancing using our predicted execution behavior can achieve considerably higher speedup and throughput along with more effective utilization of multi-cores than static balancing approaches.

No description available.