batchprocessingmachines are often the bottleneck in semiconductor manufacturing and their scheduling plays a key role in production management. Pioneer researches on multi-objective batchmachines scheduling mainly ...
详细信息
batchprocessingmachines are often the bottleneck in semiconductor manufacturing and their scheduling plays a key role in production management. Pioneer researches on multi-objective batchmachines scheduling mainly focus on evolutionary algorithms, failing to meet the online scheduling demand. To deal with the challenges confronted by incompatible job families, dynamic job arrivals, capacitated machines and multiple objectives, we propose a clustering-aided multi-agent deep reinforcement learning approach (CA-MADRL) for the scheduling problem. Specifically, to achieve diverse nondominated solutions, an offline multi-objective scheduling algorithm named Multi-Subpopulation fast elitist Non-Dominated Sorting Genetic Algorithm (MS-NSGA-II) is firstly developed to obtain the Pareto Fronts, and a clustering algorithm based on cosine distance is employed to analyze the distribution of Pareto frontier solution, which would be used to guide reward functions design in multi-agent deep reinforcement learning. To realize multi-objective optimization, several reinforcement learning base models are trained for different optimization directions, each of which composed of batch forming agent and batch scheduling agent. To alleviate time complexity of model training, a parameter sharing strategy is introduced between different reinforcement learning base model. By validating the proposed approach with 16 instances designed based on actual production data from a semiconductor manufacturing company, it has been demonstrated that the approach not only meets the high-frequency scheduling requirements of manufacturing systems for parallel batch processing machines but also effectively reduces the total job tardiness and machine energy consumption.
This paper aims to minimise the makespan of a set of identical batchprocessingmachines in parallel. The batchprocessing machine can process a batch of jobs as long as the total size of all the jobs in the batch doe...
详细信息
This paper aims to minimise the makespan of a set of identical batchprocessingmachines in parallel. The batchprocessing machine can process a batch of jobs as long as the total size of all the jobs in the batch does not exceed its capacity. The processing time of the job and its size are given. batchprocessing time is equal to the longest processing job in the batch. Two interdependent decisions are required, namely grouping jobs into batches, and scheduling the batches on the machines. The problem under study is NP-hard and hence a Genetic Algorithm (GA) approach is proposed. The effectiveness of the GA approach to solve randomly generated problems was compared with a Simulated Annealing (SA) approach, a Random Keys Genetic Algorithm (RKGA), a Hybrid Genetic Heuristic (HGH) and a commercial solver. The proposed GA approach was found to be very effective in finding a good solution in a short time as opposed to SA, RKGA and a commercial solver. Both GA and HGH are marginally better than each other on different problem instances. [Submitted 17 August 2007;Revised 10 October 2007;Revised 30 May 2008;Revised 29 July 2008;Accepted 15 September 2008]
This paper investigates the scheduling problem of parallel identical batchprocessingmachines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and pro...
详细信息
This paper investigates the scheduling problem of parallel identical batchprocessingmachines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and processing time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Based on developing heuristic approaches, we proposed a hybrid genetic heuristic (HGH) to minimize makespan objective. To verify the performance of our algorithm, comparisons are made through using a simulated annealing (SA) approach addressed in the literature as a comparator algorithm. Computational experiments reveal that affording the knowledge of problem through using heuristic procedures, gives HGH the ability of finding optimal or near optimal solutions in a reasonable time. (C) 2006 Elsevier Ltd. All rights reserved.
This paper deals with the problem of scheduling identical parallel batch processing machines. In this scheduling system, each machine processes a set of jobs in a batch simultaneously and each job in the batch is char...
详细信息
This paper deals with the problem of scheduling identical parallel batch processing machines. In this scheduling system, each machine processes a set of jobs in a batch simultaneously and each job in the batch is characterized by its processing time, ready time and job size. We propose a hybrid discrete cuckoo search (HDCS) algorithm to minimize makespan for this scheduling problem. The HDCS is constructed, based on a modified variable neighborhood search and cuckoo search algorithm. In the proposed algorithm, we present a modified Levy flight in the cuckoo search to transform a continuous position in the HDCS into a discrete schedule for generating a new solution. The process parameters of the proposed HDCS are tuned by implementing the desirability-based Taguchi method to optimize both solution quality and run time. The results of exhaustive computational experimentation on a large number of randomly generated sparse as well as non-sparse problem instances show that the proposed algorithm is more effective and efficient than the state-of-the-art algorithms.
This paper investigates a scheduling problem of non-identical parallel batch processing machines (PBPMs) with job release times and non-identical job sizes, in which jobs come from compatible product families, to mini...
详细信息
This paper investigates a scheduling problem of non-identical parallel batch processing machines (PBPMs) with job release times and non-identical job sizes, in which jobs come from compatible product families, to minimise the total weighted tardiness (TWT). Only a few studies on PBPM problems aimed at minimising the TWT are concerned with compatible product families. A mixed integer programming (MIP) model is formulated, and a multi-MIP approach is proposed based on this model. Given the computational difficulty in directly solving the multi-MIP approach, several heuristics are developed based on dispatching rules, dynamic programming methods, and simulated annealing (SA) algorithms. Computational results reveal that the proposed SA algorithms can obtain the optimal solutions for 99.8% of the tested small-scale (n = 10) problems and they significantly outperform the dispatching rule heuristics because the solution space is enlarged by the composite list and swapping method.
In this paper we consider the problem of scheduling jobs with release dates on parallel unbounded batchprocessingmachines to minimize the maximum lateness. We show that the case where the jobs have deadlines is stro...
详细信息
In this paper we consider the problem of scheduling jobs with release dates on parallel unbounded batchprocessingmachines to minimize the maximum lateness. We show that the case where the jobs have deadlines is strongly NP-hard. We develop a polynomial-time approximation scheme for the problem to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint. (C) 2009 Elsevier B.V. All rights reserved.
This paper addresses the parallel batch processing machines scheduling problem with two-dimensional bin packing constraints. One typical application of this problem is last-mile truck delivery. A set of rectangular it...
详细信息
This paper addresses the parallel batch processing machines scheduling problem with two-dimensional bin packing constraints. One typical application of this problem is last-mile truck delivery. A set of rectangular items (or jobs) that have delivery times are processed by a set of homogeneous vehicles (or machines). Each vehicle can deliver a batch of items at a trip following a fixed route as long as these items in the batch can be placed onto the vehicle without overlapping. The total delivery time of a batch is determined by the longest delivery time of the items in the batch. The problem is to allocate the items, which may be rotated, into batches and then assign the batches to the vehicles so as to minimize the makespan. A mixed integer programming model of the problem is formulated. A number of heuristic algorithms are proposed and compared. Some heuristics for two-dimensional packing problems are adapted to the problem. The performance of the algorithms is evaluated based on computational experiments. The experimental results show that the best-fit maximal rectangle (BFMR) heuristic is the best, in which the batch with the smallest remaining capacity is selected for an item, the empty maximal rectangle with the least space in the batch is chosen to place the item, and finally the generated batches are allocated to the vehicles according to the longest batch delivery time algorithm
We study the problem of scheduling on parallel batch processing machines with different capacities under a fuzzy environment to minimize the makespan. The jobs have non-identical sizes and fuzzy processing times. Afte...
详细信息
We study the problem of scheduling on parallel batch processing machines with different capacities under a fuzzy environment to minimize the makespan. The jobs have non-identical sizes and fuzzy processing times. After constructing a mathematical model of the problem, we propose a fuzzy ant colony optimization (FACO) algorithm. Based on the machine capacity constraint, two candidate job lists are adopted to select the jobs for building the batches. Moreover, based on the unoccupied space of the solution, heuristic information is designed for each candidate list to guide the ants. In addition, a fuzzy local optimization algorithm is incorporated to improve the solution quality. Finally, the proposed algorithm is compared with several state-of-the-art algorithms through extensive simulated experiments and statistical tests. The comparative results indicate that the proposed algorithm can find better solutions within reasonable time than all the other compared algorithms. (C) 2018 Elsevier B.V. All rights reserved.
暂无评论