Search results for: Job shop scheduling problem

Authors: Amin Sahraeian

Abstract:

One of the criteria in production scheduling is Make Span, minimizing this criteria causes more efficiently use of the resources specially machinery and manpower. By assigning some budget to some of the operations the operation time of these activities reduces and affects the total completion time of all the operations (Make Span). In this paper this issue is practiced in parallel flow shops. At first we convert parallel flow shop to a network model and by using a linear programming approach it is identified in order to minimize make span (the completion time of the network) which activities (operations) are better to absorb the predetermined and limited budget. Minimizing the total completion time of all the activities in the network is equivalent to minimizing make span in production scheduling.

Keywords: parallel flow shop, make span, linear programming, budget

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1749

Authors: A. Shirzadeh Chaleshtari, Sh. Shadrokh

Abstract:

Renewable and non-renewable resource constraints have been vast studied in theoretical fields of project scheduling problems. However, although cumulative resources are widespread in practical cases, the literature on project scheduling problems subject to these resources is scant. So in order to study this type of resources more, in this paper we use the framework of a resource constrained project scheduling problem (RCPSP) with finish-start precedence relations between activities and subject to the cumulative resources in addition to the renewable resources. We develop a branch and bound algorithm for this problem customizing precedence tree algorithm of RCPSP. We perform extensive experimental analysis on the algorithm to check its effectiveness and performance for solving different instances of the problem in question.

Keywords: Resource constrained project scheduling problem, cumulative resources, branch and bound algorithm, precedence tree.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2872

Authors: Phruksaphanrat B.

Abstract:

This research proposes a preemptive fuzzy goal programming model for multi-objective multi-mode resource constrained project scheduling problem. The objectives of the problem are minimization of the total time and the total cost of the project. Objective in a multi-mode resource-constrained project scheduling problem is often a minimization of makespan. However, both time and cost should be considered at the same time with different level of important priorities. Moreover, all elements of cost functions in a project are not included in the conventional cost objective function. Incomplete total project cost causes an error in finding the project scheduling time. In this research, preemptive fuzzy goal programming is presented to solve the multi-objective multi-mode resource constrained project scheduling problem. It can find the compromise solution of the problem. Moreover, it is also flexible in adjusting to find a variety of alternative solutions. 

Keywords: Multi-mode resource constrained project scheduling problem, Fuzzy set, Goal programming, Preemptive fuzzy goal programming.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2731

Authors: Miloš Šeda

Abstract:

Resource-constrained project scheduling is an NPhard optimisation problem. There are many different heuristic strategies how to shift activities in time when resource requirements exceed their available amounts. These strategies are frequently based on priorities of activities. In this paper, we assume that a suitable heuristic has been chosen to decide which activities should be performed immediately and which should be postponed and investigate the resource-constrained project scheduling problem (RCPSP) from the implementation point of view. We propose an efficient routine that, instead of shifting the activities, extends their duration. It makes it possible to break down their duration into active and sleeping subintervals. Then we can apply the classical Critical Path Method that needs only polynomial running time. This algorithm can simply be adapted for multiproject scheduling with limited resources.

Keywords: Project management, resource-constrained scheduling, NP-hard problem, CPM, heuristic method.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1376

Authors: C. E. Nugraheni, L. Abednego

Abstract:

This paper is concerned with minimization of mean tardiness and flow time in a real single machine production scheduling problem. Two variants of genetic algorithm as metaheuristic are combined with hyper-heuristic approach are proposed to solve this problem. These methods are used to solve instances generated with real world data from a company. Encouraging results are reported.

Keywords: Hyper-heuristics, evolutionary algorithms, production scheduling.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2373

Authors: Shuangquan Liu, Jinwen Wang, Dada Wang

Abstract:

A case study of the generation scheduling optimization of the multi-hydroplants on the Yuan River Basin in China is reported in this paper. Concerning the uncertainty of the inflows, the long/mid-term generation scheduling (LMTGS) problem is solved by a stochastic model in which the inflows are considered as stochastic variables. For the short-term generation scheduling (STGS) problem, a constraint violation priority is defined in case not all constraints are satisfied. Provided the stage-wise separable condition and low dimensions, the hydroplant-based operational region schedules (HBORS) problem is solved by dynamic programming (DP). The coordination of LMTGS and STGS is presented as well. The feasibility and the effectiveness of the models and solution methods are verified by the numerical results.

