یک روش فرااکتشافی با عملکرد بسیار بالا برای زمان بندی تولید کارگاهی با زمان های راه اندازی وابسته به توالی

This paper investigates scheduling job shop problems with sequence-dependent setup times under minimization of makespan. We develop an effective metaheuristic, simulated annealing with novel operators, to potentially solve the problem. Simulated annealing is a well-recognized algorithm and historically classified as a local-search-based metaheuristic. The performance of simulated annealing critically depends on its operators and parameters, in particular, its neighborhood search structure. In this paper, we propose an effective neighborhood search structure based on insertion neighborhoods as well as analyzing the behavior of simulated annealing with different types of operators and parameters by the means of Taguchi method. An experiment based on Taillard benchmark is conducted to evaluate the proposed algorithm against some effective algorithms existing in the literature. The results show that the proposed algorithm outperforms the other algorithms.

Job shop scheduling (or JSS) is one of the most complicated combinatorial optimizations. A JSS could be described as follows: we have a set of n jobs need to be operated on a set of m machines [1]. Each job has its own processing route; that is, jobs visit machines in different orders. Each job might need to be performed only on a fraction of m machines, not all of them. The following assumptions are additionally characterized. Each job can be processed by at most one machine at a time and each machine can process at most one job at a time. When the process of an operation starts, it cannot be interrupted before the completion; that is, the jobs are non-preemptive. There is no transportation time between machines; in other words, when an operation of a job finishes, its operation on subsequent machine can immediately begin. The jobs are independent; that is, there are no precedence constraints among the jobs and they can be operated in any sequence. The jobs are available for their process at time 0. There is unlimited buffer between machines for semi-finished jobs; meaning that if a job needs a machine that is occupied, it waits indefinitely until it becomes available. There is no machine breakdown (i.e. machines are continuously available). The objective function when solving or optimizing a JSS is to determine the processing order of all jobs on each machine that minimizes the makespan. Numerous savings obtained by considering setup times in scheduling decisions prompted researchers to utilize this assumption in their studies [2]. Setup times are typically sequence-dependent (or SDST), that is, the magnitude of setup strongly depends on both current and immediately processed jobs on a given machine. For example, this may occur in a painting operation, where different initial paint colors require different levels of cleaning when being followed by other paint colors. We also assume that setup is non-anticipatory, meaning that the setup can only begin as soon as the job and the machine are both available. The sequence-dependent setup time job shop scheduling (SDST JSS) is defined as J/STsd/Cmax according to three-fold notation of Graham et al. [41]. The JSS is known to be an NP-hard optimization problem [3]. Therefore, effective metaheuristics for the JSS are necessary to find optimal or near optimal solutions in reasonable amount of time. This paper proposes such an algorithm, in the form of simulated annealing (or SA), for the problem under consideration. Many researchers in the field of scheduling conclude that SAs show inferior performance in comparison with other metaheuristics [4]; however, SAs have recently proved their efficiency and effectiveness in a wide variety of optimization problems [4], [5] and [6]. It is known that the performance of SAs strongly depends on the choice of its operators and parameters. Hence, beside presenting our operators, we explore the impact of different operators and parameters on the performance of SA by means of Taguchi method. Taguchi method is an optimization technique that brings robustness into experimental designs as well as being a cost-effective and labor-saving method [7] and [8]. It can simultaneously investigate several factors and define quickly those having significant effects on response variables by conducting a minimal number of possible experiments [9]. There are many successful applications of this approach at the parameter design stage in many fields [10]. The reminder of the paper is organized as follows. Section 2 reviews the literature of SDST JSS. Section 3 describes the proposed simulated annealing. The calibration of the proposed algorithm is presented in Section 4. In Section 5, experimental design and comparison of the proposed algorithm with existing methods are reported. Section 6 concludes the paper and provides some directions for future studies.

This paper studied job shop scheduling where the setup times were sequence-dependent. The optimization criterion was makespan. Considering scheduling problems with setup times is of interest among researchers because nowadays companies produce multiple goods on common resources and this ends up with the need for setup activities. Setup activities usually play a costly role in production processes. Therefore, planners should consider the principles of setup activities in their schedules. To tackle the problem, we apply a high performing metaheuristic, in the framework of simulated annealing, incorporating a novel neighborhood search structure. We investigated impacts of many operators and parameters (i.e. such as initial solution, cooling schedule, initial temperature and neighborhood search structure and, etc.) on the performance of SA. This extensive calibration was conducted through effective statistical tools, called Taguchi method, in order to exploit its advantages. The effectiveness of our new neighborhood search structure against the other existing ones was illustrated by the experimental results. To evaluate the performance of the proposed SA, we carried out a numerical experiment by which we compared the SA with some other existing algorithms (i.e. two different genetic algorithms, an immune algorithm and a variable neighborhood search) that showed their effectiveness in papers they were applied. The numerical experiment included a set of instances generated based on Taillard's benchmark. The results showed that the proposed SA outperformed the other metaheuristics taken from the literature. As a direction for future studies, it could be interesting to work on multi-objective cases of the problem and develop effective metaheuristics incorporating advanced features. Since realistic cases are of interest, consideration of other practical assumptions such as machine availability constraints or transportation times could be regarded as an impressive research.