This paper considers a reentrant scheduling problem on parallel primary machines with a remote server machine, which is required to carry out the setup operation. In this problem, each job has three operations. The fi...This paper considers a reentrant scheduling problem on parallel primary machines with a remote server machine, which is required to carry out the setup operation. In this problem, each job has three operations. The first and last operations are performed by the same primary machine, implying the reentrance, and the second operation is processed on the single server machine. The order of jobs is predetermined in our context. The challenge is to assign jobs to the primary machines to minimize the makespan. We develop a genetic algorithm(GA) to solve this problem. Based on a simple strategy of assigning jobs in batches on the parallel primary machines, the standardized random key vector representation is employed to split the jobs into batches. Comparisons among the proposed algorithm, the branch and bound(BB) algorithm and the heuristic algorithm, coordinated scheduling(CS), which is only one heuristic algorithm to solve this problem in the literature, are made on the benchmark data. The computational experiments show that the proposed genetic algorithm outperforms the heuristic CS and the maximum relative improvement rate in the makespan is 1.66%.展开更多
In order to improve the scheduling efficiency of photolithography,bottleneck process of wafer fabrications in the semiconductor industry,an effective estimation of distribution algorithm is proposed for scheduling pro...In order to improve the scheduling efficiency of photolithography,bottleneck process of wafer fabrications in the semiconductor industry,an effective estimation of distribution algorithm is proposed for scheduling problems of parallel litho machines with reticle constraints,where multiple reticles are available for each reticle type.First,the scheduling problem domain of parallel litho machines is described with reticle constraints and mathematical programming formulations are put forward with the objective of minimizing total weighted completion time.Second,estimation of distribution algorithm is developed with a decoding scheme specially designed to deal with the reticle constraints.Third,an insert-based local search with the first move strategy is introduced to enhance the local exploitation ability of the algorithm.Finally,simulation experiments and analysis demonstrate the effectiveness of the proposed algorithm.展开更多
This paper considers two parallel machine scheduling problems, where the objectives of both problems are to minimize the makespan, and the jobs arrive over time, on two uniform machines with speeds 1 and s （s 〉 1）,...This paper considers two parallel machine scheduling problems, where the objectives of both problems are to minimize the makespan, and the jobs arrive over time, on two uniform machines with speeds 1 and s （s 〉 1）, and on m identical machines, respectively. For the first problem, the authors show that the on-line LPT algorithm has a competitive ratio of （1 ＋ √5）/2 ≈ 1.6180 and the bound is tight. Furthermore, the authors prove that the on-line LPT algorithm has the best possible competitive ratio if s ≥ 1.8020. For the second problem, the authors present a lower bound of （15 - √17）/8 ≈ 1.3596 on the competitive ratio of any deterministic on-line algorithm. This improves a previous result of 1.3473.展开更多
In this paper, the authors consider an on-line scheduling problem of rn （m≥ 3） identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance tim...In this paper, the authors consider an on-line scheduling problem of rn （m≥ 3） identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance time interval is larger than the largest processing time of jobs, the authors prove that any on-line algorithm has not a constant competitive ratio. For the case that the length of maintenance time interval is less than or equal to the largest processing time of jobs, the authors prove a lower bound of 3 on the competitive ratio. The authors give an on-line algorithm with competitive 1 ratio 4 - 1/m. In particular, for the case of m = 3, the authors prove the competitive ratio of the on-line algorithm is 10/3.展开更多
基金Supported by National Natural Science Foundation of China(No.61271374)Beijing Natural Science Foundation(No.4122068)
文摘This paper considers a reentrant scheduling problem on parallel primary machines with a remote server machine, which is required to carry out the setup operation. In this problem, each job has three operations. The first and last operations are performed by the same primary machine, implying the reentrance, and the second operation is processed on the single server machine. The order of jobs is predetermined in our context. The challenge is to assign jobs to the primary machines to minimize the makespan. We develop a genetic algorithm(GA) to solve this problem. Based on a simple strategy of assigning jobs in batches on the parallel primary machines, the standardized random key vector representation is employed to split the jobs into batches. Comparisons among the proposed algorithm, the branch and bound(BB) algorithm and the heuristic algorithm, coordinated scheduling(CS), which is only one heuristic algorithm to solve this problem in the literature, are made on the benchmark data. The computational experiments show that the proposed genetic algorithm outperforms the heuristic CS and the maximum relative improvement rate in the makespan is 1.66%.
基金Supported by the National High Technology Research and Development Programme of China(No.2009AA043000)the National Natural Science Foundation of China(No.61273035,71471135)
文摘In order to improve the scheduling efficiency of photolithography,bottleneck process of wafer fabrications in the semiconductor industry,an effective estimation of distribution algorithm is proposed for scheduling problems of parallel litho machines with reticle constraints,where multiple reticles are available for each reticle type.First,the scheduling problem domain of parallel litho machines is described with reticle constraints and mathematical programming formulations are put forward with the objective of minimizing total weighted completion time.Second,estimation of distribution algorithm is developed with a decoding scheme specially designed to deal with the reticle constraints.Third,an insert-based local search with the first move strategy is introduced to enhance the local exploitation ability of the algorithm.Finally,simulation experiments and analysis demonstrate the effectiveness of the proposed algorithm.
基金supported by the Special Funds of the National Natural Science Foundation of China under Grant No.61340045the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20123705110003Innovation Project of Shangdong Graduate Education under Grant No.SDYC13036
文摘This paper considers two parallel machine scheduling problems, where the objectives of both problems are to minimize the makespan, and the jobs arrive over time, on two uniform machines with speeds 1 and s （s 〉 1）, and on m identical machines, respectively. For the first problem, the authors show that the on-line LPT algorithm has a competitive ratio of （1 ＋ √5）/2 ≈ 1.6180 and the bound is tight. Furthermore, the authors prove that the on-line LPT algorithm has the best possible competitive ratio if s ≥ 1.8020. For the second problem, the authors present a lower bound of （15 - √17）/8 ≈ 1.3596 on the competitive ratio of any deterministic on-line algorithm. This improves a previous result of 1.3473.
基金supported by the National Natural Science Foundation of China under Grant Nos.11271338,11171313,61070229,10901144,11001117supported by the Ph.D.Programs Foundation of Ministry ofEducation of China under Grant No.20111401110005the Henan Province Natural Science Foundation under Grant No.112300410047
文摘In this paper, the authors consider an on-line scheduling problem of rn （m≥ 3） identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance time interval is larger than the largest processing time of jobs, the authors prove that any on-line algorithm has not a constant competitive ratio. For the case that the length of maintenance time interval is less than or equal to the largest processing time of jobs, the authors prove a lower bound of 3 on the competitive ratio. The authors give an on-line algorithm with competitive 1 ratio 4 - 1/m. In particular, for the case of m = 3, the authors prove the competitive ratio of the on-line algorithm is 10/3.
