Search results for: general flow shop scheduling problem
15823 Heuristic for Scheduling Correlated Parallel Machine to Minimize Maximum Lateness and Total Weighed Completion Time
Authors: Yang-Kuei Lin, Yun-Xi Zhang
Abstract:
This research focuses on the bicriteria correlated parallel machine scheduling problem. The two objective functions considered in this problem are to minimize maximum lateness and total weighted completion time. We first present a mixed integer programming (MIP) model that can find the entire efficient frontier for the studied problem. Next, we have proposed a bicriteria heuristic that can find non-dominated solutions for the studied problem. The performance of the proposed bicriteria heuristic is compared with the efficient frontier generated by solving the MIP model. Computational results indicate that the proposed bicriteria heuristic can solve the problem efficiently and find a set of diverse solutions that are uniformly distributed along the efficient frontier.Keywords: bicriteria, correlated parallel machines, heuristic, scheduling
Procedia PDF Downloads 13615822 Single Machine Scheduling Problem to Minimize the Number of Tardy Jobs
Authors: Ali Allahverdi, Harun Aydilek, Asiye Aydilek
Abstract:
Minimizing the number of tardy jobs is an important factor to consider while making scheduling decisions. This is because on-time shipments are vital for lowering cost and increasing customers’ satisfaction. This paper addresses the single machine scheduling problem with the objective of minimizing the number of tardy jobs. The only known information is the lower and upper bounds for processing times, and deterministic job due dates. A dominance relation is established, and an algorithm is proposed. Several heuristics are generated from the proposed algorithm. Computational analysis indicates that the performance of one of the heuristics is very close to the optimal solution, i.e., on average, less than 1.5 % from the optimal solution.Keywords: single machine scheduling, number of tardy jobs, heuristi, lower and upper bounds
Procedia PDF Downloads 55215821 Solving Operating Room Scheduling Problem by Using Dispatching Rule
Authors: Yang-Kuei Lin, Yin-Yi Chou
Abstract:
In this research, we have considered operating room scheduling problem. The objective is to minimize total operating cost. The total operating cost includes idle cost and overtime cost. We have proposed a dispatching rule that can guarantee to find feasible solutions for the studied problem efficiently. We compared the proposed dispatching rule with the optimal solutions found by solving Inter Programming, and other solutions found by using modified existing dispatching rules. The computational results indicates that the proposed heuristic can find near optimal solutions efficiently.Keywords: assignment, dispatching rule, operation rooms, scheduling
Procedia PDF Downloads 22715820 Scheduling in a Single-Stage, Multi-Item Compatible Process Using Multiple Arc Network Model
Authors: Bokkasam Sasidhar, Ibrahim Aljasser
Abstract:
The problem of finding optimal schedules for each equipment in a production process is considered, which consists of a single stage of manufacturing and which can handle different types of products, where changeover for handling one type of product to the other type incurs certain costs. The machine capacity is determined by the upper limit for the quantity that can be processed for each of the products in a set up. The changeover costs increase with the number of set ups and hence to minimize the costs associated with the product changeover, the planning should be such that similar types of products should be processed successively so that the total number of changeovers and in turn the associated set up costs are minimized. The problem of cost minimization is equivalent to the problem of minimizing the number of set ups or equivalently maximizing the capacity utilization in between every set up or maximizing the total capacity utilization. Further, the production is usually planned against customers’ orders, and generally different customers’ orders are assigned one of the two priorities – “normal” or “priority” order. The problem of production planning in such a situation can be formulated into a Multiple Arc Network (MAN) model and can be solved sequentially using the algorithm for maximizing flow along a MAN and the algorithm for maximizing flow along a MAN with priority arcs. The model aims to provide optimal production schedule with an objective of maximizing capacity utilization, so that the customer-wise delivery schedules are fulfilled, keeping in view the customer priorities. Algorithms have been presented for solving the MAN formulation of the production planning with customer priorities. The application of the model is demonstrated through numerical examples.Keywords: scheduling, maximal flow problem, multiple arc network model, optimization
Procedia PDF Downloads 39715819 The Utilization of Particle Swarm Optimization Method to Solve Nurse Scheduling Problem
Authors: Norhayati Mohd Rasip, Abd. Samad Hasan Basari , Nuzulha Khilwani Ibrahim, Burairah Hussin
Abstract:
The allocation of working schedule especially for shift environment is hard to fulfill its fairness among them. In the case of nurse scheduling, to set up the working time table for them is time consuming and complicated, which consider many factors including rules, regulation and human factor. The scenario is more complicated since most nurses are women which have personnel constraints and maternity leave factors. The undesirable schedule can affect the nurse productivity, social life and the absenteeism can significantly as well affect patient's life. This paper aimed to enhance the scheduling process by utilizing the particle swarm optimization in order to solve nurse scheduling problem. The result shows that the generated multiple initial schedule is fulfilled the requirements and produces the lowest cost of constraint violation.Keywords: nurse scheduling, particle swarm optimisation, nurse rostering, hard and soft constraint
Procedia PDF Downloads 36215818 The Development of Online-Class Scheduling Management System Conducted by the Case Study of Department of Social Science: Faculty of Humanities and Social Sciences Suan Sunandha Rajabhat University
Authors: Wipada Chaiwchan, Patcharee Klinhom
Abstract:
This research is aimed to develop the online-class scheduling management system and improve as a complex problem solution, this must take into consideration in various conditions and factors. In addition to the number of courses, the number of students and a timetable to study, the physical characteristics of each class room and regulations used in the class scheduling must also be taken into consideration. This system is developed to assist management in the class scheduling for convenience and efficiency. It can provide several instructors to schedule simultaneously. Both lecturers and students can check and publish a timetable and other documents associated with the system online immediately. It is developed in a web-based application. PHP is used as a developing tool. The database management system was MySQL. The tool that is used for efficiency testing of the system is questionnaire. The system was evaluated by using a Black-Box testing. The sample was composed of 2 groups: 5 experts and 100 general users. The average and the standard deviation of results from the experts were 3.50 and 0.67. The average and the standard deviation of results from the general users were 3.54 and 0.54. In summary, the results from the research indicated that the satisfaction of users was in a good level. Therefore, this system could be implemented in an actual workplace and satisfy the users’ requirement effectivelyKeywords: timetable, schedule, management system, online
Procedia PDF Downloads 23215817 Constraint-Directed Techniques for Transport Scheduling with Capacity Restrictions of Automotive Manufacturing Components
Authors: Martha Ndeley, John Ikome
Abstract:
In this paper, we expand the scope of constraint-directed techniques to deal with the case of transportation schedule with capacity restrictions where the scheduling problem includes alternative activities. That is, not only does the scheduling problem consist of determining when an activity is to be executed, but also determining which set of alternative activities is to be executed at all level of transportation from input to output. Such problems encompass both alternative resource problems and alternative process plan problems. We formulate a constraint-based representation of alternative activities to model problems containing such choices. We then extend existing constraint-directed scheduling heuristic commitment techniques and propagators to reason directly about the fact that an activity does not necessarily have to exist in a final transportation schedule without being completed. Tentative results show that an algorithm using a novel texture-based heuristic commitment technique propagators achieves the best overall performance of the techniques tested.Keywords: production, transportation, scheduling, integrated
Procedia PDF Downloads 35115816 Two Stage Assembly Flowshop Scheduling Problem Minimizing Total Tardiness
Authors: Ali Allahverdi, Harun Aydilek, Asiye Aydilek
Abstract:
The two stage assembly flowshop scheduling problem has lots of application in real life. To the best of our knowledge, the two stage assembly flowshop scheduling problem with total tardiness performance measure and separate setup times has not been addressed so far, and hence, it is addressed in this paper. Different dominance relations are developed and several algorithms are proposed. Extensive computational experiments are conducted to evaluate the proposed algorithms. The computational experiments have shown that one of the algorithms performs much better than the others. Moreover, the experiments have shown that the best performing algorithm performs much better than the best existing algorithm for the case of zero setup times in the literature. Therefore, the proposed best performing algorithm not only can be used for problems with separate setup times but also for the case of zero setup times.Keywords: scheduling, assembly flowshop, total tardiness, algorithm
Procedia PDF Downloads 34015815 Decision Support System for Solving Multi-Objective Routing Problem
Authors: Ismail El Gayar, Ossama Ismail, Yousri El Gamal
Abstract:
This paper presented a technique to solve one of the transportation problems that faces us in real life which is the Bus Scheduling Problem. Most of the countries using buses in schools, companies and traveling offices as an example to transfer multiple passengers from many places to specific place and vice versa. This transferring process can cost time and money, so we build a decision support system that can solve this problem. In this paper, a genetic algorithm with the shortest path technique is used to generate a competitive solution to other well-known techniques. It also presents a comparison between our solution and other solutions for this problem.Keywords: bus scheduling problem, decision support system, genetic algorithm, shortest path
Procedia PDF Downloads 40015814 Optimal Scheduling for Energy Storage System Considering Reliability Constraints
Authors: Wook-Won Kim, Je-Seok Shin, Jin-O Kim
Abstract:
This paper propose the method for optimal scheduling for battery energy storage system with reliability constraint of energy storage system in reliability aspect. The optimal scheduling problem is solved by dynamic programming with proposed transition matrix. Proposed optimal scheduling method guarantees the minimum fuel cost within specific reliability constraint. For evaluating proposed method, the timely capacity outage probability table (COPT) is used that is calculated by convolution of probability mass function of each generator. This study shows the result of optimal schedule of energy storage system.Keywords: energy storage system (ESS), optimal scheduling, dynamic programming, reliability constraints
Procedia PDF Downloads 39415813 Scheduling in Cloud Networks Using Chakoos Algorithm
Authors: Masoumeh Ali Pouri, Hamid Haj Seyyed Javadi
Abstract:
Nowadays, cloud processing is one of the important issues in information technology. Since scheduling of tasks graph is an NP-hard problem, considering approaches based on undeterminisitic methods such as evolutionary processing, mostly genetic and cuckoo algorithms, will be effective. Therefore, an efficient algorithm has been proposed for scheduling of tasks graph to obtain an appropriate scheduling with minimum time. In this algorithm, the new approach is based on making the length of the critical path shorter and reducing the cost of communication. Finally, the results obtained from the implementation of the presented method show that this algorithm acts the same as other algorithms when it faces graphs without communication cost. It performs quicker and better than some algorithms like DSC and MCP algorithms when it faces the graphs involving communication cost.Keywords: cloud computing, scheduling, tasks graph, chakoos algorithm
Procedia PDF Downloads 5315812 A Hybrid Model of Goal, Integer and Constraint Programming for Single Machine Scheduling Problem with Sequence Dependent Setup Times: A Case Study in Aerospace Industry
Authors: Didem Can
Abstract:
Scheduling problems are one of the most fundamental issues of production systems. Many different approaches and models have been developed according to the production processes of the parts and the main purpose of the problem. In this study, one of the bottleneck stations of a company serving in the aerospace industry is analyzed and considered as a single machine scheduling problem with sequence-dependent setup times. The objective of the problem is assigning a large number of similar parts to the same shift -to reduce chemical waste- while minimizing the number of tardy jobs. The goal programming method will be used to achieve two different objectives simultaneously. The assignment of parts to the shift will be expressed using the integer programming method. Finally, the constraint programming method will be used as it provides a way to find a result in a short time by avoiding worse resulting feasible solutions with the defined variables set. The model to be established will be tested and evaluated with real data in the application part.Keywords: constraint programming, goal programming, integer programming, sequence-dependent setup, single machine scheduling
Procedia PDF Downloads 22615811 Towards Developing a Self-Explanatory Scheduling System Based on a Hybrid Approach
Authors: Jian Zheng, Yoshiyasu Takahashi, Yuichi Kobayashi, Tatsuhiro Sato
Abstract:
In the study, we present a conceptual framework for developing a scheduling system that can generate self-explanatory and easy-understanding schedules. To this end, a user interface is conceived to help planners record factors that are considered crucial in scheduling, as well as internal and external sources relating to such factors. A hybrid approach combining machine learning and constraint programming is developed to generate schedules and the corresponding factors, and accordingly display them on the user interface. Effects of the proposed system on scheduling are discussed, and it is expected that scheduling efficiency and system understandability will be improved, compared with previous scheduling systems.Keywords: constraint programming, factors considered in scheduling, machine learning, scheduling system
Procedia PDF Downloads 31615810 A Fuzzy Mathematical Model for Order Acceptance and Scheduling Problem
Authors: E. Koyuncu
Abstract:
The problem of Order Acceptance and Scheduling (OAS) is defined as a joint decision of which orders to accept for processing and how to schedule them. Any linear programming model representing real-world situation involves the parameters defined by the decision maker in an uncertain way or by means of language statement. Fuzzy data can be used to incorporate vagueness in the real-life situation. In this study, a fuzzy mathematical model is proposed for a single machine OAS problem, where the orders are defined by their fuzzy due dates, fuzzy processing times, and fuzzy sequence dependent setup times. The signed distance method, one of the fuzzy ranking methods, is used to handle the fuzzy constraints in the model.Keywords: fuzzy mathematical programming, fuzzy ranking, order acceptance, single machine scheduling
Procedia PDF Downloads 33015809 Review on Crew Scheduling of Bus Transit: A Case Study in Kolkata
Authors: Sapan Tiwari, Namrata Ghosh
Abstract:
In urban mass transit, crew scheduling always plays a significant role. It deals with the formulation of work timetables for its staff so that an organization can meet the demand for its products or services. The efficient schedules of a specified timetable have an enormous impact on staff demand. It implies that an urban mass transit company's financial outcomes are strongly associated with planning operations in the region. The research aims to demonstrate the state of the crew scheduling studies and its practical implementation in mass transit businesses in metropolitan areas. First, there is a short overview of past studies in the field. Subsequently, the restrictions and problems with crew scheduling and some models, which have been developed to solve the related issues with their mathematical formulation, are defined. The comments are completed by a description of the solution opportunities provided by computer-aided scheduling program systems for operational use and exposures from urban mass transit organizations. Furthermore, Bus scheduling is performed using the Hungarian technique of problem-solving tasks and mathematical modeling. Afterward, the crew scheduling problem, which consists of developing duties using predefined tasks with set start and end times and places, is resolved. Each duty has to comply with a set line of work. The objective is to minimize a mixture of fixed expenses (number of duties) and varying costs. After the optimization of cost, the outcome of the research is that the same frequency can be provided with fewer buses and less workforce.Keywords: crew scheduling, duty, optimization of cost, urban mass transit
Procedia PDF Downloads 14315808 Solving Weighted Number of Operation Plus Processing Time Due-Date Assignment, Weighted Scheduling and Process Planning Integration Problem Using Genetic and Simulated Annealing Search Methods
Authors: Halil Ibrahim Demir, Caner Erden, Mumtaz Ipek, Ozer Uygun
Abstract:
Traditionally, the three important manufacturing functions, which are process planning, scheduling and due-date assignment, are performed separately and sequentially. For couple of decades, hundreds of studies are done on integrated process planning and scheduling problems and numerous researches are performed on scheduling with due date assignment problem, but unfortunately the integration of these three important functions are not adequately addressed. Here, the integration of these three important functions is studied by using genetic, random-genetic hybrid, simulated annealing, random-simulated annealing hybrid and random search techniques. As well, the importance of the integration of these three functions and the power of meta-heuristics and of hybrid heuristics are studied.Keywords: process planning, weighted scheduling, weighted due-date assignment, genetic search, simulated annealing, hybrid meta-heuristics
Procedia PDF Downloads 46415807 Approximation Algorithms for Peak-Demand Reduction
Authors: Zaid Jamal Saeed Almahmoud
Abstract:
Smart grid is emerging as the future power grid, with smart techniques to optimize power consumption and electricity generation. Minimizing peak power consumption under a fixed delay requirement is a significant problem in the smart grid.For this problem, all appliances must be scheduled within a given finite time duration. We consider the problem of minimizing the peak demand under appliances constraints by scheduling power jobs with uniform release dates and deadlines. As the problem is known to be NP-hard, we analyze the performance of a version of the natural greedy heuristic for solving this problem. Our theoretical analysis and experimental results show that the proposed heuristic outperforms existing methods by providing a better approximation to the optimal solution.Keywords: peak demand scheduling, approximation algorithms, smart grid, heuristics
Procedia PDF Downloads 8915806 The Management Information System for Convenience Stores: Case Study in 7 Eleven Shop in Bangkok
Authors: Supattra Kanchanopast
Abstract:
The purpose of this research is to develop and design a management information system for 7 eleven shop in Bangkok. The system was designed and developed to meet users’ requirements via the internet network by use of application software such as My SQL for database management, Apache HTTP Server for Web Server and PHP Hypertext Preprocessor for an interface between web server, database and users. The system was designed into two subsystems as the main system, or system for head office, and the branch system for branch shops. These consisted of three parts which are classified by user management as shop management, inventory management and Point of Sale (POS) management. The implementation of the MIS for the mini-mart shop, can lessen the amount of paperwork and reduce repeating tasks so it may decrease the capital of the business and support an extension of branches in the future as well.Keywords: convenience store, the management information system, inventory management, 7 eleven shop
Procedia PDF Downloads 46615805 Beliefs in Auspicious Materials of Shop Entrepreneurs in Maung Hat Yai, Thailand
Authors: Punya Tepsing
Abstract:
This research aimed to study the beliefs in auspicious materials of entrepreneurs in Muang Hat Yai. The data were collected via documentary research and field work including interviews, observations shops in Hat Yai which used auspicious materials to bring lucks to the shops. The results were as follows. The beliefs in auspicious materials that the entrepreneurs had were of three areas: 1) The auspicious materials could correct the improperness of the shop location, for example, the shop situated opposite a branch road, a shrine, or a bank. The owner usually corrected it by putting Chinese auspicious materials in front of or in the shop, for example, a lion holding a sword in his mouth, or a mirror, etc. 2) The auspicious materials could bring in more income. The owner of the shop usually put the auspicious materials such as a cat beckoning and a bamboo fish trap believed to trap money in front of or inside the shop. 3) The auspicious materials like turtles, paired fish and a monster holding the moon in his mouth could solve life problems including health, family, and safety problems. The use of these auspicious materials showed the blending of the beliefs of the Chinese shop entrepreneurs with the Thai folk beliefs. What is interesting is that Hat Yai is located near the three southern border provinces which are the unrest area and this may cause the number of tourists to decline. This prompted them to build a mechanism in adjusting themselves both to save their lives and to increase the number of customers. Auspicious materials can make them feel more confident.Keywords: belief, auspicious materials, shop, entrepreneur, Maung Hat Yai
Procedia PDF Downloads 23615804 Core Number Optimization Based Scheduler to Order/Mapp Simulink Application
Authors: Asma Rebaya, Imen Amari, Kaouther Gasmi, Salem Hasnaoui
Abstract:
Over these last years, the number of cores witnessed a spectacular increase in digital signal and general use processors. Concurrently, significant researches are done to get benefit from the high degree of parallelism. Indeed, these researches are focused to provide an efficient scheduling from hardware/software systems to multicores architecture. The scheduling process consists on statically choose one core to execute one task and to specify an execution order for the application tasks. In this paper, we describe an efficient scheduler that calculates the optimal number of cores required to schedule an application, gives a heuristic scheduling solution and evaluates its cost. Our proposal results are evaluated and compared with Preesm scheduler results and we prove that ours allows better scheduling in terms of latency, computation time and number of cores.Keywords: computation time, hardware/software system, latency, optimization, multi-cores platform, scheduling
Procedia PDF Downloads 27615803 An Integrated Mixed-Integer Programming Model to Address Concurrent Project Scheduling and Material Ordering
Authors: Babak H. Tabrizi, Seyed Farid Ghaderi
Abstract:
Concurrent planning of project scheduling and material ordering can provide more flexibility to the project scheduling problem, as the project execution costs can be enhanced. Hence, the issue has been taken into account in this paper. To do so, a mixed-integer mathematical model is developed which considers the aforementioned flexibility, in addition to the materials quantity discount and space availability restrictions. Moreover, the activities duration has been treated as decision variables. Finally, the efficiency of the proposed model is tested by different instances. Additionally, the influence of the aforementioned parameters is investigated on the model performance.Keywords: material ordering, project scheduling, quantity discount, space availability
Procedia PDF Downloads 36115802 Factory Communication System for Customer-Based Production Execution: An Empirical Study on the Manufacturing System Entropy
Authors: Nyashadzashe Chiraga, Anthony Walker, Glen Bright
Abstract:
The manufacturing industry is currently experiencing a paradigm shift into the Fourth Industrial Revolution in which customers are increasingly at the epicentre of production. The high degree of production customization and personalization requires a flexible manufacturing system that will rapidly respond to the dynamic and volatile changes driven by the market. They are a gap in technology that allows for the optimal flow of information and optimal manufacturing operations on the shop floor regardless of the rapid changes in the fixture and part demands. Information is the reduction of uncertainty; it gives meaning and context on the state of each cell. The amount of information needed to describe cellular manufacturing systems is investigated by two measures: the structural entropy and the operational entropy. Structural entropy is the expected amount of information needed to describe scheduled states of a manufacturing system. While operational entropy is the amount of information that describes the scheduled states of a manufacturing system, which occur during the actual manufacturing operation. Using Anylogic simulator a typical manufacturing job shop was set-up with a cellular manufacturing configuration. The cellular make-up of the configuration included; a Material handling cell, 3D Printer cell, Assembly cell, manufacturing cell and Quality control cell. The factory shop provides manufactured parts to a number of clients, and there are substantial variations in the part configurations, new part designs are continually being introduced to the system. Based on the normal expected production schedule, the schedule adherence was calculated from the structural entropy and operation entropy of varying the amounts of information communicated in simulated runs. The structural entropy denotes a system that is in control; the necessary real-time information is readily available to the decision maker at any point in time. For contractive analysis, different out of control scenarios were run, in which changes in the manufacturing environment were not effectively communicated resulting in deviations in the original predetermined schedule. The operational entropy was calculated from the actual operations. From the results obtained in the empirical study, it was seen that increasing, the efficiency of a factory communication system increases the degree of adherence of a job to the expected schedule. The performance of downstream production flow fed from the parallel upstream flow of information on the factory state was increased.Keywords: information entropy, communication in manufacturing, mass customisation, scheduling
Procedia PDF Downloads 23915801 A Novel Integration of Berth Allocation, Quay Cranes and Trucks Scheduling Problems in Container Terminals
Authors: M. Moharami Gargari, S. Javdani Zamani, A. Mohammadnejad, S. Abuali
Abstract:
As maritime container transport is developing fast, the need arises for efficient operations at container terminals. One of the most important determinants of container handling efficiency is the productivity of quay cranes and internal transportation vehicles, which are responsible transporting of containers for unloading and loading operations for container vessels. For this reason, this paper presents an integrated mathematical model formulation for discrete berths with quay cranes and internal transportations vehicles. The problems have received increasing attention in the literature and the present paper deals with the integration of these interrelated problems. A new mixed integer linear formulation is developed for the Berth Allocation Problem (BAP), Quay Crane Assignment and Scheduling Problem (QCASP) and Internal Transportation Scheduling (ITS), which accounts for cranes and trucks positioning conditions.Keywords: discrete berths, container terminal, truck scheduling, dynamic vessel arrival
Procedia PDF Downloads 39215800 Multi-Level Priority Based Task Scheduling Algorithm for Workflows in Cloud Environment
Authors: Anju Bala, Inderveer Chana
Abstract:
Task scheduling is the key concern for the execution of performance-driven workflow applications. As efficient scheduling can have major impact on the performance of the system, task scheduling is often chosen for assigning the request to resources in an efficient way based on cloud resource characteristics. In this paper, priority based task scheduling algorithm has been proposed that prioritizes the tasks based on the length of the instructions. The proposed scheduling approach prioritize the tasks of Cloud applications according to the limits set by six sigma control charts based on dynamic threshold values. Further, the proposed algorithm has been validated through the CloudSim toolkit. The experimental results demonstrate that the proposed algorithm is effective for handling multiple task lists from workflows and in considerably reducing Makespan and Execution time.Keywords: cloud computing, priority based scheduling, task scheduling, VM allocation
Procedia PDF Downloads 51215799 Optimization of Scheduling through Altering Layout Using Pro-Model
Authors: Zouhair Issa Ahmed, Ahmed Abdulrasool Ahmed, Falah Hassan Abdulsada
Abstract:
This paper presents a layout of a factory using Pro-Model simulation by choosing the best layout that gives the highest productivity and least work in process. The general problem is to find the best sequence in which jobs pass between the machines which are compatible with the technological constraints and optimal with respect to some performance criteria. The best simulation with Pro-Model program increased productivity and reduced work in process by balancing lines of production compared with the current layout of factory when productivity increased from 45 products to 180 products through 720 hours.Keywords: scheduling, Pro-Model, simulation, balancing lines of production, layout planning, WIP
Procedia PDF Downloads 62615798 ACO-TS: an ACO-based Algorithm for Optimizing Cloud Task Scheduling
Authors: Fahad Y. Al-dawish
Abstract:
The current trend by a large number of organizations and individuals to use cloud computing. Many consider it a significant shift in the field of computing. Cloud computing are distributed and parallel systems consisting of a collection of interconnected physical and virtual machines. With increasing request and profit of cloud computing infrastructure, diverse computing processes can be executed on cloud environment. Many organizations and individuals around the world depend on the cloud computing environments infrastructure to carry their applications, platform, and infrastructure. One of the major and essential issues in this environment related to allocating incoming tasks to suitable virtual machine (cloud task scheduling). Cloud task scheduling is classified as optimization problem, and there are several meta-heuristic algorithms have been anticipated to solve and optimize this problem. Good task scheduler should execute its scheduling technique on altering environment and the types of incoming task set. In this research project a cloud task scheduling methodology based on ant colony optimization ACO algorithm, we call it ACO-TS Ant Colony Optimization for Task Scheduling has been proposed and compared with different scheduling algorithms (Random, First Come First Serve FCFS, and Fastest Processor to the Largest Task First FPLTF). Ant Colony Optimization (ACO) is random optimization search method that will be used for assigning incoming tasks to available virtual machines VMs. The main role of proposed algorithm is to minimizing the makespan of certain tasks set and maximizing resource utilization by balance the load among virtual machines. The proposed scheduling algorithm was evaluated by using Cloudsim toolkit framework. Finally after analyzing and evaluating the performance of experimental results we find that the proposed algorithm ACO-TS perform better than Random, FCFS, and FPLTF algorithms in each of the makespaan and resource utilization.Keywords: cloud Task scheduling, ant colony optimization (ACO), cloudsim, cloud computing
Procedia PDF Downloads 41715797 Generic Model for Timetabling Problems by Integer Linear Programmimg Approach
Authors: Nur Aidya Hanum Aizam, Vikneswary Uvaraja
Abstract:
The agenda of showing the scheduled time for performing certain tasks is known as timetabling. It widely used in many departments such as transportation, education, and production. Some difficulties arise to ensure all tasks happen in the time and place allocated. Therefore, many researchers invented various programming model to solve the scheduling problems from several fields. However, the studies in developing the general integer programming model for many timetabling problems are still questionable. Meanwhile, this thesis describe about creating a general model which solve different types of timetabling problems by considering the basic constraints. Initially, the common basic constraints from five different fields are selected and analyzed. A general basic integer programming model was created and then verified by using the medium set of data obtained randomly which is much similar to realistic data. The mathematical software, AIMMS with CPLEX as a solver has been used to solve the model. The model obtained is significant in solving many timetabling problems easily since it is modifiable to all types of scheduling problems which have same basic constraints.Keywords: AIMMS mathematical software, integer linear programming, scheduling problems, timetabling
Procedia PDF Downloads 42815796 Energy-Aware Scheduling in Real-Time Systems: An Analysis of Fair Share Scheduling and Priority-Driven Preemptive Scheduling
Authors: Su Xiaohan, Jin Chicheng, Liu Yijing, Burra Venkata Durga Kumar
Abstract:
Energy-aware scheduling in real-time systems aims to minimize energy consumption, but issues related to resource reservation and timing constraints remain challenges. This study focuses on analyzing two scheduling algorithms, Fair-Share Scheduling (FFS) and Priority-Driven Preemptive Scheduling (PDPS), for solving these issues and energy-aware scheduling in real-time systems. Based on research on both algorithms and the processes of solving two problems, it can be found that Fair-Share Scheduling ensures fair allocation of resources but needs to improve with an imbalanced system load, and Priority-Driven Preemptive Scheduling prioritizes tasks based on criticality to meet timing constraints through preemption but relies heavily on task prioritization and may not be energy efficient. Therefore, improvements to both algorithms with energy-aware features will be proposed. Future work should focus on developing hybrid scheduling techniques that minimize energy consumption through intelligent task prioritization, resource allocation, and meeting time constraints.Keywords: energy-aware scheduling, fair-share scheduling, priority-driven preemptive scheduling, real-time systems, optimization, resource reservation, timing constraints
Procedia PDF Downloads 11215795 Using the SMT Solver to Minimize the Latency and to Optimize the Number of Cores in an NoC-DSP Architectures
Authors: Imen Amari, Kaouther Gasmi, Asma Rebaya, Salem Hasnaoui
Abstract:
The problem of scheduling and mapping data flow applications on multi-core architectures is notoriously difficult. This difficulty is related to the rapid evaluation of Telecommunication and multimedia systems accompanied by a rapid increase of user requirements in terms of latency, execution time, consumption, energy, etc. Having an optimal scheduling on multi-cores DSP (Digital signal Processors) platforms is a challenging task. In this context, we present a novel technic and algorithm in order to find a valid schedule that optimizes the key performance metrics particularly the Latency. Our contribution is based on Satisfiability Modulo Theories (SMT) solving technologies which is strongly driven by the industrial applications and needs. This paper, describe a scheduling module integrated in our proposed Workflow which is advised to be a successful approach for programming the applications based on NoC-DSP platforms. This workflow transform automatically a Simulink model to a synchronous dataflow (SDF) model. The automatic transformation followed by SMT solver scheduling aim to minimize the final latency and other software/hardware metrics in terms of an optimal schedule. Also, finding the optimal numbers of cores to be used. In fact, our proposed workflow taking as entry point a Simulink file (.mdl or .slx) derived from embedded Matlab functions. We use an approach which is based on the synchronous and hierarchical behavior of both Simulink and SDF. Whence, results of running the scheduler which exist in the Workflow mentioned above using our proposed SMT solver algorithm refinements produce the best possible scheduling in terms of latency and numbers of cores.Keywords: multi-cores DSP, scheduling, SMT solver, workflow
Procedia PDF Downloads 28015794 A Case Study of Bee Algorithm for Ready Mixed Concrete Problem
Authors: Wuthichai Wongthatsanekorn, Nuntana Matheekrieangkrai
Abstract:
This research proposes Bee Algorithm (BA) to optimize Ready Mixed Concrete (RMC) truck scheduling problem from single batch plant to multiple construction sites. This problem is considered as an NP-hard constrained combinatorial optimization problem. This paper provides the details of the RMC dispatching process and its related constraints. BA was then developed to minimize total waiting time of RMC trucks while satisfying all constraints. The performance of BA is then evaluated on two benchmark problems (3 and 5construction sites) according to previous researchers. The simulation results of BA are compared in term of efficiency and accuracy with Genetic Algorithm (GA) and all problems show that BA approach outperforms GA in term of efficiency and accuracy to obtain optimal solution. Hence, BA approach could be practically implemented to obtain the best schedule.Keywords: bee colony optimization, ready mixed concrete problem, ruck scheduling, multiple construction sites
Procedia PDF Downloads 381