Scheduling Jobs on Cloud Computing using Firefly Algorithm

Demyana Izzat Esa,Adil Yousif 보안공학연구지원센터 2016 International Journal of Grid and Distributed Comp Vol.9 No.7

Cloud computing is a new technology, instead of all computer hardware and software that used on desktop, or somewhere within company's network, it's presented as a service by cloud service providers and accessed via the Internet. Exactly where hardware and software are located and how everything works does not matter. In cloud computing there are many jobs that requires to be executed on the available resources to achieve best minimal execution time. Several optimization methods are available for cloud job scheduling. However, the job scheduling process is still need to be optimized. This paper proposes a new job scheduling mechanism using Firefly Algorithm to minimize the execution time of jobs. The proposed mechanism based on information of jobs and resources such as length of job speed of resource and identifiers. The scheduling function in the proposed job scheduling mechanism firstly creates a set of jobs and resources to generate the population by assigning the jobs to resources randomly and evaluates the population using a fitness value which represents the execution time of jobs. Secondly the function used iterations to regenerate populations based on firefly behavior to produce the best job schedule that gives the minimum execution time of jobs. Several scenarios are implemented using Java Language and CloudSim simulator. Different settings have been considered in the evaluation and experimentation phase to examine the proposed mechanism in different workloads. The first phase of the evaluation process describes how the proposed mechanism can be used to minimize the execution time of jobs. The second phase of the evaluation process compares the proposed mechanism with First Come First Serves (FCFS) algorithm. The results revealed that the proposed mechanism minimizes the execution time significantly. Furthermore, the proposed mechanism outperformed the FCFS algorithm.

Job Shop 일정계획 문제 풀이를 위한 유전 알고리즘의 복호화 방법

김준우 ( Kim Jun Woo ) 한국정보시스템학회 2016 情報시스템硏究 Vol.25 No.4

Purpose 생산 일정계획 문제의 해법들은 일반적으로 총처리시간이 짧은 active 스케줄에 초점을 맞추어 해를 탐색하는 경우가 많다. 그러나 active 스케줄은 semi active 스케줄에 비해 생성하는 것이 까다롭기 때문에, 일정계획을 생성하는데 소요되는 계산 비용을 감안하면 semi active 스케줄을 적절히 활용하는 것이 도움이 될 수 있다. 이에, 본 논문에서는 동일한 생산 일정계획 문제에 active 스케줄기반 탐색 방법과 semi active 스케줄 기반 탐색 방법을 적용함으로써 이들의 성능을 비교해보고자 하였다. Design/methodology/approach 각 공정들의 작업장 할당 순서를 의미하는 permutation encoding 기반 유전 알고리즘을 고전적인 job shop 일정계획 문제에 적용하기 위해 본 논문에서는 active 스케줄 복호화 및 semi active 스케줄 복호화의 두 가지 복호화 방법을 소개하였으며, 이들은 공정들의 순열로부터 실행가능한 스케줄을 얻는데 사용되었다. Findings semi active 스케줄 기반 유전 알고리즘은 active 스케줄 기반 유전 알고리즘에 비해 최적해를 탐색하는데 소요되는 반복 횟수가 좀 더 많은 경향이 있었으나, 알고리즘 실행 시간을 훨씬 짧았다. 나아가, semi active 스케줄 복호화는 그 절차가 단순하여 이해하고 구현하기 용이하다는 장점이 있었다. 따라서, 효과적인 해 탐색 전략이 주어지는 경우에는 semi active 스케줄에 기반한 해법이 일정계획 문제 풀이에 도움이 될 수도 있을 것으로 보여진다. Purpose The conventional solution methods for production scheduling problems typically focus on the active schedules, which result in short makespans. However, the active schedules are more difficult to generate than the semi active schedules. In other words, semi active schedule based search strategy may help to reduce the computational costs associated with production scheduling. In this context, this paper aims to compare the performances of active schedule based and semi active schedule based search methods for production scheduling problems. Design/methodology/approach Two decoding approaches, active schedule decoding and semi active schedule decoding, are introduced in this paper, and they are used to implement genetic algorithms for classical job shop scheduling problem. The permutation representation is adopted by the genetic algorithms, and the decoding approaches are used to obtain a feasible schedule from a sequence of given operations. Findings The semi active schedule based genetic algorithm requires slightly more iterations in order to find the optimal schedule, while its execution time is quite shorter than active schedule based genetic algorithm. Moreover, the operations of semi active schedule decoding is easy to understand and implement. Consequently, this paper concludes that semi active schedule based search methods also can be useful if effective search strategies are given.