Keywords: generation scheduling, multi-hydroplants, optimization.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1515

Authors: R.A.Mahdavinejad

Abstract:

In this paper, multi-processors job shop scheduling problems are solved by a heuristic algorithm based on the hybrid of priority dispatching rules according to an ant colony optimization algorithm. The objective function is to minimize the makespan, i.e. total completion time, in which a simultanous presence of various kinds of ferons is allowed. By using the suitable hybrid of priority dispatching rules, the process of finding the best solution will be improved. Ant colony optimization algorithm, not only promote the ability of this proposed algorithm, but also decreases the total working time because of decreasing in setup times and modifying the working production line. Thus, the similar work has the same production lines. Other advantage of this algorithm is that the similar machines (not the same) can be considered. So, these machines are able to process a job with different processing and setup times. According to this capability and from this algorithm evaluation point of view, a number of test problems are solved and the associated results are analyzed. The results show a significant decrease in throughput time. It also shows that, this algorithm is able to recognize the bottleneck machine and to schedule jobs in an efficient way.

Keywords: Job shops scheduling, Priority dispatching rules, Makespan, Hybrid heuristic algorithm.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1633

Authors: M. Haddadzade, M. R. Razfar, M. Farahnakian

Abstract:

Integration of process planning and scheduling functions is necessary to achieve superior overall system performance. This paper proposes a methodology for integration of process planning and scheduling for prismatic component that can be implemented in a company with existing departments. The developed model considers technological constraints whereas available time for machining in shop floor is the limiting factor to produce multiple process plan (MPP). It takes advantage of MPP while guarantied the fulfillment of the due dates via using overtime. This study has been proposed to determinate machining parameters, tools, machine and amount of over time within the minimum cost objective while overtime is considered for this. At last the illustration shows that the system performance is improved by as measured by cost and compatible with due date.

Keywords: Due date, Integration, Multiple process plan, Process planning, Scheduling.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1610

Authors: Zaki Ahmad Khan, Jamshed Siddiqui, Abdus Samad

Abstract:

The Scheduling and mapping of tasks on a set of processors is considered as a critical problem in parallel and distributed computing system. This paper deals with the problem of dynamic scheduling on a special type of multiprocessor architecture known as Linear Crossed Cube (LCQ) network. This proposed multiprocessor is a hybrid network which combines the features of both linear types of architectures as well as cube based architectures. Two standard dynamic scheduling schemes namely Minimum Distance Scheduling (MDS) and Two Round Scheduling (TRS) schemes are implemented on the LCQ network. Parallel tasks are mapped and the imbalance of load is evaluated on different set of processors in LCQ network. The simulations results are evaluated and effort is made by means of through analysis of the results to obtain the best solution for the given network in term of load imbalance left and execution time. The other performance matrices like speedup and efficiency are also evaluated with the given dynamic algorithms.

Keywords: Dynamic algorithm, Load imbalance, Mapping, Task scheduling.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1981

Authors: Farzad Abtahi, Sahar Khanmohamadi, Bahram Sadeghi Bigham

Abstract:

Wireless channels are characterized by more serious bursty and location-dependent errors. Many packet scheduling algorithms have been proposed for wireless networks to guarantee fairness and delay bounds. However, most existing schemes do not consider the difference of traffic natures among packet flows. This will cause the delay-weight coupling problem. In particular, serious queuing delays may be incurred for real-time flows. In this paper, it is proposed a scheduling algorithm that takes traffic types of flows into consideration when scheduling packets and also it is provided scheduling flexibility by trading off video quality to meet the playback deadline.

Keywords: Data communication, Real-time, Scheduling, Video transport.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1440

Authors: Farhad Kolahan, Vahid Kayvanfar

Abstract:

In this paper we address a multi-objective scheduling problem for unrelated parallel machines. In unrelated parallel systems, the processing cost/time of a given job on different machines may vary. The objective of scheduling is to simultaneously determine the job-machine assignment and job sequencing on each machine. In such a way the total cost of the schedule is minimized. The cost function consists of three components, namely; machining cost, earliness/tardiness penalties and makespan related cost. Such scheduling problem is combinatorial in nature. Therefore, a Simulated Annealing approach is employed to provide good solutions within reasonable computational times. Computational results show that the proposed approach can efficiently solve such complicated problems.

