الگوریتم های هیوریستیک و دقیق برای برنامه ریزی موازی ماشین با اثر یادگیری دی جانگ

We consider a parallel-machine scheduling problem with a learning effect and the makespan objective. The impact of the learning effect on job processing times is modelled by the general DeJong’s learning curve. For this NPNP-hard problem we propose two exact algorithms: a sequential branch-and-bound algorithm and a parallel branch-and-bound algorithm. We also present the results of experimental evaluation of these algorithms on a computational cluster. Finally, we use the exact algorithms to estimate the performance of two greedy heuristic scheduling algorithms for the problem.

Scheduling problems concerning multi-machine production environments are encountered in many modern manufacturing processes (Leung, 2004 and Pinedo, 2008). Since the classical scheduling theory (Conway, Maxwell, & Miller, 1967) turned out to be too rigid for some of these environments, the theory started to evolve in early 1990s. This led to a rise of new scheduling models such as, e.g., scheduling with controllable job processing times (Shabtay & Steiner, 2007), scheduling jobs with time-dependent processing times (Gawiejnowicz, 2008) and multiprocessor task scheduling (Drozdowski, 2009). An important group of such new scheduling models constitute scheduling models with the so-called learning effect (Biskup, 2008) that we consider in this paper. The impact of the learning effect on production issues was first discussed in 1936 by Wright (Biskup, 2008), who observed that learning may decrease the processing times of production tasks in the aircraft industry. The observation was later confirmed by many empirical studies saying that the knowledge of a learning curve during the planning process may result in cost savings in manufacturing, industrial production and software engineering (Badiru, 1992, Globerson and Seidmann, 1988 and Raccoon, 1995). A general learning effect is modelled in scheduling theory by assumption that the processing time of a job is a function of the job position in a schedule. In literature there are known different models of the learning effect that lead to distinct forms of the function (see, e.g., Bachman and Janiak, 2004, Biskup, 2008, Dondeti and Mohanty, 1998 and Gawiejnowicz, 1996, for details). Thus, since the learning effect allows to take into account human factors in scheduling, the problems similar to the mentioned above belong to intensively studied topics in scheduling research (Lodree, Geiger, & Jiang, 2009). Throughout the paper, we will consider the following scheduling problem with a learning effect. There is given a set of jobs J1, J2, … , Jn which have to be processed on machines M1, M2, … , Mm. All jobs are available for processing at time 0 and job preemption is not allowed. The processing time of job Jj is described by DeJong’s learning curve, pj,r = pj(M + (1 − M)ra), where pj is the initial job processing time, a ⩽ 0 is the learning index, M is the incompressibility factor, r is the current position of a job in a given schedule and 1 ⩽ j,r ⩽ n. To the best of our knowledge, no scheduling problems with this form of a learning effect have been considered earlier. Function pj,r, introduced by DeJong (Badiru, 1992), mirrors the impact of a learning effect on job processing times and is a generalization of both the log-linear learning curve, pj,r = pjra, and the case of fixed job processing times, pj,r = pj. (The first case is obtained for M = 0, while the second one for M = 1.) The main advantage of DeJong’s model follows from the fact that parameter M represents the part of job processing time that is limited by some conditions and cannot be shortened. Different values of M are recommended in literature. For example, DeJong suggests M = 0.25 for labour-intensive jobs and M = 0.5 for machine-intensive jobs (Raccoon, 1995). Throughout the paper, we assume that M ∈ [0, 1]. The criterion of schedule optimality in our problem is to minimize the makespan, Cmax: = max{Cj:1 ⩽ j ⩽ n}, where Cj is the completion time of job Jj. Extending the three-field notation (Graham, Lawler, Lenstra, & Rinnooy Kan, 1979), we will denote the problem as Pm∣pj,r = pj(M + (1 − M)ra)∣Cmax. The contribution of the paper is threefold. First, we prove some basic properties of the problem. Next, on the basis of the properties, we propose for this problem two exact algorithms: a sequential branch-and-bound algorithm and a parallel branch-and-bound algorithm. To the best of our knowledge, no branch-and-bound algorithms for parallel-machine scheduling problems with a learning effect have been proposed earlier. We also present the results of experiments conducted on a computational cluster in order to evaluate the quality of schedules generated by our exact algorithms. Finally, we discuss the application of two greedy heuristic scheduling algorithms for the problem, comparing schedules generated by the heuristics with schedules generated by the branch-and-bound algorithms. The remainder of the paper is organized as follows. In Section 2, we present a brief review of recent research on multi-machine scheduling with a learning effect. In Section 3, we prove basic properties of the considered problem. In Sections 4 and 5, we describe the sequential and the parallel branch-and-bound algorithm for the problem, respectively. In Section 6 we discuss two greedy heuristic scheduling algorithms for the problem. In Section 7, we present the results of computational experiments conducted on a computational cluster for both the exact algorithms and the greedy scheduling algorithms. We complete the paper by Section 8 with conclusions and remarks about future research.

In this paper, we considered a parallel-machine scheduling problem with DeJong’s learning effect and the objective to minimize the makespan. We proved basic properties of the problem and gave some lower and upper bounds on the optimal value of the objective. We also proposed for solving the problem two exact algorithms, a sequential branch-and-bound algorithm and a parallel branch-and-bound algorithm, and two greedy heuristic algorithms. Finally, we reported the results of computational experiments conducted in order to evaluate the performance of the proposed branch-and-bound algorithms and the greedy heuristics. In future research more tight lower and upper bounds on the optimal makespan value should be determined. This would allow to solve by the branch-and-bound algorithms larger instances in a reasonable time.