Dispatching Rule based Job-Shop Scheduling Algorithm with Delay Schedule for Minimizing Total Tardiness

Jae-Gon Kim(김재곤),June-Young Bang(방준영) 한국산업경영시스템학회 2019 한국산업경영시스템학회지 Vol.42 No.1

This study focuses on a job-shop scheduling problem with the objective of minimizing total tardiness for the job orders that have different due dates and different process flows. We suggest the dispatching rule based scheduling algorithm to generate fast and efficient schedule. First, we show the delay schedule can be optimal for total tardiness measure in some cases. Based on this observation, we expand search space for selecting the job operation to explore the delay schedules. That means, not only all job operations waiting for process but also job operations not arrived at the machine yet are considered to be scheduled when a machine is available and it is need decision for the next operation to be processed. Assuming each job operation is assigned to the available machine, the expected total tardiness is estimated, and the job operation with the minimum expected total tardiness is selected to be processed in the machine. If this job is being processed in the other machine, then machine should wait until the job arrives at the machine. Simulation experiments are carried out to test the suggested algorithm and compare with the results of other well-known dispatching rules such as EDD, ATC and COVERT, etc. Results show that the proposed algorithm, MET, works better in terms of total tardiness of orders than existing rules without increasing the number of tardy jobs.

지연 스케쥴을 허용하는 납기최소화 잡샵 스케쥴링 알고리즘

김재곤,방준영 한국산업경영시스템학회 2019 한국산업경영시스템학회지 Vol.42 No.1

This study focuses on a job-shop scheduling problem with the objective of minimizing total tardiness for the job orders that have different due dates and different process flows. We suggest the dispatching rule based scheduling algorithm to generate fast and efficient schedule. First, we show the delay schedule can be optimal for total tardiness measure in some cases. Based on this observation, we expand search space for selecting the job operation to explore the delay schedules. That means, not only all job operations waiting for process but also job operations not arrived at the machine yet are considered to be scheduled when a machine is available and it is need decision for the next operation to be processed. Assuming each job operation is assigned to the available machine, the expected total tardiness is estimated, and the job operation with the minimum expected total tardiness is selected to be processed in the machine. If this job is being processed in the other machine, then machine should wait until the job arrives at the machine. Simulation experiments are carried out to test the suggested algorithm and compare with the results of other well-known dispatching rules such as EDD, ATC and COVERT, etc. Results show that the proposed algorithm, MET, works better in terms of total tardiness of orders than existing rules without increasing the number of tardy jobs.

동적 Job Shop 일정계획을 위한 유전 알고리즘

박병주,최형림,김현수,이상완 한국경영과학회 2002 韓國經營科學會誌 Vol.27 No.2

Manufacturing environments in the real world are subject to many sources of change and uncertainty, such as new job releases, job cancellations, a change in the processing time or start time of some operation. Thus, the realistic scheduling method should properly reflect these dynamic environment. Based on the release times of jobs, JSSP (Job Shop Scheduling Problem) can be classified as static and dynamic scheduling problem. In this research, we mainly consider the dynamic JSSP with continually arriving jobs. The goal of this research is to develop an efficient scheduling method based on GA (Genetic Algorithm) to address dynamic JSSP, we designed scheduling method based on SGA (Single Genetic Algorithm) and PGA (Parallel Genetic Algorithm). The scheduling method based on GA is extended to address dynamic JSSP. Then, this algorithms are tested for scheduling and rescheduling in dynamic JSSP. The results is compared with dispatching rule. In comparison to dispatching rule, the GA approach produces better scheduling performance.

계산 그리드를 위한 서비스 예측 기반의 작업 스케줄링 모델

장성호,이종식,Jang Sung-Ho,Lee Jong-Sik 한국시뮬레이션학회 2005 한국시뮬레이션학회 논문지 Vol.14 No.3

