Study On Theory And Method Of Multi-objective Scheduling Problems With Controllable Processing Times

Shop scheduling problem with controllable processing times(CPT)is one of the most crucial combinatorial optimization problems to be solved urgently in the modern manufacturing systems.In the traditional shop scheduling problems,job processing times are usually deemed to be fixed.However,job processing times can be controlled by allocating available resources(e.g.,fuel,human resouce,machine,energy and finance)in the practical production.Meanwhile,compressing job processing times can improve production efficiency to some extend,thus,job processing times are usually adjusted in the practical production.Obviously,condsideration of controllable processing times in shop scheduling problems is more close to the practical production.However,compared with the traditional shop scheduling problems,it will increase the difficulty of problem-sloving because of considering the controllable processing times.For this reason,the first study on this field can be traced back to 1980,but most research is mainly focused on relatively simple signle machine environment.Obviously,there is few studies reported on the complex shop scheduling problems.Additionally,controlling processing times need to consume extra resources,which also leads to the increase of the cost.Therefore,the shop scheduling problem with controllable processing times is a multi-objective optimization problem in nature.Based on the above reasons,this paper makes a system and deep research on various types of multi-objective shop scheduling problems with controllable processing times.The main work of this paper is as follows:For the single machine scheduling problem with controllable processing times,this paper constructs a mathematical model for minimizing the total tardiness and total extra resource consumption,and proposes a hybrid algorithm(MODGWO)based on genetic algorithm(GA)and grey wolf optimizer(GWO).According to the characteristic of such a problem,a new discrete encoding schema is designed.This encoding schema contains two layers information:job sequence vector and the job practical processing time vector.The feasibility and effectiveness of this encoding schema has been validated by conducting an experiment.To improve the diversity and convergence of the proposed algorithm,two kinds of strategies are proposed to enhance its performance.To evaluate the performance of MODGWO,it is compared with other classical MOEAs including NSGA-?,SPEA2 and PAES.Experimental results show that the MODGWO is superior to other MOEAs on most problems.For the unrelated parallel machine scheduling problem with controllable processing times,this paper formulates a mathematical model considering sequence-dependent setup times(SDST).The objectives of this problems are to minimize the makespan and total extra resource consumption simultaneously.To solve this problem,this paper presents a hybrid algorithm based on GA and virus optimization algorithm(MODVOA).To adapt to the characteristic of such a problem,a new discrete encoding schema is designed.To evaluate the performance of MODVOA,it is compared with other MOEAs including NSGA-II,SPEA2 and MODGWO.Experimental results show that MODVOA is superior to other MOEAs on most problems.For the flow shop scheduling problem with controllable processing times,this paper first formulates a mathematical model for minimizing makespan and total machine load.This model considers SDST and job dependent transportation times(JDTT).Single machine scheduling and flow shop scheduling problems have the common characteristic(i.e.,both need to perform the job permutation).Therefore,based on the proposed algorithm in the single machine scheduling problem with controllable processing times,we propose a multi-objective discrete grey wolf optimizer(MODGWO)to address such a scheduling problem.According to the characteristic of this problem,one reduction machine load strategy is used to adjust the number of machines aiming to minimize the machine load.To evaluate the effectiveness of the proposed MODGWO,we compare it with other well-known multi-objective evolutionary algorithms including NSGA-??SPEA2 and MODVOA on a set of instances.Experimental results demonstrate that the proposed MODGWO is significantly better than its compared algorithms on most instances.For the flexible job shop scheduling problem with controllable processing times,this study formulates a mathematical model with the objectives of minimizing both the makespan and the total additional resource consumption.Unrelated parallel machine scheduling and flexible job shop scheduling problems have one common characteristic(i.e.,both need to select available machine).Therefore,based on the proposed algorithm in the unrelated parallel machine scheduling problem with controllable processing times,we design a new multi-objective discrete virus optimization algorithm(MODVOA)with a three-part representation for each virus,an improved method for yielding the initial population,and an ensemble of operators for updating each virus.To further improve the exploitation,a problem-specific exploitation mechanism is implemented in the later stage of the search process.Finally,to evaluate the effectiveness of the MODVOA,the MODVOA is compared with other well-known multi-objective evolutionary algorithms including NSGA-??SPEA2 and MODGWO.Experimental results on randomly generated instances demonstrate that the proposed MODVOA can achieve a better performance than other algorithms for solving such problems.Based on the above theoretical fruits and the workshop production situation,this paper analyses the existing multi-objective scheduling problems with controllable processing times in the practical production applications.Then,the theoretical fruits are applied to the practical applications.Experimental results certify the effectiveness of the proposed multi-objective scheduling optimization algorithm.Finally,the above work and novel points are summarized,and the future research directions are discussed.