Search

Cloud providers deliver heterogeneous virtual machines to run complicated jobs submitted by users. The task scheduling issue is formulated to a discrete optimization problem which is well-known NP-Hard. This paper presents a hybrid meta-heuristic algorithm based on genetic and thermodynamic simulated annealing algorithms to solve this problem. In the proposed algorithm, the genetic and simulated annealing algorithms have respective global and local search inclinations covering each other's shortcomings. A novel theorem is presented and applied to produce a semi-conducted initial population. In a used genetic algorithm with a global trend, the crossover operator is performed to explore search space. The thermodynamic simulated annealing algorithm is utilized to improve the efficiency, which considers entropy and energy difference concepts in the cooling schedule process. After obtaining a suitable solution, one of the three novel neighbor operators is randomly called to enhance the given solution potentially. In this way, the efficient balance between exploration and exploitation in the search space is achieved. Simulation results prove that the proposed hybrid algorithm has 10.17%, 9.31%, 7.76%, and 8.21% dominance in terms of makespan, schedule length ratio, speedup, and efficiency against other comparative algorithms. [ABSTRACT FROM AUTHOR]

Multi-objective evolutionary algorithms (MOEAs) have been successfully employed to solve many scientific and engineering problems. However, many algorithms perform ill in maintaining diversity and convergence simultaneously. In this paper, we devised a novel operator selection framework based on two collaborative indicators, generational distance (GD) and maximum spread (MS) to improve the diversity while maintaining a good convergence. By calculating the variation of GDs and MSs over the past 7 iterations, an instruction is conveyed to select a proper operator to execute next 7 iterations. This process is repeated until it reaches the maximum iteration. Two operators are embedded in this algorithm which are differential evolution operator (DE/rand/1) and our proposed crow search operator which is deemed to be efficient in explorating the search space. MOEA/D is utilized as the basis framework of our proposed algorithm. Experiments indicate that our proposed algorithm is valid and outperforms other famous algorithms in terms of diversity and convergence. In the end, a particular aeroengine maintenance scheduling problem is solved by our proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider a two parallel machine problem where each machine has a fixed and known unavailable period. The objective is to minimize the makespan. In the literature, the problem has been considered for the case in which there is only one unavailable period on either one of the machines. This paper extends the results to two unavailable periods, one for each machine. For each of the different cases of the problem, an algorithm is developed to find the optimal solution. Although all the proposed algorithms have exponential time complexities, they are quite efficient in solving large problems. Computational results for problems with up to 1000 jobs are reported. [ABSTRACT FROM AUTHOR]

In a scheduling problem, denoted by 1|prec|∑ C in the Graham notation, we are given a set of n jobs, together with their processing times and precedence constraints. The task is to order the jobs so that their total completion time is minimized. 1|prec|∑ C is a special case of the Traveling Repairman Problem with precedences. A natural dynamic programming algorithm solves both these problems in 2 n time, and whether there exists an algorithms solving 1|prec|∑ C in O( c) time for some constant c<2 was an open problem posted in 2004 by Woeginger. In this paper we answer this question positively. [ABSTRACT FROM AUTHOR]

The m-machine no-wait flowshop scheduling problem, with the objective of minimizing total completion time subject to the constraint that makespan has to be less than or equal to a certain value, is addressed in this paper. First, an algorithm is proposed to find an upper bound on the makespan in case the upper bound is not given or unknown. Given the upper bound on makespan, a proposed algorithm ( PAL) with five versions L (1, 5, 10, 15, and 20) and a genetic algorithm ( GA) are utilized for solving the problem. Furthermore, a dominance relation is established for the case of four machines. The five versions of PAL and GA are evaluated on randomly generated problems with different number of jobs and number of machines. Computational experiments show that the errors of PA10, PA15, and PA20 are much smaller than that of GA while the CPU times of PA10, PA15, and PA20 are significantly smaller than that of GA. Therefore, the algorithms PA10, PA15, and PA20 are superior to the GA algorithm. [ABSTRACT FROM AUTHOR]