Grid computing is widely applicable to various fields of industry including process control and manufacturing, military command and control, transportation management, and so on. In a viewpoint of application area, grid computing can be classified to three aspects that are computational grid, data grid and access grid. This paper focuses on computational grid which handles complex and large-scale computing problems. Computational grid is characterized by system dynamics which handles a variety of processors and jobs on continuous time. To solve problems of system complexity and reliability due to complex system dynamics, computational grid needs scheduling policies that allocate various jobs to proper processors and decide processing orders of allocated jobs. This paper proposes a service prediction-based job scheduling model and present its scheduling algorithm that is applicable for computational grid. The service prediction-based job scheduling model can minimize overall system execution time since the model predicts the next processing time of each processing component and distributes a job to a processing component with minimum processing time. This paper implements the job scheduling model on the DEVS modeling and simulation environment and evaluates its efficiency and reliability. Empirical results, which are compared to conventional scheduling policies, show the usefulness of service prediction-based job scheduling.

Deadline Constrained Adaptive Multilevel Scheduling System in Cloud Environment

( Dinesh Komarasamy ),( Vijayalakshmi Muthuswamy ) 한국인터넷정보학회 2015 KSII Transactions on Internet and Information Syst Vol.9 No.4

In cloud, everything can be provided as a service wherein a large number of users submit their jobs and wait for their services. Thus, scheduling plays major role for providing the resources efficiently to the submitted jobs. The brainwave of the proposed work is to improve user satisfaction, to balance the load efficiently and to bolster the resource utilization. Hence, this paper proposes an Adaptive Multilevel Scheduling System (AMSS) which will process the jobs in a multileveled fashion. The first level contains Preprocessing Jobs with Multi-Criteria (PJMC) which will preprocess the jobs to elevate the user satisfaction and to mitigate the jobs violation. In the second level, a Deadline Based Dynamic Priority Scheduler (DBDPS) is proposed which will dynamically prioritize the jobs for evading starvation. At the third level, Contest Mapping Jobs with Virtual Machine (CMJVM) is proposed that will map the job to suitable Virtual Machine (VM). In the last level, VM Scheduler is introduced in the two-tier VM architecture that will efficiently schedule the jobs and increase the resource utilization. These contributions will mitigate job violations, avoid starvation, increase throughput and maximize resource utilization. Experimental results show that the performance of AMSS is better than other algorithms.

A Coevolutionary Bacterial Foraging Model Using PSO in Job-Shop Scheduling Environments

Liang Sun,Hongwei Ge,Limin Wang 보안공학연구지원센터 2016 International Journal of Grid and Distributed Comp Vol.9 No.9

The optimization of job-shop scheduling is very important because of its theoretical and practical significance. In this paper, a computationally effective approach of combining bacterial foraging strategy with particle swarm optimization for solving the minimum makespan problem of job shop scheduling is proposed. In the artificial bacterial foraging system, a novel chemotactic model is designed to address the job shop scheduling problem and a mechanism of quorum sensing and communication are presented to improve the foraging performance. In the particle swarm system, a novel concept for the distance and velocity of a particle is presented to pave the way for the job-shop scheduling problem. The proposed coevolutionary algorithm effectively exploits the capabilities of distributed and parallel computing of swarm intelligence approaches. The algorithm is examined using a set of benchmark instances with various sizes and levels of hardness and compared with other approaches reported in some existing literatures. The computational results validate the effectiveness of the proposed algorithm.

ERG요인이 조직유효성에 미치는 영향에 대한 조절효과 연구 -한,중 아르바이트 대학생의 경우-

이매결 ( Mei Jie Li ),이금희 ( Jin Xi Michelle Li ),권순식 ( Soon Sik Kwon ) 한국인적자원관리학회 2015 인적자원관리연구 Vol.22 No.1

