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.展开更多
As a complicated optimization problem,parallel batch processing machines scheduling problem(PBPMSP)exists in many real-life manufacturing industries such as textiles and semiconductors.Machine eligibility means that a...As a complicated optimization problem,parallel batch processing machines scheduling problem(PBPMSP)exists in many real-life manufacturing industries such as textiles and semiconductors.Machine eligibility means that at least one machine is not eligible for at least one job.PBPMSP and scheduling problems with machine eligibility are frequently considered;however,PBPMSP with machine eligibility is seldom explored.This study investigates PBPMSP with machine eligibility in fabric dyeing and presents a novel shuffled frog-leaping algorithm with competition(CSFLA)to minimize makespan.In CSFLA,the initial population is produced in a heuristic and random way,and the competitive search of memeplexes comprises two phases.Competition between any two memeplexes is done in the first phase,then iteration times are adjusted based on competition,and search strategies are adjusted adaptively based on the evolution quality of memeplexes in the second phase.An adaptive population shuffling is given.Computational experiments are conducted on 100 instances.The computational results showed that the new strategies of CSFLA are effective and that CSFLA has promising advantages in solving the considered PBPMSP.展开更多
Fabric dyeing is a critical production process in the clothing industry and heavily relies on batch processing machines(BPM).In this study,the parallel BPM scheduling problem with machine eligibility in fabric dyeing ...Fabric dyeing is a critical production process in the clothing industry and heavily relies on batch processing machines(BPM).In this study,the parallel BPM scheduling problem with machine eligibility in fabric dyeing is considered,and an adaptive cooperated shuffled frog-leaping algorithm(ACSFLA)is proposed to minimize makespan and total tardiness simultaneously.ACSFLA determines the search times for each memeplex based on its quality,with more searches in high-quality memeplexes.An adaptive cooperated and diversified search mechanism is applied,dynamically adjusting search strategies for each memeplex based on their dominance relationships and quality.During the cooperated search,ACSFLA uses a segmented and dynamic targeted search approach,while in non-cooperated scenarios,the search focuses on local search around superior solutions to improve efficiency.Furthermore,ACSFLA employs adaptive population division and partial population shuffling strategies.Through these strategies,memeplexes with low evolutionary potential are selected for reconstruction in the next generation,while thosewithhighevolutionarypotential are retained to continue their evolution.Toevaluate the performance of ACSFLA,comparative experiments were conducted using ACSFLA,SFLA,ASFLA,MOABC,and NSGA-CC in 90 instances.The computational results reveal that ACSFLA outperforms the other algorithms in 78 of the 90 test cases,highlighting its advantages in solving the parallel BPM scheduling problem with machine eligibility.展开更多
In this paper we study the problem of scheduling a batching machine with nonidentical job sizes. The jobs arrive simultaneously and have unit processing time. The goal is to minimize the total completion times. Having...In this paper we study the problem of scheduling a batching machine with nonidentical job sizes. The jobs arrive simultaneously and have unit processing time. The goal is to minimize the total completion times. Having shown that the problem is NP-hard, we put forward three approximation schemes with worst case ratio 4, 2, and 3/2, respectively.展开更多
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.展开更多
Planning and scheduling is one of the most important activity in supply chain operation management.Over the years,there have been multiple researches regarding planning and scheduling which are applied to improve a va...Planning and scheduling is one of the most important activity in supply chain operation management.Over the years,there have been multiple researches regarding planning and scheduling which are applied to improve a variety of supply chains.This includes two commonly used methods which are mathematical programming models and heuristics algorithms.Flowshop manufacturing systems are seen normally in industrial environments but few have considered certain constraints such as transportation capacity and transportation time within their supply chain.A two-stage flowshop of a single processing machine and a batch processing machine are considered with their capacity and transportation time between twomachines.The objectives of this research are to build a suitable mathematical model capable of minimizing the maximum completion time,to propose a heuristic optimization algorithm to solve the problem,and to develop an applicable program of the heuristics algorithm.AMixed Integer Programming(MIP)model and a heuristics optimization algorithmwas developed and tested using a randomly generated data set for feasibility.The overall results and performance of each approach was compared between the two methods that would assist the decision maker in choosing a suitable solution for their manufacturing line.展开更多
The casting production process typically involves single jobs and small batches,with multiple constraints in the molding and smelting operations.To address the discrete optimization challenge of casting production sch...The casting production process typically involves single jobs and small batches,with multiple constraints in the molding and smelting operations.To address the discrete optimization challenge of casting production scheduling,this paper presents a multi-objective batch scheduling model for molding and smelting operations on unrelated batch processing machines with incompatible job families and non-identical job sizes.The model aims to minimise the makespan,number of batches,and average vacancy rate of sandboxes.Based on the genetic algorithm,virus optimization algorithm,and two local search strategies,a hybrid algorithm(GA-VOA-BMS)has been designed to solve the model.The GA-VOA-BMS applies a novel Batch First Fit(BFF)heuristic for incompatible job families to improve the quality of the initial population,adopting the batch moving strategy and batch merging strategy to further enhance the quality of the solution and accelerate the convergence of the algorithm.The proposed algorithm was then compared with multi-objective swarm optimization algorithms,namely NSGA-ll,SPEA-l,and PESA-ll,to evaluate its effectiveness.The results of the performance comparison indicate that the proposed algorithm outperforms the others in terms of both qualityand stability.展开更多
We investigate the problem of the online scheduling with kind release times and job compatibilities on a single unbounded parallel-batch machine to minimize makespan.The kind release times(KRT)means that under the onl...We investigate the problem of the online scheduling with kind release times and job compatibilities on a single unbounded parallel-batch machine to minimize makespan.The kind release times(KRT)means that under the online setting no jobs can be released when the machine is busy.What associated with each job J_(j)are its normal processing time P_(j)and release time r_(j).Two jobs J_(i)and J_(j)are called compatible if max(p_(i),P_(j))≤(1+a)min(p_(i),P_(j)),where a is a given positive constant.Compatible jobs could be processed in the same batch.We derive a best possible online algorithm with a competitive ratio of 1+√λ^(2)-λ+1-λ,whereλ=a/(1+a).展开更多
This paper considers competitive project scheduling on two unbounded parallel batch machines.There are two competing firms,and each firm has an unbounded parallel batch machine.All projects must be performed in batche...This paper considers competitive project scheduling on two unbounded parallel batch machines.There are two competing firms,and each firm has an unbounded parallel batch machine.All projects must be performed in batches by Firms 1 and 2 on their machines,respectively.The profit that each firm obtains from each project depends on whether the firm finishes the job before or after its competitor.In the first problem,given a feasible schedule for Firm 1,the objective is to find an optimal schedule to maximize the total reward for Firm 2 under the given schedule for Firm 1.The corresponding total reward for Firm 1 is called the worst-case total reward of the given schedule for Firm 1.In the second problem,the objective is to find an optimal schedule for Firm 1 to maximize the worst-case total reward.We provide optimal algorithms for the two problems,respectively.展开更多
This study addresses the problem of two-stage scheduling on batch and single machines with limited waiting time constraint; thus, the makespan is minimized.A mixed-integer linear programming model is proposed for this...This study addresses the problem of two-stage scheduling on batch and single machines with limited waiting time constraint; thus, the makespan is minimized.A mixed-integer linear programming model is proposed for this problem. Three tight lower bounds and a heuristic algorithm are developed. The worst-case performance of the proposed algorithm is discussed. A hybrid differential evolution algorithm is also developed to improve the solution quantity. Numerical results show that the hybrid algorithm is capable of obtaining high-quality solutions and exhibits a competitive展开更多
基金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.
基金supported by the National Natural Science Foundation of China(Grant Number 61573264).
文摘As a complicated optimization problem,parallel batch processing machines scheduling problem(PBPMSP)exists in many real-life manufacturing industries such as textiles and semiconductors.Machine eligibility means that at least one machine is not eligible for at least one job.PBPMSP and scheduling problems with machine eligibility are frequently considered;however,PBPMSP with machine eligibility is seldom explored.This study investigates PBPMSP with machine eligibility in fabric dyeing and presents a novel shuffled frog-leaping algorithm with competition(CSFLA)to minimize makespan.In CSFLA,the initial population is produced in a heuristic and random way,and the competitive search of memeplexes comprises two phases.Competition between any two memeplexes is done in the first phase,then iteration times are adjusted based on competition,and search strategies are adjusted adaptively based on the evolution quality of memeplexes in the second phase.An adaptive population shuffling is given.Computational experiments are conducted on 100 instances.The computational results showed that the new strategies of CSFLA are effective and that CSFLA has promising advantages in solving the considered PBPMSP.
文摘Fabric dyeing is a critical production process in the clothing industry and heavily relies on batch processing machines(BPM).In this study,the parallel BPM scheduling problem with machine eligibility in fabric dyeing is considered,and an adaptive cooperated shuffled frog-leaping algorithm(ACSFLA)is proposed to minimize makespan and total tardiness simultaneously.ACSFLA determines the search times for each memeplex based on its quality,with more searches in high-quality memeplexes.An adaptive cooperated and diversified search mechanism is applied,dynamically adjusting search strategies for each memeplex based on their dominance relationships and quality.During the cooperated search,ACSFLA uses a segmented and dynamic targeted search approach,while in non-cooperated scenarios,the search focuses on local search around superior solutions to improve efficiency.Furthermore,ACSFLA employs adaptive population division and partial population shuffling strategies.Through these strategies,memeplexes with low evolutionary potential are selected for reconstruction in the next generation,while thosewithhighevolutionarypotential are retained to continue their evolution.Toevaluate the performance of ACSFLA,comparative experiments were conducted using ACSFLA,SFLA,ASFLA,MOABC,and NSGA-CC in 90 instances.The computational results reveal that ACSFLA outperforms the other algorithms in 78 of the 90 test cases,highlighting its advantages in solving the parallel BPM scheduling problem with machine eligibility.
文摘In this paper we study the problem of scheduling a batching machine with nonidentical job sizes. The jobs arrive simultaneously and have unit processing time. The goal is to minimize the total completion times. Having shown that the problem is NP-hard, we put forward three approximation schemes with worst case ratio 4, 2, and 3/2, respectively.
基金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.
文摘Planning and scheduling is one of the most important activity in supply chain operation management.Over the years,there have been multiple researches regarding planning and scheduling which are applied to improve a variety of supply chains.This includes two commonly used methods which are mathematical programming models and heuristics algorithms.Flowshop manufacturing systems are seen normally in industrial environments but few have considered certain constraints such as transportation capacity and transportation time within their supply chain.A two-stage flowshop of a single processing machine and a batch processing machine are considered with their capacity and transportation time between twomachines.The objectives of this research are to build a suitable mathematical model capable of minimizing the maximum completion time,to propose a heuristic optimization algorithm to solve the problem,and to develop an applicable program of the heuristics algorithm.AMixed Integer Programming(MIP)model and a heuristics optimization algorithmwas developed and tested using a randomly generated data set for feasibility.The overall results and performance of each approach was compared between the two methods that would assist the decision maker in choosing a suitable solution for their manufacturing line.
文摘The casting production process typically involves single jobs and small batches,with multiple constraints in the molding and smelting operations.To address the discrete optimization challenge of casting production scheduling,this paper presents a multi-objective batch scheduling model for molding and smelting operations on unrelated batch processing machines with incompatible job families and non-identical job sizes.The model aims to minimise the makespan,number of batches,and average vacancy rate of sandboxes.Based on the genetic algorithm,virus optimization algorithm,and two local search strategies,a hybrid algorithm(GA-VOA-BMS)has been designed to solve the model.The GA-VOA-BMS applies a novel Batch First Fit(BFF)heuristic for incompatible job families to improve the quality of the initial population,adopting the batch moving strategy and batch merging strategy to further enhance the quality of the solution and accelerate the convergence of the algorithm.The proposed algorithm was then compared with multi-objective swarm optimization algorithms,namely NSGA-ll,SPEA-l,and PESA-ll,to evaluate its effectiveness.The results of the performance comparison indicate that the proposed algorithm outperforms the others in terms of both qualityand stability.
基金supported by the National Natural Science Foundation of China(No.61573362).
文摘We investigate the problem of the online scheduling with kind release times and job compatibilities on a single unbounded parallel-batch machine to minimize makespan.The kind release times(KRT)means that under the online setting no jobs can be released when the machine is busy.What associated with each job J_(j)are its normal processing time P_(j)and release time r_(j).Two jobs J_(i)and J_(j)are called compatible if max(p_(i),P_(j))≤(1+a)min(p_(i),P_(j)),where a is a given positive constant.Compatible jobs could be processed in the same batch.We derive a best possible online algorithm with a competitive ratio of 1+√λ^(2)-λ+1-λ,whereλ=a/(1+a).
基金This research was supported in part by the National Natural Science Foundation of China(Nos.11771406,11571321 and U1504103).
文摘This paper considers competitive project scheduling on two unbounded parallel batch machines.There are two competing firms,and each firm has an unbounded parallel batch machine.All projects must be performed in batches by Firms 1 and 2 on their machines,respectively.The profit that each firm obtains from each project depends on whether the firm finishes the job before or after its competitor.In the first problem,given a feasible schedule for Firm 1,the objective is to find an optimal schedule to maximize the total reward for Firm 2 under the given schedule for Firm 1.The corresponding total reward for Firm 1 is called the worst-case total reward of the given schedule for Firm 1.In the second problem,the objective is to find an optimal schedule for Firm 1 to maximize the worst-case total reward.We provide optimal algorithms for the two problems,respectively.
基金supported in part by National Natural Science Foundation of China (Grant Nos. 71690232 and 71371015)by National Science Foundation (Grant Nos. CMMI-1435800 and CMMI-1536978)
文摘This study addresses the problem of two-stage scheduling on batch and single machines with limited waiting time constraint; thus, the makespan is minimized.A mixed-integer linear programming model is proposed for this problem. Three tight lower bounds and a heuristic algorithm are developed. The worst-case performance of the proposed algorithm is discussed. A hybrid differential evolution algorithm is also developed to improve the solution quantity. Numerical results show that the hybrid algorithm is capable of obtaining high-quality solutions and exhibits a competitive
