A Monte Carlo Simulation based Chaotic Differential Evolution Algorithm for
Scheduling a Stochastic Parallel Processor System
Hadi Mokhtari, Ali Salmasnia
Reference: ESWA 10034
To appear in: Expert Systems with Applications
Please cite this article as: Mokhtari, H., Salmasnia, A., A Monte Carlo Simulation based Chaotic Differential
Evolution Algorithm for Scheduling a Stochastic Parallel Processor System, Expert Systems with Applications (2015), doi: http://dx.doi.org/10.1016/j.eswa.2015.05.015
This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting proof before it is published in its final form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain. 1
A Monte Carlo Simulation based
Chaotic Differential Evolution
Algorithm for Scheduling a
Stochastic Parallel Processor
Department of Industrial Engineering, Faculty of Engineering, University of Kashan, Kashan, Iran (firstname.lastname@example.org)
Department of Industrial Engineering, Faculty of Engineering and Technology, University of Qom, Qom, Iran
Abstract. One of the main limitation of the application of evolutionary algorithms (EA) is the tendency to converge prematurely to a local optimum. The
EAs suffer with the disadvantage of premature convergence and hence the study on convergence of EAs is always one of the most important research fields. Due to outstanding capability of chaos to avoid being trapped in local optimum, it can be considered as an efficient search tool. Therefore, in current paper, in order to taking properties of chaos, eight chaotic maps are employed within a differential evolution (DE) algorithm for solving a stochastic job scheduling problem. To speedup searching and avoid local optimum traps, the random sequences produced from chaotic maps are utilized instead of random variables in DE.
Furthermore, to address the uncertainties arising in scheduling environments,
Monte Carlo simulation is used. However, simulation is not an optimization approach. Therefore, we design the simulation-based optimization approach where a simulator is combined with chaotic DE. The simulation experiments are used to evaluate the quality of candidate solutions and the chaotic DE is utilized to find best-compromised solutions and then guide the search direction. The performance of simulation-based chaotic DE algorithm is investigated in a computational study, and the results show the outperformance of suggested method with respect to the traditional methods.
Keywords: Chaos Theory; Chaotic Maps; Simulation-based Optimization;
Differential Evolution; Parallel Processor System Scheduling. 2 1. Introduction and Related Works
Among scheduling problems addressed in literature, production scheduling with parallel processors has been a subject of interest by researchers and practitioners for a long time (Chang et al 2005). In fact, any situations with a series of processing units and a set of jobs to be carried out on units are real-life examples of such problem (Ying and Cheng 2010). Scheduling of jobs on parallel processors leads to a major operational problem for running a time-sharing system.
Moreover, it is a generalization of the single processor problem and of a particular case of problems arising in flexible manufacturing systems (Balin 2011). This problem can be classified into three main groups (Cevikcan et al 2011): (i)
Identical parallel processor scheduling problem, where processing times are same for each processor, (ii) Uniform parallel processor scheduling problem, where processors have a parametric relationship in terms of processing time differences, and (iii) Unrelated parallel processor scheduling problem, where processing time differences among processors cannot be expressed in a parametric relationship.
Generally, parallel processor scheduling problem has many real-world applications, particularly, in semiconductor industry, wafer probing and integrated circuit (IC) manufacturing (Pearn et al., 2002). 1.1 Parallel Processor Scheduling Problem
The first paper on parallel processor scheduling is presented by McNaughton (1959), where three performance criteria were introduced for parallel-identicalprocessors. The measures are: makespan, total weighted tardiness and total weighted flow time. Hu (1961) presented a label scheduling algorithm entitled critical path method, to solve a set of non-preemptive jobs on parallel environment. Afterwards, Chen and Liu (1975) generalized Hu's method to 3 address the non-preemptive partial order unit jobs on an arbitrary number of processors. Moreover, Fujii et al. (1969, 1971) investigated such problem with a set of unit jobs and arbitrary precedence relations. In order to minimize either the makespan or flow time, Weber (1982) studied identical parallel machines with the exponential probability distribution of processing times.
Afterwards, many researchers have investigated the problem under different assumptions. Arnaout et al. (2006) considered a stochastic parallel machine scheduling problem to minimize total weighted mean completion time and developed a heuristic solution method. Ying and Cheng (2010) developed an iterated greedy heuristic for dynamic parallel processor scheduling problem and extensive computational experiments were implemented to indicate its effectiveness as opposed to state-of-the-art algorithms. In addition, an integration of parts design characteristics and scheduling on parallel processors was presented by Cevikcan et al (2011) in order to reduce the total set up times. To make the proposed methodology compatible with cable sequencing, an expert system is developed by the authors so as to reduce the burden of supervisors and improve effectiveness. Moreover, Behnamian et al (2009) developed a hybrid algorithm based on ant colony optimization (ACO), simulated annealing (SA), and variable neighborhood search (VNS) metaheuristics for a kind of parallel processor scheduling with sequence-dependent set up times. In order to minimize the makespan, an initial population generation method based on ACO, a SA for solution evolution, and a VNS which involves three local search procedures to improve the population. A two-phase sub population genetic algorithm is devised in another study by Chang et al (2005) for solving traditional problem of scheduling with parallel processors. Balin (2011) describes a special case of parallel processors with non-identical parallel processors and applies the genetic algorithm to solve it. 4