StudentShare
Contact Us
Sign In / Sign Up for FREE
Search
Go to advanced search...
Free

Scheduling: Problems, Models and Solution Methods - Case Study Example

Summary
The study "Scheduling: Problems, Models and Solution Methods" focuses on the description of the most important problems, models, and solution methods of scheduling. Literally, scheduling can be defined as the arrangement of the execution of a lot of tasks/operations concerning time…
Download full paper File format: .doc, available for editing
GRAB THE BEST PAPER95.4% of users find it useful
Scheduling: Problems, Models and Solution Methods
Read Text Preview

Extract of sample "Scheduling: Problems, Models and Solution Methods"

of the of the of the Scheduling: some of the most important problems, models and solution methods Literally, scheduling can be defined as the arrangement of the execution of a number of tasks/operations with respect to time. According to ‘hyperdictionary’ (2003) there are various meanings of scheduling with respect to computers: “{instruction scheduling} - sequencing the instructions executed by the {CPU} {multitasking} ("process scheduling") - sharing a CPU between several processes {application} {software} to help organize your daily meetings etc. {task scheduling} - {algorithms} to solve the general problem of satisfying time and resource {constraints} between a number of tasks. Compare {planning}. “ Scheduling, in the scenario of present day computing, has broadened and diversified effects. The performance and requirement of scheduling can be observed in almost all areas pertaining to computing. From a barber’s shop to car assembly line the effectiveness of scheduling has been proven upon various real world scenarios. Theoretical and applied perspectives add more diversity to this phenomenon. In spite of immense work being done in this regard, the performance issues, algorithmic complexities and limitations are few of the areas that are still open for researchers. Optimization of the resource utilization is the main objective of all scheduling strategies. This text takes specific example of CPU scheduling for further detailed discussion. The effectiveness, implications, limitations and remedies of different scheduling strategies is discussed henceforth. A scheduling problem can ideally be defined with respect to its model. On a broader scale, the model refers to the environment, characteristics, constraints and the objective of the scheduling scenario at hand. From the most complex to the most trivial tasks within a system, each processing requires the help of this mechanism. More specifically, every multiprocessing and multi tasking environment cannot survive without proper scheduling algorithms working at its backend. CPU Scheduling: The CPU is a central resource in a computer system environment. The simplest instance that can be considered for scheduling is a uni-processor (1 CPU) environment. CPU scheduling is an attempt to allocate and de-allocate this central resource to the processes in an optimal manner. Maximum CPU utilization and throughput; and Minimum turn-around time (the time for which a process resides in the system) are the goals to be achieved. Following are some of the very basic assumptions established to acquire the basic understanding of the process. The environment is composed of a process queue for CPU. The arrival time of each process in a queue and the expected duration of processing are already recorded. There is just one input device with is respective queue. When a process requires input its request is scheduled accordingly in the input queue and its processing halts for the time being. There are different algorithms that can be studied in this regard. Few are discussed below. First Come First Served (FCFS). This algorithm is considered as the simplest and most robust of all. It can be implemented using a FIFO process queue. It simply schedules the processes according to their arrival times. The basic version of this strategy does not allow process preemption during processing. The algorithm is explained through the following example with table 1. Table 1: Deterministic Model Processes Arrival Time Duration/Size 1 1 5 units 2 3 7 units 3 4 2 units Following are the assumptions that are taken for the sake of simplicity. The time line is assumed to start at zero (0). No input requests. The continuity of process execution remains undisturbed despite the marking of arrival of a new process in the queue by CPU. The Gantt. Chart is as follows, Gantt Chart Processes/Time line 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 Legend: Gray shade indicates processing and Blue indicates waiting The grey portion highlights the processing time and the blue portion represents the respective waiting time of each process in a process queue. The average turnaround time is 8.6 units and the average waiting time of processes is 6 units. The average turnaround time and average waiting time with FCFS is usually high. Considering the unrealistic assumptions maintained for simplicity, there are certain issues. The presence of I/O bound processes would definitely change the whole picture. The effect of context switches done by CPU for marking the arrivals and service of input requests on the turnaround times and waiting times of processes. The duration of stay of a process is always unpredictable due to the incorporated conditional structures and random input requests. A deterministic model is not sufficient to study this algorithm. Simulation or large scale implementation with beta testing are better techniques for analysis. The FCFS environment is also designated as a prioritized environment. The arrival time is the basis of priority. Theoretically the average turnaround time seems to reduce when the priority is given to the shortest duration process first. Shortest Remaining Time First: A preemptive approach. This approach produces the minimum optimal turnaround times and waiting times theoretically. The main reason of its being impractical is the absence of advance knowledge of process durations. For the above example the average turnaround time and average waiting time with SRTF are 7 units and 3.33 units respectively. The anomalies associated with this strategy are outlined as, Process durations cannot be determined in advance. Probabilistic estimates are used for implementation. Does not support deadlines. Shorter the size higher would be the priority. This theme violates rest of the important factors that must be taken into account like system initiated processes etc. Constant preemption may result in process starvation. Although the average turnaround time and waiting time are optimal as compared to other strategies, but the selection of a feasible schedule for a subset of processes takes factorial time. Priority Algorithm: Non-preemptive and preemptive approach. The main theme is to assign integers as priorities explicitly or through a mathematical model after a careful evaluation of most of the important factors. This resolves the issue of unrealistic priorities of SRTF. The process queue becomes a heap based priority queue which further resolves the problem of accommodating external priorities or system designated specialized priorities. The remedy to starvation is achieved through waiting time based increment in the priority by one. This method is known as aging. The idea fully depends on the model or criteria of priority determination. Any flaw in the process may lead to complete failure. Example Table 2: Deterministic Model for Priority Algorithm with 1 as highest priority Processes Arrival Time Duration/Size Priorities 1 1 5 units 3 2 3 7 units 1 3 4 2 units 2 Gantt Chart Processes/Time line 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 Legend: Gray shade indicates processing and Blue indicates waiting The average turnaround time and average waiting time are 9.6 and 5 respectively. The average waiting time is lesser than that of FCFS. The assumptions are same as considered for FCFS. Unlike FCSF and SRTF this algorithm fully supports real time processing. Priority algorithm does not support processes with deadlines and time sharing. Scheduling with Deadlines: The main objective of generalized scheduling is to minimize the total time a job spends in system. Scheduling with deadlines, on the other hand, focuses on the optimization of profit. Table 3 contains example with respective assumptions. Example 1 Table 3: Example 1 Job Deadline Profit 1 2 30 2 1 35 3 2 25 4 1 40 The duration of each job is 1 unit of time. Jobs can be performed before or by their deadlines. The main goal is to find a schedule that reveals maximum yield. A brute force approach considers all feasible schedules and then selects the schedule with maximum profit. This approach takes factorial time. While a greedy approach gives better algorithm. According to Neapolitan (166) following Algorithm 1.1 exhibits greedy approach in solving the problem of scheduling with deadlines. Algorithm 1.1: The objective is to obtain the maximum yield schedule. n represents number of jobs. Array deadline with size n contains respective deadlines. It is sorted according to the respective in profits non increasing order. K contains schedule. J contains optimal sequence. void schedule (int n, const int deadline [], sequence_of_integer& j) { index i; sequence_of_integer K; J = [1]; for (i = 2; i Read More

CHECK THESE SAMPLES OF Scheduling: Problems, Models and Solution Methods

Model for an Online Examination Timetable using Constraint Programming, PHP and MySQL

Amongst the approaches include methods based on evolutionary algorithms (Cote 2005), clustering, graph-based sequential methods, case-based reasoning (Gaspero & Schaerf 2001), hyper-heuristics (Burke et al.... t has been observed that hybrid methods in general give better solutions than pure algorithms.... herefore, a universal solution for the examination timetabling problem would have a substantial impact factor.... Owing to the fact that different institutes require a solution satisfying different constraints, the problem of finding a generalized solution that caters to all these differences could be rather challenging....
3 Pages (750 words) Dissertation

Scheduling: some description of the most important problems, models and solution methods

[Name of the Writer] [Name of the Professor] [Name of the Course] [Date] Scheduling: some description of the most important problems, models and solution methods Literally, scheduling can be defined as the arrangement of the execution of a number of tasks/operations with respect to time.... According to ‘hyperdictionary' (2003) there are various meanings of scheduling with respect to computers: “{instruction scheduling} - sequencing the instructions executed by the {CPU} {multitasking} ("process scheduling") - sharing a CPU between several processes {application} {software} to help organize your daily meetings etc....
5 Pages (1250 words) Essay

Commonly Used Heuristics in Resources Allocation

Therefore, the procedures of heuristic solution are requisite in the solving of cases of large problems as they normally appear in the practical cases.... Most commonly used models for program scheduling and planning do take into consideration the problem of availability of resources, even though many essential resources are limited and restrain the activities of scheduling that need them.... Several works published in the field of project management refer to the single projects' scheduling and time objectives such as minimizing the duration of project....
6 Pages (1500 words) Essay

Planning, Scheduling, and Control of Large Projects

Planning, scheduling and control of large projects has become less difficult because of the tools of networking.... The uses of network analysis are as extensive as the subject itself.... Yet at the same time network analysis should not be seen as a tool for managing complexity in isolation....
19 Pages (4750 words) Essay

Focus Plastics Plc - Producer of Moulded Plastic

The paper "Focus Plastics Plc - Producer of Moulded Plastic" describes that in the process of planning and controlling the production, planning manager has experienced certain problems related to scheduling of the different product range.... In the process of operations, new product trial increases the product cycle time and hence created the problems for the company.... So the company is always trying to develop newer products but in the process faces some problems in developing products continuously and timely....
12 Pages (3000 words) Essay

Operational Research in Decision Making

Operational research is a tool to help make better decisions by using modern concepts and advanced analytical methods.... While this will be based on the latest decision-making tools and methods, all available options should be considered as input to the operation research model adopted for a particular case.... Hence, the operation research professionals customize each solution, that is unique and tailor-made for the imposing challenge.... This leads to the testing of many options and conclusions for reaching the best solution possible....
6 Pages (1500 words) Report

Dynamic Scheduling In Manufacturing Systems

The paper "Dynamic scheduling In Manufacturing Systems" is a great example of a report on management.... The problem of scheduling concerns the search for optimal (or almost optimal) schedules that are subject to several constraints.... The paper "Dynamic scheduling In Manufacturing Systems" is a great example of a report on management.... The problem of scheduling concerns the search for optimal (or almost optimal) schedules that are subject to several constraints....
12 Pages (3000 words) Report

Dynamic Lot Sizing Model for Stochastic Inventory Factors

(2016) employed new lagrangian heuristic to create a solution, while Hwang and Kang (2016) employed geometric method.... The models classified in this group are quite diverse though there are some that have slight similarities.... For instance, Tunc et al and Rossi, Kilic & Tarim employed unified mixed integer programming modelling technique in the development of their models to resolve the identified problems.... Chen, Tunc et al and Rossi, Kilic & Tarim, and Rossi Kilic & Tarim, demonstrated the efficiency of their proposed model by comparing them with the previously presented models in the literature....
16 Pages (4000 words) Assignment
sponsored ads
We use cookies to create the best experience for you. Keep on browsing if you are OK with that, or find out how to manage cookies.
Contact Us