In this contribution we present an online scheduling algorithm for a real world multiproduct batch plant. The overall mixed integer nonlinear programming (MINLP) problem is hierarchically structured into a mixed integ...In this contribution we present an online scheduling algorithm for a real world multiproduct batch plant. The overall mixed integer nonlinear programming (MINLP) problem is hierarchically structured into a mixed integer linear programming (MILP) problem first and then a reduced dimensional MINLP problem, which are optimized by mathematical programming (MP) and genetic algorithm (GA) respectively. The basis idea relies on combining MP with GA to exploit their complementary capacity. The key features of the hierarchical model are explained and illustrated with some real world cases from the multiproduct batch plants.展开更多
In this paper, a fabrication scheduling problem concerning the production of components at a single manufacturing facility was studied, in which the manufactured components are subsequently assembled into a finite num...In this paper, a fabrication scheduling problem concerning the production of components at a single manufacturing facility was studied, in which the manufactured components are subsequently assembled into a finite number of end products. Each product was assumed to comprise a common component to all jobs and a unique component to itself. Common operations were processed in batches and each batch required a setup time. A product is completed when both its two operations have been processed and are available. The optimality criterion considered was the minimization of weighted flow time. For this scheduling problem, the optimal schedules were described in a weignted shortest processing time first （WSPT） order and two algorithms were constructed corresponding to the batch availability and item availability, respectively.展开更多
We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the long...We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the longest processing time of the jobs in this batch. We prove this problem to be NP-hard. Furthermore, we present a polynomial time approximation scheme （PTAS） and a fully polynomial time approximation scheme （FPTAS） for this problem.展开更多
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 study scheduling problems with rejection on parallel-machine.Each job consists of a processing time,a rejection cost,and a release date.The goal is to minimize the makespan of the jobs accepted when the total rejec...We study scheduling problems with rejection on parallel-machine.Each job consists of a processing time,a rejection cost,and a release date.The goal is to minimize the makespan of the jobs accepted when the total rejection cost is not larger than a given threshold.Firstly,we verify that these problems are NP-hard.Secondly,for the multiprocessor scheduling problem with rejection,we give a pseudo-polynomial algorithm and two fully polynomial approximation schemes(FPTAS for short)for fixed positive integer m,where m is the number of machines.For the scheduling problem with rejection and the job with non-identical release time on m machines,we also design a pseudo-polynomial algorithm and a fully polynomial approximation scheme when m is a fixed positive integer.We provide an approximation algorithm with the worst case performance 2 for arbitrary positive integer m.Finally,we discuss the online scheduling problem with rejection.We show that even if there are just two distinct arrive times for the jobs,there is not any online algorithm whose competitive ratio is constant for it.展开更多
The scheduling problem on a single batching machine with family jobs was proposed.The single batching machine can process a group of jobs simultaneously as a batch.Jobs in the same batch complete at the same time.The ...The scheduling problem on a single batching machine with family jobs was proposed.The single batching machine can process a group of jobs simultaneously as a batch.Jobs in the same batch complete at the same time.The batch size is assumed to be unbounded.Jobs that belong to different families can not be processed in the same batch.The objective function is minimizing maximum lateness.For the problem with fixed number of m families and n jobs,a polynomial time algorithm based on dynamic programming with time complexity of O(n(n/m+1)m)was presented.展开更多
This paper studies the batch sizing scheduling problem with earliness and tardiness penalties which is closely related to a two-level supply chain problem.In the problem,there are K customer orders,where each customer...This paper studies the batch sizing scheduling problem with earliness and tardiness penalties which is closely related to a two-level supply chain problem.In the problem,there are K customer orders,where each customer order consisting of some unit length jobs has a due date.The jobs are processed in a common machine and then delivered to their customers in batches,where the size of each batch has upper and lower bounds and each batch may incur a fixed setup cost which can also be considered a fixed delivery cost.The goal is to find a schedule which minimizes the sum of the earliness and tardiness costs and the setup costs incurred by creating a new batch.The authors first present some structural properties of the optimal schedules for single-order problem with an additional assumption(a):The jobs are consecutively processed from time zero.Based on these properties,the authors give a polynomial-time algorithm for single-order problem with Assumption(a).Then the authors give dynamic programming algorithms for some special cases of multiple-order problem with Assumption(a).At last,the authors present some structural properties of the optimal schedules for single-order problem without Assumption(a) and give a polynomial-time algorithm for it.展开更多
基金Supported by the National 973 Program of China (No. G2000263).
文摘In this contribution we present an online scheduling algorithm for a real world multiproduct batch plant. The overall mixed integer nonlinear programming (MINLP) problem is hierarchically structured into a mixed integer linear programming (MILP) problem first and then a reduced dimensional MINLP problem, which are optimized by mathematical programming (MP) and genetic algorithm (GA) respectively. The basis idea relies on combining MP with GA to exploit their complementary capacity. The key features of the hierarchical model are explained and illustrated with some real world cases from the multiproduct batch plants.
文摘In this paper, a fabrication scheduling problem concerning the production of components at a single manufacturing facility was studied, in which the manufactured components are subsequently assembled into a finite number of end products. Each product was assumed to comprise a common component to all jobs and a unique component to itself. Common operations were processed in batches and each batch required a setup time. A product is completed when both its two operations have been processed and are available. The optimality criterion considered was the minimization of weighted flow time. For this scheduling problem, the optimal schedules were described in a weignted shortest processing time first （WSPT） order and two algorithms were constructed corresponding to the batch availability and item availability, respectively.
文摘We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the longest processing time of the jobs in this batch. We prove this problem to be NP-hard. Furthermore, we present a polynomial time approximation scheme （PTAS） and a fully polynomial time approximation scheme （FPTAS） for this problem.
基金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.
基金supported by the National Natural Science Foundation of China(Nos.12271295 and 12371319)Shandong Province Natural Science Foundation(Nos.ZR2019MA061 and ZR2022MA038).
文摘We study scheduling problems with rejection on parallel-machine.Each job consists of a processing time,a rejection cost,and a release date.The goal is to minimize the makespan of the jobs accepted when the total rejection cost is not larger than a given threshold.Firstly,we verify that these problems are NP-hard.Secondly,for the multiprocessor scheduling problem with rejection,we give a pseudo-polynomial algorithm and two fully polynomial approximation schemes(FPTAS for short)for fixed positive integer m,where m is the number of machines.For the scheduling problem with rejection and the job with non-identical release time on m machines,we also design a pseudo-polynomial algorithm and a fully polynomial approximation scheme when m is a fixed positive integer.We provide an approximation algorithm with the worst case performance 2 for arbitrary positive integer m.Finally,we discuss the online scheduling problem with rejection.We show that even if there are just two distinct arrive times for the jobs,there is not any online algorithm whose competitive ratio is constant for it.
基金National Natural Science Foundation of China(No.70832002)Graduate Student Innovation Fund of Fudan University,China
文摘The scheduling problem on a single batching machine with family jobs was proposed.The single batching machine can process a group of jobs simultaneously as a batch.Jobs in the same batch complete at the same time.The batch size is assumed to be unbounded.Jobs that belong to different families can not be processed in the same batch.The objective function is minimizing maximum lateness.For the problem with fixed number of m families and n jobs,a polynomial time algorithm based on dynamic programming with time complexity of O(n(n/m+1)m)was presented.
基金National Nature Science Foundation of China under Grant Nos.11471210and 11171207the Natural Science Foundation of Ningbo City under Grant No.2015A610168the Natural Science Foundation of Zhejiang Province of China under Grant No.LQl3A010010
文摘This paper studies the batch sizing scheduling problem with earliness and tardiness penalties which is closely related to a two-level supply chain problem.In the problem,there are K customer orders,where each customer order consisting of some unit length jobs has a due date.The jobs are processed in a common machine and then delivered to their customers in batches,where the size of each batch has upper and lower bounds and each batch may incur a fixed setup cost which can also be considered a fixed delivery cost.The goal is to find a schedule which minimizes the sum of the earliness and tardiness costs and the setup costs incurred by creating a new batch.The authors first present some structural properties of the optimal schedules for single-order problem with an additional assumption(a):The jobs are consecutively processed from time zero.Based on these properties,the authors give a polynomial-time algorithm for single-order problem with Assumption(a).Then the authors give dynamic programming algorithms for some special cases of multiple-order problem with Assumption(a).At last,the authors present some structural properties of the optimal schedules for single-order problem without Assumption(a) and give a polynomial-time algorithm for it.
