متا هیوریستیک برای برنامه ریزی ماشین آلات موازی با تقسیم کار برای به حداقل رساندن تاخیر در کل

Parallel machine scheduling is a popular research area due to its wide range of potential application areas. This paper focuses on the problem of scheduling n independent jobs to be processed on m identical parallel machines with the aim of minimizing the total tardiness of the jobs considering a job splitting property. It is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. We present a mathematical model for this problem. The problem of total tardiness on identical parallel machines is NP-hard. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using an optimization solver is extremely difficult. We propose two meta-heuristics: Tabu search and simulated annealing. Computational results are compared on random generated problems with different sizes.

Parallel machine scheduling (PMS) has been a popular research area due to its wide range potential application areas. This popularity has been increased considerably during recent years by the emergence of parallel processor computer technology [1]. A bank of machines in parallel is a setting that is important from both the theoretical and practical points of view. From the theoretical viewpoint, it is a generalization of the single machine, and a special case of the flexible flow shop. From the practical point of view, it is important because the occurrence of resources in parallel is common in the real-world. Furthermore, techniques for machines in parallel are often used in decomposition procedure for multistage systems [2]. One may consider parallel machine scheduling as a two-step process. First, one has to determine which jobs are to be allocated to which machines; second, one has to determine the sequence of the jobs allocated to each machine. With the makespan objective only the allocation process is important [2]. Although problems with due date-related performance measures were studied in many research articles, not much progress has been made for the objective of minimizing total tardiness in parallel machine scheduling problems except for special cases of identical parallel machines [3]. Furthermore, since it is not easy to obtain optimal solutions for parallel machine tardiness problems of a practical size, researchers have focused on the development of heuristic algorithms [4]. There are very few research results on the parallel machine scheduling problem with job-splitting properties. Serafini [5], studied cases in which each job can be split arbitrarily (into sub-jobs of continuous units, not discrete units) and processed independently on uniform or unrelated parallel machines and give heuristic algorithms for the objective of minimizing the maximum weighed tardiness. For an identical processor problem in which each job can be split arbitrarily, Xing and Zhang [6] propose a heuristic algorithm for the objective of minimizing makespan and analyze the worst case performance of the algorithm. Tahar et al. [7] presented a method based on linear programming for identical parallel machine scheduling with job splitting and sequence-dependent setup times. Kim et al. [4], studied cases in which each job can be split into a discrete number of sub-jobs and they are processed on a parallel machine independently. They suggested a two-phase heuristic algorithm for the parallel machine scheduling problem with a job splitting property for the objective of minimizing total tardiness. Shim and Kim [3] suggested a B&B algorithm for the identical machine scheduling problem with the objective of minimizing total tardiness considering the job splitting property described by Kim et al. [4]. They developed dominance properties and lower bounds and used them in their B&B algorithm. Results of their computational experiments showed that their suggested algorithm was able to find optimal solutions for problems with up to four machines and 12 jobs (and five machines and eight jobs) in a reasonable amount of CPU time. According to this paper, one can devise heuristic algorithms that give very good solutions for large problems within a reasonably short computation time. Although job splitting reduces flow times or completion times of certain jobs, it increases overall set-up frequency and delays completion of other jobs. In other words, the more sub-jobs into which a job is split, the shorter the flow time of the job tends to become, since those sub-jobs can be processed simultaneously on different machines. However, more set-ups may be required if there are more sub-jobs. Hence, in the scheduling problem considered in this study, it is very important to find an appropriate number of sub-jobs to be split from each job [4]. In this paper, we focus on the problem of scheduling n independent jobs on m identical parallel machines with the objective of minimizing total tardiness of the jobs considering a job splitting property. It is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. The problem is formulated as a mixed integer programming model. The results of tabu search are compared with simulated annealing from the point of objective function values and CPU computation times. The remainder of this paper is organized as follows. In the next section, we introduce the identical parallel machine scheduling problem and the problem is formulated as a mixed integer programming model. The problem is solved by tabu search and simulated annealing algorithm in Section 3. The effectiveness of the algorithms is examined in Section 4 by several computational experiments. Finally, our results are summarized in Section 5.

This study dealt with the scheduling problem of identical parallel machines with splitting jobs. First, the problem is formulated by using a mixed integer programming model. The practical and industrial applications of tardiness problem are considerable. The problem is NP-hard, meaning the problem cannot be solved in polynomial time as n gets large. Quite often the time required to solve such a problem increases exponentially with respect to n. We proposed two meta-heuristics: simulated annealing and tabu search. The components of the proposed tabu search were defined such that they were suitable for the structure of the problem and then the parameter values peculiar to Tabu Search were determined by means of experimental design. Three groups test problems were solved by using the proposed tabu search and simulated annealing. The computational results have shown that SA has a better performance and consumes less time than TS. SA can be suggested as a better heuristic method than TS in considered problem. Considering the objective containing the due date, the meta-heuristics suggested in this paper may be useful for today’s customer-oriented market environments in which meeting due dates is considered as an important criterion, since they are devised to deal with a due date based objective and give good solutions very quickly