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

In this study, we consider the problem of scheduling a set of independent jobs with sequence-dependent setup times and job splitting, on a set of identical parallel machines such that maximum completion time (makespan) is minimized. For this NP-hard problem, we suggest a heuristic algorithm improving an existing one, using a linear programming modeling with setup times and job splitting considerations. The performance of our new method is tested on over 6000 instances with different size by comparing it with a lower bound.

This paper considers an identical parallel machine scheduling problem (PMSP) in which setups are necessary between the processing of different jobs. The criterion is to minimize the makespan. This problem is NP-hard (Nait et al., 2003, Yalaoui and Chu, 2003 and Sveltana et al., 2001). The problem of scheduling jobs on identical parallel machines, without preemption, to minimize makespan is NP-hard, since even the problem restricted to two machines (P2//Cmax)(P2//Cmax) was shown to be NP-hard by a reduction to a bi-partitioning problem by Karp (1972). Note that our problem is a real-life one, as most of the studies on PMSP taking into account setup times in order to minimize makespan. The setup time has often been considered to be negligible or as a part of the processing time. Otherwise, we can distinguish two types of setup time: sequence-independent and sequence-dependent setup times. Sequence-independent setup time depends only on the job to be processed while sequence-dependent setup time depends on both the job to be processed and the one yet processed. The phenomenon of sequence-dependent setup times has been investigated by researchers for real-world job-shop environment as glass industry (Paul, 1979 and Chevalier et al., 1996), metallurgical industry (Narasimhan and Panwalkar, 1984 and Narasimhan and Mangiameli, 1987), paper industry (Sherali et al., 1990), chemical industry (Riane, 1998) and (Fortemps et al., 1996), textile industry (Sherali et al., 1990 and Aghezzaf et al., 1995), wood industry (Riane, 1998), aerospace industry (Li, 1997). Another important feature of our problem is that each job can be split into job sections, which can be processed in parallel on different machines. In textile industry for example, a job can be a batch of several parts (100 shirts or 1000 socks ……). Any batch can be decomposed into sub-batches. This corresponds to the splitting of jobs. The difference between job splitting and preemption is that job sections cannot be processed on different machines simultaneously if only preemption is allowed. However, with job splitting, jobs can be split to continuous sublots and processed simultaneously on different machines. The first on parallel machines scheduling problem dates from the Fifties through the works of McNaughton (1959) and Hu (1961). This type of problem has received continuous interest from researchers and from this fact the literature increased. Various constraints have been taken into account and different criteria have been studied. The first heuristic to solve PMSP based on the nearest neighbor was published in 1978 (Frederickson et al., 1978). Other authors investigated the problem, such as Flynn (1987), Hahn et al. (1989) and Bobrowski and Kim, 1994 and Bobrowski and Kim, 1997. They investigated the impact of setup time variation on sequencing decision. Guinet (1993) shows that PMSP can be reduced on vehicle routing problem (VRP) and suggest first a two step heuristic. Secondly, they formulated the problem in a zero–one linear program and proposed a new heuristic which consisted of solving the dual problem of the obtained assignment problem. A state-of-the-art until 1990 on parallel machines scheduling according to the viewpoints: completion-time-based, due-date-based and flow-time-based performance measures, is given in Cheng and Sin (1990). Lam and Xing (1997) gave a short review of new developments of PSMP associated with the problems of just-in-time productions, preemption with setup and capacited machine scheduling. Xing and Zhang (2000) presented a heuristic for identical PMSP with sequence-independent setup times and job splitting which has the worst-case performance ratio not greater than View the MathML source74-1/M for M⩾2M⩾2 where M is the number of machines. They also presented a linear programming formulation for an unrelated PMSP with job splitting and without setup times to minimize makespan. We note also that most of works using linear programming deal with unrelated parallel machines ( Potts, 1985 and Xing and Zhang, 2000). For more information, we refer interested readers to the papers of Allahverdi et al. (1999) and Yalaoui and Chu (2003). The proposed new method is an improvement of the method proposed by Yalaoui and Chu, 1999 and Yalaoui and Chu, 2003 and called Y_C. Heu thereafter. This latter method can be decomposed into two parts. Firstly, the PMSP with sequence-dependent setup times is reduced to a single machine scheduling problem (SMSP). The SMSP is transformed into a traveling salesman problem (TSP) and solved by an appropriate algorithm. Secondly, a feasible initial solution to the original parallel machine problem is obtained by using the result of the first part. This initial solution is then improved using an iterative algorithm in a step by step manner, taking into account the setup times and job splitting. The idea is to reduce makespan at each iteration by sublots calibration between critical machines. The computations stop when the improvement becomes insignificant. It means that the iteration number may not be bounded. Many works have been performed on the subject. Riotteau et al. (2001) proposed an improvement of the lower bound of Yalaoui and Chu (1999), and a new heuristic based on a multiple TSP resolution. The TSP problem is solved to optimality using appropriate algorithms. Therefore the number of jobs is limited and important computational time is required. At the first stage, an asymmetrical TSP has to be solved. For this problem a lot of work has been performed, such as Little et al. (1963), Gilmore and Gomory (1964), Bellmore and Malone (1971). Smith et al. (1977) proposed a branch and bound algorithm based on Bellmore and Malone methods and characterized by an adapted lower bounding scheme and a depth-first searching strategy. Carpaneto and Toth (1980) introduced some improvements to Bellmore and Malone scheme's. In 1995, they published (Carpaneto et al., 1995) a new method considered until now by most of the researchers (Yalaoui and Chu, 2003 and Lysgaard, 1999) as the most effective exact method to solve the asymmetrical TSP. In addition to the studies cited above, more heuristics and exact methods could be founded in Lysgaard (1999) and Boland et al. (2000). In spite of the efficiency of the 1995 Carpaneto et al. (1995) exact method, Yalaoui and Chu (2003) preferred using Little's method for its relative implementation simplicity and its efficiency whereas Riotteau et al. (2001) used an exact algorithm (Skierra, 1998) for the successive resolution of TSP. In this paper, we describe the problem in Section 2. Section 3 presents the linear programming formulation. In Section 4 an example is given to illustrate the Yalaoui and Chu heuristic and the new method. Section 5 is dedicated to computational experimentation.

In this paper, we have proposed a new method based on linear programming techniques for an identical parallel machine scheduling problem involving sequence-dependent setup times and job splitting. The criterion is to minimize the makespan. We use a lower bound to evaluate the performance of our new method on large number of randomly generated instances. This method has improved the run time for an acceptable quality of the solution. As shown in the computational results, for more than 6000 instances a general average performance of 4.74% was obtained by using linear programming and a TSP heuristic method with less run time who makes the method very practical in real-life problems. Further evaluation of the method is needed, especially its worst case performance and its computational complexity. This is the topic of a future research.