In parallel-batching machine scheduling, all jobs in a batch start and complete at the same time, and the processing time of the batch is the maximum processing time of any job in it. For the unbounded parallel-batchi...In parallel-batching machine scheduling, all jobs in a batch start and complete at the same time, and the processing time of the batch is the maximum processing time of any job in it. For the unbounded parallel-batching machine scheduling problem of minimizing the maximum lateness, denoted 1|p-batch|L_(max), a dynamic programming algorithm with time complexity O(n^2) is well known in the literature.Later, this algorithm is improved to be an O(n log n) algorithm. In this note, we present another O(n log n) algorithm with simplifications on data structure and implementation details.展开更多
This study focuses on the scheduling problem of unrelated parallel batch processing machines(BPM)with release times,a scenario derived from the moulding process in a foundry.In this process,a batch is initially formed...This study focuses on the scheduling problem of unrelated parallel batch processing machines(BPM)with release times,a scenario derived from the moulding process in a foundry.In this process,a batch is initially formed,placed in a sandbox,and then the sandbox is positioned on a BPM formoulding.The complexity of the scheduling problem increases due to the consideration of BPM capacity and sandbox volume.To minimize the makespan,a new cooperated imperialist competitive algorithm(CICA)is introduced.In CICA,the number of empires is not a parameter,and four empires aremaintained throughout the search process.Two types of assimilations are achieved:The strongest and weakest empires cooperate in their assimilation,while the remaining two empires,having a close normalization total cost,combine in their assimilation.A new form of imperialist competition is proposed to prevent insufficient competition,and the unique features of the problem are effectively utilized.Computational experiments are conducted across several instances,and a significant amount of experimental results show that the newstrategies of CICAare effective,indicating promising advantages for the considered BPMscheduling problems.展开更多
In order to solve the flexible job shop scheduling problem with variable batches,we propose an improved multiobjective optimization algorithm,which combines the idea of inverse scheduling.First,a flexible job shop pro...In order to solve the flexible job shop scheduling problem with variable batches,we propose an improved multiobjective optimization algorithm,which combines the idea of inverse scheduling.First,a flexible job shop problem with the variable batches scheduling model is formulated.Second,we propose a batch optimization algorithm with inverse scheduling in which the batch size is adjusted by the dynamic feedback batch adjusting method.Moreover,in order to increase the diversity of the population,two methods are developed.One is the threshold to control the neighborhood updating,and the other is the dynamic clustering algorithm to update the population.Finally,a group of experiments are carried out.The results show that the improved multi-objective optimization algorithm can ensure the diversity of Pareto solutions effectively,and has effective performance in solving the flexible job shop scheduling problem with variable batches.展开更多
We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching machine.The processing time of each job is defined by an interval and any number of jobs can be assigned into...We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching machine.The processing time of each job is defined by an interval and any number of jobs can be assigned into a batch provided that the processing time intervals of the jobs in the common batch are not disjoint.Three problems are considered:(1)minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs;(2)minimize the makespan of accepted jobs subject to an upper bound on the total rejection penalty of rejected jobs;(3)minimize the total rejection penalty of rejected jobs subject to an upper bound on the makespan of accepted jobs.We provide an O(n2)time algorithm for the first problem.Moreover,for the other two problems,we first show that they are NP-hard,and then present pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for them,respectively.展开更多
In flexible job-shop batch scheduling problem, the optimal lot-size of different process is not always the same because of different processing time and set-up time. Even for the same process of the same workpiece, th...In flexible job-shop batch scheduling problem, the optimal lot-size of different process is not always the same because of different processing time and set-up time. Even for the same process of the same workpiece, the choice of machine also affects the optimal lot-size. In addition, different choices of lot-size between the constrained processes will impact the manufacture efficiency. Considering that each process has its own appropriate lot-size, we put forward the concept of scheduling with lot-splitting based on process and set up the scheduling model of lot-splitting to critical path process as the core. The model could update the set of batch process and machine selection strategy dynamically to determine processing route and arrange proper lot-size for different processes, to achieve the purpose of optimizing the makespan and reducing the processing batches effectively. The experiment results show that, comparing with lot-splitting scheduling scheme based on workpiece, this model optimizes the makespan and improves the utilization efficiency of the machine. It also greatly decreases the machined batches (42%) and reduces the complexity of shop scheduling production management.展开更多
We consider bounded parallel-batch scheduling with proportional-linear deteriorating jobs and the objective to minimize the total completion time.We give some properties of optimal schedules for the problem and presen...We consider bounded parallel-batch scheduling with proportional-linear deteriorating jobs and the objective to minimize the total completion time.We give some properties of optimal schedules for the problem and present for it a dynamic programming algorithm running in O(b^(2)m^(2)2^(m))time,where b is the size of a batch and m is the number of distinct deterioration rates.展开更多
基金Supported by NSFC(11571323 11201121)+1 种基金NSFSTDOHN(162300410221)NSFEDOHN(2013GGJS-079)
文摘In parallel-batching machine scheduling, all jobs in a batch start and complete at the same time, and the processing time of the batch is the maximum processing time of any job in it. For the unbounded parallel-batching machine scheduling problem of minimizing the maximum lateness, denoted 1|p-batch|L_(max), a dynamic programming algorithm with time complexity O(n^2) is well known in the literature.Later, this algorithm is improved to be an O(n log n) algorithm. In this note, we present another O(n log n) algorithm with simplifications on data structure and implementation details.
基金the National Natural Science Foundation of China(Grant Number 61573264).
文摘This study focuses on the scheduling problem of unrelated parallel batch processing machines(BPM)with release times,a scenario derived from the moulding process in a foundry.In this process,a batch is initially formed,placed in a sandbox,and then the sandbox is positioned on a BPM formoulding.The complexity of the scheduling problem increases due to the consideration of BPM capacity and sandbox volume.To minimize the makespan,a new cooperated imperialist competitive algorithm(CICA)is introduced.In CICA,the number of empires is not a parameter,and four empires aremaintained throughout the search process.Two types of assimilations are achieved:The strongest and weakest empires cooperate in their assimilation,while the remaining two empires,having a close normalization total cost,combine in their assimilation.A new form of imperialist competition is proposed to prevent insufficient competition,and the unique features of the problem are effectively utilized.Computational experiments are conducted across several instances,and a significant amount of experimental results show that the newstrategies of CICAare effective,indicating promising advantages for the considered BPMscheduling problems.
基金supported by the National Key R&D Plan(2020YFB1712902)the National Natural Science Foundation of China(52075036).
文摘In order to solve the flexible job shop scheduling problem with variable batches,we propose an improved multiobjective optimization algorithm,which combines the idea of inverse scheduling.First,a flexible job shop problem with the variable batches scheduling model is formulated.Second,we propose a batch optimization algorithm with inverse scheduling in which the batch size is adjusted by the dynamic feedback batch adjusting method.Moreover,in order to increase the diversity of the population,two methods are developed.One is the threshold to control the neighborhood updating,and the other is the dynamic clustering algorithm to update the population.Finally,a group of experiments are carried out.The results show that the improved multi-objective optimization algorithm can ensure the diversity of Pareto solutions effectively,and has effective performance in solving the flexible job shop scheduling problem with variable batches.
基金Supported by Key Research Projects of Henan Higher Education Institutions(20A110037)Young Backbone Teachers Training Program of Zhongyuan University of Technology(2018XQG15)+4 种基金Outstanding Youth Foundation of Science and Technology Innovation of Henan Province(184100510004)Natural Science Foundation of Henan Education Department(16A630061)Science and Technology Program of Henan Province(182102110129)Innovation Training Program for College Students of Henan Province(S201910485026)Basic Research Projects of Key Scientific Research Projects Plan in Henan Higher Education Institutions(20zx003)。
文摘We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching machine.The processing time of each job is defined by an interval and any number of jobs can be assigned into a batch provided that the processing time intervals of the jobs in the common batch are not disjoint.Three problems are considered:(1)minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs;(2)minimize the makespan of accepted jobs subject to an upper bound on the total rejection penalty of rejected jobs;(3)minimize the total rejection penalty of rejected jobs subject to an upper bound on the makespan of accepted jobs.We provide an O(n2)time algorithm for the first problem.Moreover,for the other two problems,we first show that they are NP-hard,and then present pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for them,respectively.
基金Supported by National Key Technology R&D Program(No.2013BAJ06B)
文摘In flexible job-shop batch scheduling problem, the optimal lot-size of different process is not always the same because of different processing time and set-up time. Even for the same process of the same workpiece, the choice of machine also affects the optimal lot-size. In addition, different choices of lot-size between the constrained processes will impact the manufacture efficiency. Considering that each process has its own appropriate lot-size, we put forward the concept of scheduling with lot-splitting based on process and set up the scheduling model of lot-splitting to critical path process as the core. The model could update the set of batch process and machine selection strategy dynamically to determine processing route and arrange proper lot-size for different processes, to achieve the purpose of optimizing the makespan and reducing the processing batches effectively. The experiment results show that, comparing with lot-splitting scheduling scheme based on workpiece, this model optimizes the makespan and improves the utilization efficiency of the machine. It also greatly decreases the machined batches (42%) and reduces the complexity of shop scheduling production management.
基金This work was supported by the National Natural Science Foundation of China(Nos.11201259,11071142,71101081)the Doctoral Fund of the Ministry of Education(Nos.20123705120001,20123705120003)+2 种基金the Natural Science Foundation of Shandong Province(Nos.ZR2011AL017,ZR2010AM034)Doctoral Research Fund(No.20110130)and Postdoctoral Researcher of Qufu Normal UniversityWe thank the editor an。
文摘We consider bounded parallel-batch scheduling with proportional-linear deteriorating jobs and the objective to minimize the total completion time.We give some properties of optimal schedules for the problem and present for it a dynamic programming algorithm running in O(b^(2)m^(2)2^(m))time,where b is the size of a batch and m is the number of distinct deterioration rates.