Keywords: Makespan, Parallel machines, Scheduling, Simulated Annealing

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1606

Authors: Viraj Tyagi, Ajai Jain, P. K. Jain, Aarushi Jain

Abstract:

This paper presents a genetic algorithm based loading methodology for a capacity constrained job-shop with the consideration of alternative process plans for each part to be produced. Performance analysis of the proposed methodology is carried out for two case studies by considering two different manufacturing scenarios. Results obtained indicate that the methodology is quite effective in improving the shop load balance, and hence, it can be included in the frameworks of manufacturing planning systems of job-shop oriented industries.

Keywords: Manufacturing planning, loading, genetic algorithm, Job-Shop

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1462

Authors: Christian Meinecke, Bernd Scholz-Reiter

Abstract:

The integrated problem of production and distribution scheduling is relevant in many industrial applications. Thus, many heuristics to solve this integrated problem have been developed in the last decade. Most of these heuristics use a sequential working principal or a single decomposition and integration approach to separate and solve subproblems. A heuristic using a multi step decomposition and integration approach is presented in this paper and evaluated in a case study. The result show significant improved results compared with sequential scheduling heuristics.

Keywords: Production and outbound distribution, integrated planning, heuristic, decomposition and integration.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2432

Authors: N. F. Jamaluddin, N. A. H. Aizam

Abstract:

This paper explains the educational timetabling problem, a type of scheduling problem that is considered as one of the most challenging problem in optimization and operational research. The university examination timetabling problem (UETP), which involves assigning a set number of exams into a set number of timeslots whilst fulfilling all required conditions, has been widely investigated. The limitation of available timeslots and resources with the increasing number of examinations are the main reasons in the difficulty of solving this problem. Dynamical change in the examination scheduling system adds up the complication particularly in coping up with the demand and new requirements by the communities. Our objective is to investigate these demands and requirements with subjects taken from Universiti Malaysia Terengganu (UMT), through questionnaires. Integer linear programming model which reflects the preferences obtained to produce an effective examination timetabling was formed.

Keywords: Demands, educational timetabling, integer linear programming, scheduling, university examination timetabling problem.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1961

Authors: Siriluck Lorpunmanee, Mohd Noor Sap, Abdul Hanan Abdullah, Chai Chompoo-inwai

Abstract:

Grid computing is growing rapidly in the distributed heterogeneous systems for utilizing and sharing large-scale resources to solve complex scientific problems. Scheduling is the most recent topic used to achieve high performance in grid environments. It aims to find a suitable allocation of resources for each job. A typical problem which arises during this task is the decision of scheduling. It is about an effective utilization of processor to minimize tardiness time of a job, when it is being scheduled. This paper, therefore, addresses the problem by developing a general framework of grid scheduling using dynamic information and an ant colony optimization algorithm to improve the decision of scheduling. The performance of various dispatching rules such as First Come First Served (FCFS), Earliest Due Date (EDD), Earliest Release Date (ERD), and an Ant Colony Optimization (ACO) are compared. Moreover, the benefit of using an Ant Colony Optimization for performance improvement of the grid Scheduling is also discussed. It is found that the scheduling system using an Ant Colony Optimization algorithm can efficiently and effectively allocate jobs to proper resources.

Keywords: Grid computing, Distributed heterogeneous system, Ant colony optimization algorithm, Grid scheduling, Dispatchingrules.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2674

Authors: Ivan C. Mustakerov, Daniela I. Borissova

Abstract:

The increasing competitiveness in manufacturing industry is forcing manufacturers to seek effective processing schedules. The paper presents an optimization manufacture scheduling approach for dependent details processing with given processing sequences and times on multiple machines. By defining decision variables as start and end moments of details processing it is possible to use straightforward variables restrictions to satisfy different technological requirements and to formulate easy to understand and solve optimization tasks for multiple numbers of details and machines. A case study example is solved for seven base moldings for CNC metalworking machines processed on five different machines with given processing order among details and machines and known processing time-s duration. As a result of linear optimization task solution the optimal manufacturing schedule minimizing the overall processing time is obtained. The manufacturing schedule defines the moments of moldings delivery thus minimizing storage costs and provides mounting due-time satisfaction. The proposed optimization approach is based on real manufacturing plant problem. Different processing schedules variants for different technological restrictions were defined and implemented in the practice of Bulgarian company RAIS Ltd. The proposed approach could be generalized for other job shop scheduling problems for different applications.