An increasing number of college students are engaging in part time jobs because of the current unemployment crisis, increased desire of consumption and growth in the service industries. However, they have encountered many difficulties such as poor work environment, poor pay, and delay in payment of wages as well as stress from both work and study. This paper aims to identify the factors affecting their job attitudes and behaviors (organizational effectiveness) and thus to provide some practical guidelines for employers hiring them and universities where they study. The paper also aims to investigate the differences in job attitudes and behaviors of Korean and Chinese student workers as well as of voluntary and involuntary workers. Around 20 Korean and Chinese student workers were randomly selected for interview to select the variables that best represent the research context. The variables, duly sorted by different human needs under ERG theory, were assumed to predict their job attitudes and behaviors (organizational effectiveness), and included Job Autonomy, Schedule Flexibility, Relations with Supervisors, Relations with Customers, and Role Conflict for Study. The sample of our respondents was 303 Korean and Chinese student workers in G University in Korea: 201 Korean and 102 Chinese. We used SPSS 21.0 for statistical analysis. Our study reveals useful results for the development of theories and for organizational and welfare practices. First of all, Job Autonomy, Relations with Supervisors, and Schedule Flexibility have a significant effect on Job Satisfaction and Organizational Citizenship Behavior. It means employers should give student workers more job autonomy and allow them to be more flexible on their work schedule. Employers also need to maintain a harmonious relationship with student workers by avoiding verbal abuse, giving them more recognition, and trying to accept their good ideas. Secondly, Relations with Supervisors, Relations with Customers, and Role Conflict for Study have a significant effect on Turnover. It means universities should provide more scholarship or part-time jobs for students to help them overcome the problems of role conflict between work and study (on-campus jobs could reduce the role conflict because they normally have less of a work load than off-campus jobs). Besides, employers need to teach student workers how to maintain a harmonious relationship with their customers. Thirdly, Schedule Flexibility has a bigger effect on Turnover for voluntary workers (than involuntary workers) and Korean workers (than Chinese workers). It means ScheduleFlexibility is more important for voluntary workers and Korean workers. Therefore, employers should allow voluntary workers and Korean workers to be more flexible on their work schedule. Fourthly, Job Autonomy has a bigger effect on Organizational Citizenship Behavior for involuntary workers (than voluntary workers), and Relations with Customers has a bigger effect on voluntary workers (than involuntary workers). It means Job Autonomy is more important for involuntary workers and Relations with Customers is more important for voluntary workers. Therefore, employers should be more concerned about job autonomy of involuntary workers and should give them more job autonomy. Employers also need to take care of voluntary workers’ customer relationships and need to teach them how to deal with tricky customers. Lastly, workers with higher seniority tend to have more positive job attitudes and behaviors, and workers with older age tend to be more negative about their jobs. Therefore, hiring workers with more experience and younger age could improve organizational effectiveness. Future research needs to use different samples, such as student workers in other ethnic groups or in other countries as well as temporary workers or contract workers, to verify the research model in this study.

ERG요인이 조직유효성에 미치는 영향에 대한 조절효과 연구 - 한·중 아르바이트 대학생의 경우 -

이매결,이금희,권순식 한국인적자원관리학회 2015 인적자원관리연구 Vol.22 No.1