This paper considers the single machine scheduling problem with a new version of time-dependent processing times. The processing time of a job is defined as a piecewise linear function of its start time. It is preferred that the processing of each job be started at a specific time which means that processing the job before or after that time implies additional effort to accomplish the job. The job-processing time is a nonmonotonic function of its start time. The increasing rate of processing times is job independent and the objective is to minimize the cycle time. We show that the optimal schedule is V shaped and propose an optimal polynomial time algorithm for the problem. [ABSTRACT FROM AUTHOR]

In order to obtain efficiency and flexibility, assignment of machines' layout and determination of jobs' schedule on each machine are among the most important decisions. These decisions are interrelated and may impact each other but they are often treated separately or as a sequential decision in prior researches. In this paper, we propose a new approach to concurrently make the layout and scheduling decisions in a job shop environment. In other words, we consider an extension of the well-known job shop scheduling problem with transportation delay in which in addition to decisions made in the classic problem, the locations of machines have to be selected among possible sites. The only goal of the problem is the minimization of the makespan. A hybrid metaheuristic approach based on the scatter search algorithm is developed to tackle this problem. Using 43 randomly generated benchmark instances, the performance of the scatter search and its components are evaluated. We also applied our procedure to the classic job shop scheduling problems. Computational results show that our procedure is efficient. [ABSTRACT FROM AUTHOR]

In this paper, we focus on real-life settings that require the development of new models of flowshop scheduling problems, where job processing times can increase with the number of processed jobs due to the aging effect and decrease by the allocation of additional resource. We analyse the makespan minimization flowshop problem with such model and also with the aging effect only. We prove that the considered problems and their special cases are still polynomially solvable under given conditions, and on their basis, we provide optimal polynomial time solution algorithms. [ABSTRACT FROM AUTHOR]

This paper presents a hybrid Pareto-based discrete artificial bee colony algorithm for solving the multi-objective flexible job shop scheduling problem. In the hybrid algorithm, each solution corresponds to a food source, which composes of two components, i.e., the routing component and the scheduling component. Each component is filled with discrete values. A crossover operator is developed for the employed bees to learn valuable information from each other. An external Pareto archive set is designed to record the non-dominated solutions found so far. A fast Pareto set update function is introduced in the algorithm. Several local search approaches are designed to balance the exploration and exploitation capability of the algorithm. Experimental results on the well-known benchmark instances and comparisons with other recently published algorithms show the efficiency and effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Generating schedules such that all operations are repeated every constant period of time is as important as generating schedules with minimum delays in all cases where a known discipline is desired or obligated by stakeholders. In this paper, a periodic job shop scheduling problem (PJSSP) based on the periodic event scheduling problem (PESP) is presented, which deviates from the cyclic scheduling. The PESP schedules a number of recurring events as such that each pair of event fulfills certain constraints during a given fixed time period. To solve such a hard PJSS problem, we propose a hybrid algorithm, namely PSO-SA, based on particle swarm optimization (PSO) and simulated annealing (SA) algorithms. To evaluate this proposed PSO-SA, we carry out some randomly constructed instances by which the related results are compared with the proposed SA and PSO algorithms as well as a branch-and-bound algorithm. In addition, we compare the results with a hybrid algorithm embedded with electromagnetic-like mechanism and SA. Moreover, three lower bounds (LBs) are studied, and the gap between the found LBs and the best found solutions are reported. The outcomes prove that the proposed hybrid algorithm is an efficient and effective tool to solve the PJSSP. [ABSTRACT FROM AUTHOR]

This paper considers group scheduling problem in hybrid flexible flow shop with sequence-dependent setup times to minimize makespan. Group scheduling problem consists of two levels, namely scheduling of groups and jobs within each group. In order to solve problems with this context, two new metaheuristics based on simulated annealing (SA) and genetic algorithm (GA) are developed. A design procedure is developed to specify and adjust significant parameters for SA- and GA-based metaheuristics. The proposed procedure is based on the response surface methodology and two types of objective function are considered to develop multiple-objective decision making model. For comparing metaheuristics, makespan and elapsed time to obtain it are considered as two response variables representing effectiveness and efficiency of algorithms. Based on obtained results in the aspect of makespan, GA-based metaheuristic is recommended for solving group scheduling problems in hybrid flexible flow shop in all sizes and for elapsed time SA-based metaheuristic has better results. [ABSTRACT FROM AUTHOR]