Keywords: Optimal manufacturing scheduling, linear programming, metalworking machines production, dependant details processing.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1449

Authors: M. Heydari, S. A. Torabi

Abstract:

The problem of lot sizing, sequencing and scheduling multiple products in flow line production systems has been studied by several authors. Almost all of the researches in this area assumed that setup times and costs are sequence –independent even though sequence dependent setups are common in practice. In this paper we present a new mixed integer non linear program (MINLP) and a heuristic method to solve the problem in sequence dependent case. Furthermore, a genetic algorithm has been developed which applies this constructive heuristic to generate initial population. These two proposed solution methods are compared on randomly generated problems. Computational results show a clear superiority of our proposed GA for majority of the test problems.

Keywords: Economic lot scheduling problem, finite horizon, genetic algorithm, mixed zero-one nonlinear programming, sequence-dependent.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1504

Authors: Jain-Shing Liu

Abstract:

In this work, we study the problem of determining the minimum scheduling length that can satisfy end-to-end (ETE) traffic demand in scheduling-based multihop WSNs with cooperative multiple-input multiple-output (MIMO) transmission scheme. Specifically, we present a cross-layer formulation for the joint routing, scheduling and stream control problem by incorporating various power and rate adaptation schemes, and taking into account an antenna beam pattern model and the signal-to-interference-and-noise (SINR) constraint at the receiver. In the context, we also propose column generation (CG) solutions to get rid of the complexity requiring the enumeration of all possible sets of scheduling links.

Keywords: Wireless Sensor Networks, Cross-Layer Design, CooperativeMIMO System, Column Generation.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1617

Authors: K. -H. Yang

Abstract:

In the past, the quay crane operations have been well studied. There were a certain number of scheduling algorithms for quay crane operations, but without considering some nuisance factors that might disrupt the quay crane operations. For example, bad grapples make a crane unable to load or unload containers or a sudden strong breeze stops operations temporarily. Although these disruptive conditions randomly occur, they influence the efficiency of quay crane operations. The disruption is not considered in the operational procedures nor is evaluated in advance for its impacts. This study applies simulation and optimization approaches to develop structures of pre-analysis and post-analysis for the Quay Crane Scheduling Problem to deal with disruptive scenarios for quay crane operation. Numerical experiments are used for demonstrations for the validity of the developed approaches.

Keywords: Disruptive Quay Crane Scheduling, pre-analysis, post-analysis, disruption.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 713

Authors: Babak H. Tabrizi, Seyed Farid Ghaderi

Abstract:

Concurrent planning of project scheduling and material ordering has been increasingly addressed within last decades as an approach to improve the project execution costs. Therefore, we have taken the problem into consideration in this paper, aiming to maximize schedules quality robustness, in addition to minimize the relevant costs. In this regard, a bi-objective mathematical model is developed to formulate the problem. Moreover, it is possible to utilize the all-unit discount for materials purchasing. The problem is then solved by the E-constraint method, and the Pareto front is obtained for a variety of robustness values. The applicability and efficiency of the proposed model is tested by different numerical instances, finally.

Keywords: E-constraint method, material ordering, project management, project scheduling.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1973

Authors: Meng-Hui Chen, Pei-Chann Chang, Wei-Hsiu Huang

Abstract:

Artificial Immune System is adopted as a Heuristic Algorithm to solve the combinatorial problems for decades. Nevertheless, many of these applications took advantage of the benefit for applications but seldom proposed approaches for enhancing the efficiency. In this paper, we continue the previous research to develop a Self-evolving Artificial Immune System II via coordinating the T and B cell in Immune System and built a block-based artificial chromosome for speeding up the computation time and better performance for different complexities of problems. Through the design of Plasma cell and clonal selection which are relative the function of the Immune Response. The Immune Response will help the AIS have the global and local searching ability and preventing trapped in local optima. From the experimental result, the significant performance validates the SEAIS II is effective when solving the permutation flows-hop problems.

Keywords: Artificial Immune System, Clonal Selection, Immune Response, Permutation Flow-shop Scheduling Problems

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1575

Authors: Bita Tadayon, Nasser Salmasi

Abstract:

This research deals with a flexible flowshop scheduling problem with arrival and delivery of jobs in groups and processing them individually. Due to the special characteristics of each job, only a subset of machines in each stage is eligible to process that job. The objective function deals with minimization of sum of the completion time of groups on one hand and minimization of sum of the differences between completion time of jobs and delivery time of the group containing that job (waiting period) on the other hand. The problem can be stated as FFc / rj , Mj / irreg which has many applications in production and service industries. A mathematical model is proposed, the problem is proved to be NPcomplete, and an effective heuristic method is presented to schedule the jobs efficiently. This algorithm can then be used within the body of any metaheuristic algorithm for solving the problem.

Keywords: flexible flowshop scheduling, group processing, machine eligibility constraint, mathematical modeling.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1793

Authors: Smajo Bisanovic, Mensur Hajro, Muris Dlakic

Abstract:

This paper presents one comprehensive modelling approach for maintenance scheduling problem of thermal power units in competitive market. This problem is formulated as a 0/1 mixedinteger linear programming model. Model incorporates long-term bilateral contracts with defined profiles of power and price, and weekly forecasted market prices for market auction. The effectiveness of the proposed model is demonstrated through case study with detailed discussion.

Keywords: Maintenance scheduling, bilateral contracts, market prices, profit.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1575

Authors: Khalid Abd, Kazem Abhary, Romeo Marian

Abstract:

Multiple criteria decision making (MCDM) is an approach to ranking the solutions and finding the best one when two or more solutions are provided. In this study, MCDM approach is proposed to select the most suitable scheduling rule of robotic flexible assembly cells (RFACs). Two MCDM approaches, Analytic Hierarchy Process (AHP) and Technique for Order Preference by Similarity to Ideal Solution (TOPSIS) are proposed for solving the scheduling rule selection problem. The AHP method is employed to determine the weights of the evaluation criteria, while the TOPSIS method is employed to obtain final ranking order of scheduling rules. Four criteria are used to evaluate the scheduling rules. Also, four scheduling policies of RFAC are examined to choose the most appropriate one for this purpose. A numerical example illustrates applications of the suggested methodology. The results show that the methodology is practical and works in RFAC settings.

Keywords: AHP, TOPSIS, Scheduling rules selection

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1779

Authors: Vahid Salmani, Saman Taghavi Zargar, Mahmoud Naghibzadeh

Abstract:

This paper presents a modified version of the maximum urgency first scheduling algorithm. The maximum urgency algorithm combines the advantages of fixed and dynamic scheduling to provide the dynamically changing systems with flexible scheduling. This algorithm, however, has a major shortcoming due to its scheduling mechanism which may cause a critical task to fail. The modified maximum urgency first scheduling algorithm resolves the mentioned problem. In this paper, we propose two possible implementations for this algorithm by using either earliest deadline first or modified least laxity first algorithms for calculating the dynamic priorities. These two approaches are compared together by simulating the two algorithms. The earliest deadline first algorithm as the preferred implementation is then recommended. Afterwards, we make a comparison between our proposed algorithm and maximum urgency first algorithm using simulation and results are presented. It is shown that modified maximum urgency first is superior to maximum urgency first, since it usually has less task preemption and hence, less related overhead. It also leads to less failed non-critical tasks in overloaded situations.

Keywords: Modified maximum urgency first, maximum urgency first, real-time systems, scheduling.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2689

Authors: Fatemeh Azimi, Razeeh Sadat Aboutalebi, Amir Abbas Najafi

Abstract:

In this paper the multi-mode resource-constrained project scheduling problem with discounted cash flows is considered. Minimizing the makespan and maximization the net present value (NPV) are the two common objectives that have been investigated in the literature. We apply one evolutionary algorithm named multiobjective particle swarm optimization (MOPSO) to find Pareto front solutions. We used standard sets of instances from the project scheduling problem library (PSPLIB). The results are computationally compared respect to different metrics taken from the literature on evolutionary multi-objective optimization.

Keywords: Evolutionary multi-objective optimization makespan, multi-mode, resource constraint, net present value.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2264

Authors: Yongxian Jin, Jingzhou Huang

Abstract:

In an open real-time system environment, the coexistence of different kinds of real-time and non real-time applications makes the system scheduling mechanism face new requirements and challenges. One two-level scheduling scheme of the open real-time systems is introduced, and points out that hard and soft real-time applications are scheduled non-distinctively as the same type real-time applications, the Quality of Service (QoS) cannot be guaranteed. It has two flaws: The first, it can not differentiate scheduling priorities of hard and soft real-time applications, that is to say, it neglects characteristic differences between hard real-time applications and soft ones, so it does not suit a more complex real-time environment. The second, the worst case execution time of soft real-time applications cannot be predicted exactly, so it is not worth while to cost much spending in order to assure all soft real-time applications not to miss their deadlines, and doing that may cause resource wasting. In order to solve this problem, a novel two-level real-time scheduling mechanism (including scheduling profile and scheduling algorithm) which adds the process of dealing with soft real-time applications is proposed. Finally, we verify real-time scheduling mechanism from two aspects of theory and experiment. The results indicate that our scheduling mechanism can achieve the following objectives. (1) It can reflect the difference of priority when scheduling hard and soft real-time applications. (2) It can ensure schedulability of hard real-time applications, that is, their rate of missing deadline is 0. (3) The overall rate of missing deadline of soft real-time applications can be less than 1. (4) The deadline of a non-real-time application is not set, whereas the scheduling algorithm that server 0 S uses can avoid the “starvation" of jobs and increase QOS. By doing that, our scheduling mechanism is more compatible with different types of applications and it will be applied more widely.

Keywords: Hard real-time, two-level scheduling profile, open real-time system, non-distinctive schedule, soft real-time

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1531

Authors: Mohammad S. Laghari, Gulzar A. Khuwaja

Abstract:

Many problems in computer vision and image processing present potential for parallel implementations through one of the three major paradigms of geometric parallelism, algorithmic parallelism and processor farming. Static process scheduling techniques are used successfully to exploit geometric and algorithmic parallelism, while dynamic process scheduling is better suited to dealing with the independent processes inherent in the process farming paradigm. This paper considers the application of parallel or multi-computers to a class of problems exhibiting spatial data characteristic of the geometric paradigm. However, by using processor farming paradigm, a dynamic scheduling technique is developed to suit the MIMD structure of the multi-computers. A hybrid scheme of scheduling is also developed and compared with the other schemes. The specific problem chosen for the investigation is the Hough transform for line detection.

Keywords: Hough transforms, parallel computer, parallel paradigms, scheduling.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1615

Authors: Raksha Sharma, Vishnu Kant Soni, Manoj Kumar Mishra, Prachet Bhuyan

Abstract:

Grid computing is a form of distributed computing that involves coordinating and sharing computational power, data storage and network resources across dynamic and geographically dispersed organizations. Scheduling onto the Grid is NP-complete, so there is no best scheduling algorithm for all grid computing systems. An alternative is to select an appropriate scheduling algorithm to use in a given grid environment because of the characteristics of the tasks, machines and network connectivity. Job and resource scheduling is one of the key research area in grid computing. The goal of scheduling is to achieve highest possible system throughput and to match the application need with the available computing resources. Motivation of the survey is to encourage the amateur researcher in the field of grid computing, so that they can understand easily the concept of scheduling and can contribute in developing more efficient scheduling algorithm. This will benefit interested researchers to carry out further work in this thrust area of research.

Keywords: Grid Computing, Job Scheduling, ResourceScheduling.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3377

Authors: Anis Gharbi

Abstract:

This paper considers the problem of scheduling maintenance actions for identical aircraft gas turbine engines. Each one of the turbines consists of parts which frequently require replacement. A finite inventory of spare parts is available and all parts are ready for replacement at any time. The inventory consists of both new and refurbished parts. Hence, these parts have different field lives. The goal is to find a replacement part sequencing that maximizes the time that the aircraft will keep functioning before the inventory is replenished. The problem is formulated as an identical parallel machine scheduling problem where the minimum completion time has to be maximized. Two models have been developed. The first one is an optimization model which is based on a 0-1 linear programming formulation, while the second one is an approximate procedure which consists in decomposing the problem into several two-machine subproblems. Each subproblem is optimally solved using the first model. Both models have been implemented using Lingo and have been tested on two sets of randomly generated data with up to 150 parts and 10 turbines. Experimental results show that the optimization model is able to solve only instances with no more than 4 turbines, while the decomposition procedure often provides near-optimal solutions within a maximum CPU time of 3 seconds.

Keywords: Aircraft turbines, Scheduling, Identical parallel machines, 0-1 linear programming, Heuristic.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1970