취업난, 소비욕구의 증가, 서비스업의 발달 등으로 인해 아르바이트를 하는 학생의 수가 대폭 증가하고 있다. 하지만 이들은 열악한 근무환경과 저임금, 임금체불 및 학업과 일을 병행해야 하는 스트레스 등 많 은 어려움을 겪고 있다. 본 연구는 아르바이트 대학생들의 직무태도나 행동(조직유효성)에 영향을 주는 요인들을 밝혀냄으로써 이들을 고용한 업체나 대학에 실무적 시사점을 제공하는데 목적이 있다. 본 연구 에서는 한국학생과 중국학생 및 자발과 비자발 근로자에 따른 조직유효성의 차이를 알아보기 위해 인종 과 자발성 요인의 조절효과를 분석하였다. 본 연구는 20명 정도의 아르바이트생들을 면담 조사한 결과에 기초해 연구대상을 가장 잘 반영하는 변수들을 선정하였으며, ERG이론을 이론적 틀로 한 분석모형을 구성하였다. 연구대상은 대학생 303명(한국학생 201명, 중국인 유학생 102명)이며 SPSS 21.0프로그램을 사 용하여 위계적 회귀분석을 실시하였다. 분석 결과, 직무 자율성과 스케줄 조정 가능성은 모두 직무만족과 조직시민행동에 유의한 정(+)의 영향을, 상사와의 조화롭지 못한 관계는 직무만족과 조직시민행동에 모 두 유의한 부(-)의 영향을 미쳤다. 또한 상사 및 고객과의 조화롭지 못한 관계 그리고 학업과의 역할갈등 은 모두 이직의도에 유의한 정(+)의 영향을 미치는 것으로 나타났다. 한편 자발성 요인은 직무 자율성과 조직시민행동 간의 관계, 고객과의 관계와 조직시민행동 간의 관계, 스케줄 조정 가능성과 이직의도 간의 관계 등에서 조절효과가 있는 것으로 나타났다. 즉 직무 자율성이 조직시민행동에 미치는 영향은 비자발 적으로 아르바이트를 하는 학생이 자발적으로 아르바이트를 하는 학생보다 높게 나타났다. 그리고 고객 과의 관계가 조직시민행동에 미치는 영향과 스케줄 조정 가능성이 이직의도에 미치는 영향 모두에서 자 발적으로 아르바이트를 하는 학생이 비자발적으로 아르바이트를 하는 학생보다 높게 나타났다. 마지막으 로, 인종은 스케줄 조정 가능성과 이직의도 간의 관계에서 조절작용을 하는 것으로 나타났다. 스케줄 조정 가능성이 이직의도에 미치는 영향은 한국학생이 중국학생보다 높게 나타났다. An increasing number of college students are engaging in part time jobs because of the current unemployment crisis, increased desire of consumption and growth in the service industries. However, they have encountered many difficulties such as poor work environment, poor pay, and delay in payment of wages as well as stress from both work and study. This paper aims to identify the factors affecting their job attitudes and behaviors (organizational effectiveness) and thus to provide some practical guidelines for employers hiring them and universities where they study. The paper also aims to investigate the differences in job attitudes and behaviors of Korean and Chinese student workers as well as of voluntary and involuntary workers. Around 20 Korean and Chinese student workers were randomly selected for interview to select the variables that best represent the research context. The variables, duly sorted by different human needs under ERG theory, were assumed to predict their job attitudes and behaviors (organizational effectiveness), and included Job Autonomy, Schedule Flexibility, Relations with Supervisors, Relations with Customers, and Role Conflict for Study. The sample of our respondents was 303 Korean and Chinese student workers in G University in Korea: 201 Korean and 102 Chinese. We used SPSS 21.0 for statistical analysis. Our study reveals useful results for the development of theories and for organizational and welfare practices. First of all, Job Autonomy, Relations with Supervisors, and Schedule Flexibility have a significant effect on Job Satisfaction and Organizational Citizenship Behavior. It means employers should give student workers more job autonomy and allow them to be more flexible on their work schedule. Employers also need to maintain a harmonious relationship with student workers by avoiding verbal abuse, giving them more recognition, and trying to accept their good ideas. Secondly, Relations with Supervisors, Relations with Customers, and Role Conflict for Study have a significant effect on Turnover. It means universities should provide more scholarship or part-time jobs for students to help them overcome the problems of role conflict between work and study (on-campus jobs could reduce the role conflict because they normally have less of a work load than off-campus jobs). Besides, employers need to teach student workers how to maintain a harmonious relationship with their customers. Thirdly, Schedule Flexibility has a bigger effect on Turnover for voluntary workers (than involuntary workers) and Korean workers (than Chinese workers). It means Schedule Flexibility is more important for voluntary workers and Korean workers. Therefore, employers should allow voluntary workers and Korean workers to be more flexible on their work schedule. Fourthly, Job Autonomy has a bigger effect on Organizational Citizenship Behavior for involuntary workers (than voluntary workers), and Relations with Customers has a bigger effect on voluntary workers (than involuntary workers). It means Job Autonomy is more important for involuntary workers and Relations with Customers is more important for voluntary workers. Therefore, employers should be more concerned about job autonomy of involuntary workers and should give them more job autonomy. Employers also need to take care of voluntary workers’ customer relationships and need to teach them how to deal with tricky customers. Lastly, workers with higher seniority tend to have more positive job attitudes and behaviors, and workers with older age tend to be more negative about their jobs. Therefore, hiring workers with more experience and younger age could improve organizational effectiveness. Futureresearch needs to use different samples, such as student workers in other ethnic groups or in other countries as well as temporary workers or contract workers, to verify the research model in this study.