رویکرد الگوریتم ژنتیک برای یک مسئله برنامه ریزی با استفاده از محدودیت های زمانی ویندوز

This study considers a cyclic scheduling of hoist movements in electroplating industry. Several jobs have to flow through a production line according to an ordered bath sequence. They firstly enter the line at a loading buffer. Then they will be soaked sequentially in a series of tanks containing specific chemical baths. Finally, they will leave the line at the unloading buffer. The processing time duration of each job in each tank is not constant but confined within a time window bounded by a minimum and a maximum duration. If a job spends less than the minimum duration or more than the maximum duration it is considered defective. Moreover, not only the job operations in the soaking tanks have to be scheduled, but also the transportation of the jobs between tanks has to be considered. The problem now is to find an optimum or near optimum feasible cyclic scheduling such that the hard resource and time-window constraints are respected and the cycle time duration is minimized. A mathematical formulation is proposed for the multi-jobs cyclic hoist scheduling problem with a single transportation resource, and a Genetic Algorithm (GA) approach is presented to solve it. The performance of the proposed algorithm is evaluated with the objective value obtained with a linear programming model, on several literature instances. Computational experiments show the good performance of our GA in terms of solution quality, convergence and computation time.

In recent years scheduling problem with transportation resources has gained much attention in the literature. Despite the differences between the several proposed models, they all deal with the coordination of material handling devices and classical problem scheduling decisions. In this section we review the most important research concerning the Cyclic Hoist Scheduling Problem (CHSP). This problem is a branch stemming of the Hoist Scheduling Problem (HSP). Since the first model given by Phillips and Unger (1976), several researchers have been interested in the Hoist Scheduling Problem (Manier and Bloch, 2003) and a large number of mathematical models (Spacek et al., 1999, Chen et al., 1998, Zhou and Ling, 2003 and Che and Chu, 2007) have been developed. Nevertheless, the cyclic problem and more precisely, the single-job cyclic schedule, was the most studied case in literature (Armstrong et al., 1996 and Manier et al., 2000) due to the strong complexity of the problem, even with a simple line configuration (single-job, single-hoist and single-capacity tanks). However, the problem is so complex that the most practical path consists of addressing the simplest cases, and then studying possible extensions. One of these extensions that we propose to study in this paper is the multi-parts jobs. For a given cyclic schedule, we have to minimize the cycle time duration for n different part-jobs. Each cycle is specified by a parameter n, called the cycle degree. In an n-degree cyclic schedule, exactly n parts enter and leave the production line every one cycle (Lei, 1994). The most known studies dealing with this extension are presented as follows. Ptuskin studied a multi-parts problem (single job problem, line with 50 tanks, nparts jobs and nop operations) denoted (CHSP|50/nc/|nparts/nps,nop|Cmax) according to the notation, elaborated by Manier and Bloch (2003) and dedicated to Hoist Scheduling Problems. In this problem, parts are processed according to the same sequence, with various processing times, where the sequence periodically alternates jobs of different parts and is known in advance. Moreover, the date of each part has to be computed. This problem is decomposed in several mono-product sub-problems and the solution corresponds to a common period (Ptuskin, 1995). Nevertheless, the obtained cyclic schedule is feasible but it is not guaranty to be optimal. Varnier and Jeunehomme used a branch and bound method for a similar multi-part problem (CHSP|mt//load-unload|/nps,nop|Tmin problem). A difference with Ptuskin (1995) is that the entry sequence of jobs (configuration) is not known in advance. Each level of the search tree consists in adding a possible state at the beginning of the cycle, which is called configuration. The possible schedules from this configuration constitute the branches of the search tree and then a linear program is achieved to check if the problem has a solution. If not, backtrack is allowed to consider the other schedules. However, Varnier and Jeunehomme mainly study the transition part of the schedule (Varnier and Jeunehomme, 2000). A branch and bound method has also been used by Mateo and Companys to study the CHSP|mt//diss|/2,2mt+2|Tmin for a two different part jobs problem. The branch and bound procedure builds the sequence of movements progressively. Each level of the search tree consists of adding one tank and thus, the stages to be done on it (stage is a new indexation used by authors to define the soaking operations). A linear program is then solved at each node to check the consistency of the constraint system. Nevertheless, this method cannot be easily extended to the general n-parts jobs (Mateo and Companys, 2006). Lei and Liu present first, a formal analysis of the hoist scheduling problem with two non-identical parts (CHSP|1,20,ct/|/42|Tmin). Then, the results are used to develop a new branch-and-bound procedure in order to find the optimal schedules. This procedure uses a depth search strategy. In each step, it chooses a node at the greatest depth to branch first. Whenever a tie is found, it chooses the one with the minimum lower bound to branch first. They state that each node at level k of their tree has two partial cycles. Then the minimum lower bound given by those two cycles is used as the lower bound of this node. For each newly generated node, authors use the result of their analysis to check its feasibility. If the offspring nodes are either infeasible or do not improve the best obtained lower bound, the node is eliminated and backtrack is allowed to its upper level. This procedure provides good computational results. Authors tested their procedure on mono-product benchmarks. They also randomly generated some test problems without really detailing them. But the efficiency and robustness of their procedure was not evaluated considering variations of hoist speed and width of time windows. Moreover, their model was dedicated to basic line configurations’ (single capacity resources …) and for 2-degree cyclic schedule (Lei and Liu, 2001). Many other studies deal with scheduling of the other production lines or even with the CHSP with relaxed constraints: mainly bounded processing times and no-wait constraints; which are problems near the CHSP (Fleury et al., 2001, Ge and Yih, 1995, Che et al., 2009, Che and Chu, 2005, Kats et al., 2006, Liu et al., 2002 and Song et al., 1995). A synthesized comparison between these works (dealing with the Multi-Parts CHSP) is presented in Table 1. Therefore, all of these works carried out on this issue, to date, have several limitations. Thus and in order to improve the electroplating line production, a general n-cyclic model could be developed by incorporating additional constraints to previous works.

This paper represents the first attempt to apply the technique of GA to solve the single hoist cyclic scheduling problem with time windows constraints and heterogeneous jobs. A new mixed integer linear programming model is proposed to minimize the cycle time for n different jobs. Due to the hardness of solving the proposed linear model for instances with large sizes, we firstly propose a conjunctive graph model for the problem. Then, we elaborate a polynomial procedure for computing the cycle time for a fixed cyclic schedule. And we finally propose a GA heuristic for solving the considered problem. The initial as well as the following populations of the GA are improved by applying repair algorithms based in neighborhood local search procedures. For small size instances, we compare the solutions obtained by our GA and optimal solutions found with the mixed integer linear model (for n=2); and for large size instances, we evaluate the GA solutions using a basic comparison drawn from the problem specificities. The obtained results indicate the efficiency of the proposed GA and provide the basis for further research, such as multi-hoist problems.