The batch splitting scheduling problem has recently become a major target in manufacturing systems, and the researchers have obtained great achievements, whereas most of existing related researches focus on equal-size...The batch splitting scheduling problem has recently become a major target in manufacturing systems, and the researchers have obtained great achievements, whereas most of existing related researches focus on equal-sized and consistent-sized batch splitting scheduling problem, and solve the problem by fixing the number of sub-batches, or the sub-batch sizes, or both. Under such circumstance and to provide a practical method for production scheduling in batch production mode, a study was made on the batch splitting scheduling problem on alternative machines, based on the objective to minimize the makespan. A scheduling approach was presented to address the variable-sized batch splitting scheduling problem in job shops trying to optimize both the number of sub-bathes and the sub-batch sizes, based on differential evolution（DE）, making full use of the finding that the sum of values of genes in one chromosome remains the same before and after mutation in DE. Considering before-arrival set-up time and processing time separately, a variable-sized batch splitting scheduling model was established and a new hybrid algorithm was brought forward to solve both the batch splitting problem and the batch scheduling problem. A new parallel chromosome representation was adopted, and the batch scheduling chromosome and the batch splitting chromosome were treated separately during the global search procedure, based on self-adaptive DE and genetic crossover operator, respectively. A new local search method was further designed to gain a better performance. A solution consists of the optimum number of sub-bathes for each operation per job, the optimum batch size for each sub-batch and the optimum sequence of sub-batches. Computational experiments of four test instances and a realistic problem in a speaker workshop were performed to testify the effectiveness of the proposed scheduling method. The study takes advantage of DE＇s distinctive feature, and employs the algorithm as a solution approach, and thereby deepens and enriches the content of batch splitting scheduling.展开更多
Given a list of items and a sequence of variable-sized bins arriving one by one, it is NP-hard to pack the items into the bin list with a goal to minimize the total size of bins from the earliest one to the last used....Given a list of items and a sequence of variable-sized bins arriving one by one, it is NP-hard to pack the items into the bin list with a goal to minimize the total size of bins from the earliest one to the last used. In this paper a set of approximation algorithms is presented for cases in which the ability to preview at most k（〉=2） arriving bins is given. With the essential assumption that all bin sizes are not less than the largest item size, analytical results show the asymptotic worst case ratios of all k-bounded space and offiine algorithms are 2. Based on experiments by applying algorithms to instances in which item sizes and bin sizes are drawn independently from the continuous uniform distribution respectively in the interval [0,u] and [u,l ], averagecase experimental results show that, with fixed k, algorithms with the Best Fit packing（closing） rule are statistically better than those with the First Fit packing（closing） rule.展开更多
It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling proble...It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling problem into a variant of the variable-sized bin packing problem, put forward eight bin packing algorithms adapted from the classic one-dimensional bin packing problem and investigated their performances from both of the worst-case and the average-case scenarios. Analytical results show that the worst-case performance ratios of the algorithms are not less than 2. Experimental results for average cases show that the Best Fit and the Best Fit Decreasing algorithm outperform any others for independent and precedence-constrained jobs respectively.展开更多
基金supported by National Hi-tech Research and Development Program of China (863 Program, Grant No. 2007AA04Z155)National Natural Science Foundation of China (Grant No. 60970021)Zhejiang Provincial Natural Science Foundation of China (Grant No. Y1090592)
文摘The batch splitting scheduling problem has recently become a major target in manufacturing systems, and the researchers have obtained great achievements, whereas most of existing related researches focus on equal-sized and consistent-sized batch splitting scheduling problem, and solve the problem by fixing the number of sub-batches, or the sub-batch sizes, or both. Under such circumstance and to provide a practical method for production scheduling in batch production mode, a study was made on the batch splitting scheduling problem on alternative machines, based on the objective to minimize the makespan. A scheduling approach was presented to address the variable-sized batch splitting scheduling problem in job shops trying to optimize both the number of sub-bathes and the sub-batch sizes, based on differential evolution（DE）, making full use of the finding that the sum of values of genes in one chromosome remains the same before and after mutation in DE. Considering before-arrival set-up time and processing time separately, a variable-sized batch splitting scheduling model was established and a new hybrid algorithm was brought forward to solve both the batch splitting problem and the batch scheduling problem. A new parallel chromosome representation was adopted, and the batch scheduling chromosome and the batch splitting chromosome were treated separately during the global search procedure, based on self-adaptive DE and genetic crossover operator, respectively. A new local search method was further designed to gain a better performance. A solution consists of the optimum number of sub-bathes for each operation per job, the optimum batch size for each sub-batch and the optimum sequence of sub-batches. Computational experiments of four test instances and a realistic problem in a speaker workshop were performed to testify the effectiveness of the proposed scheduling method. The study takes advantage of DE＇s distinctive feature, and employs the algorithm as a solution approach, and thereby deepens and enriches the content of batch splitting scheduling.
文摘Given a list of items and a sequence of variable-sized bins arriving one by one, it is NP-hard to pack the items into the bin list with a goal to minimize the total size of bins from the earliest one to the last used. In this paper a set of approximation algorithms is presented for cases in which the ability to preview at most k（〉=2） arriving bins is given. With the essential assumption that all bin sizes are not less than the largest item size, analytical results show the asymptotic worst case ratios of all k-bounded space and offiine algorithms are 2. Based on experiments by applying algorithms to instances in which item sizes and bin sizes are drawn independently from the continuous uniform distribution respectively in the interval [0,u] and [u,l ], averagecase experimental results show that, with fixed k, algorithms with the Best Fit packing（closing） rule are statistically better than those with the First Fit packing（closing） rule.
文摘It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling problem into a variant of the variable-sized bin packing problem, put forward eight bin packing algorithms adapted from the classic one-dimensional bin packing problem and investigated their performances from both of the worst-case and the average-case scenarios. Analytical results show that the worst-case performance ratios of the algorithms are not less than 2. Experimental results for average cases show that the Best Fit and the Best Fit Decreasing algorithm outperform any others for independent and precedence-constrained jobs respectively.
