Application Of Branch And Bound Algorithm In Order Scheduling With Deterioration And Learning Effect

In the fiercely competitive environment,companies need to deliver products in a timely and accurate manner to ensure high quality and efficient service and competitiveness.Especially for enterprises who use Make to Order production mode.Their order delivery ability determines the level of service they provide to customers.While order picking and packaging are the most important part in the process.In some labor-intensive transshipment centers,order picking is usually based on human cause of the specificity of the product or the individual requirements of the customer for the order.For example,the picking of fresh produce requires employees to have a high level of recognition ability.People-oriented picking and packaging activities are often accompanied by learning and deterioration.The cognitive skills and experience of employees continue to increase,then order processing time is gradually reduced.At the same time,employees are more likely to get worse due to forgetting,fatigue,etc.,and order processing time is increased compared to standard processing time.Based on the manual order picking and packaging process,this paper forms the following two types of research questions based on the learning and deterioration,combined with the order release time.The first type of problem is a scheduling problem with learning effect and release time.After the order is ready,the orders are picked and packaged in turn,and the two processes are uninterrupted.Due to the learning effect of the workers,the processing time is reduced.The goal is to minimize the completion time and maximum completion time of all orders.A model is established for this problem.(1)For the small-scale problem with a small number of orders,branch and bound algorithm is designed.The improvement strategy includes designing new upper and lower bounds.The upper bound is the solution obtained by the heuristic algorithm,and the lower bound is obtained by means of induction.In order to evaluate the efficiency of the algorithm and the heuristic algorithm,an experiment is carried out,which records the average number of nodes,the maximum number of nodes and the running time of the two algorithms,and the error percentage.Experimental results show that the branch and bound algorithm is effective for small-scale problems.The heuristic algorithm has a small percentage error and is basically distributed within 0.3%.Branch and bound algorithm take longer time,but it takes only a few milliseconds to solve small-scale problems.(2)For the large-scale order scheduling problem,memetic algorithm with a new local search strategy and global search strategy is designed.In order to verify the effectiveness of the algorithm,the algorithm is compared with NSGA-11,PSO,QGA,MOEA/D and SA algorithm.The indicators are HV and IGD.The results show that the improved algorithm has the smallest IGD and the largest HV,which means the strategy is effective.When the number of orders is small and the change is not obvious,the number of nodes of the branch and bound algorithm and the error percentage of the MFL heuristic algorithm are significantly affected by the change of the release time;the HV value of the memetic algorithm is significantly affected by the change in the number of orders and the learning efficiency.The second type of problem is a scheduling problem with deterioration and release time.After the orders are ready,the workers group the orders and then pick them one by one.As time goes on,the workers have a deteriorating effect,and the processing time of subsequent orders becomes longer.The goal is to minimize the maximum completion time.A model is based for this problem.Two cases are considered in this problem.In the first case,group number of orders are determined in advance.The problem can be processed in the polynomial time.Exact solution algorithm 1 is designed.In the second case,the number of order groups need to be decided,the branch and bound algorithm is improved.New upper and lower bounds are designed.The upper bound is obtained by new heuristic algorithm 2,and the lower bound is obtained by means of induction.In order to verify the effectiveness of the branch and bound algorithm,we compared it with algorithm 1 and algorithm 2.The average and maximum running time of the three algorithms are recorded respectively.The error percentage of algorithm 2 is recorded.From the CPU time,the results show that the algorithm 1 takes the most time,followed by the algorithm 2 and the branch and bound algorithm,the time cost difference between the two is small.At the same time,the branch and bound algorithm designed in this paper can solve the scheduling problem with order size of 300 and machine number of 11 in 15 or 16 milliseconds.Although the time consuming is longer than the heuristic algorithm 2,but the total time is short,the branch and bound algorithm is effective.From the error percentage,the maximum value of Algorithm 2 is 0.068,which is no more than 10%.The mean value is around 0.000,and the maximum is 0.003,which is not more than 0.01.It is known that Algorithm 2 performs well.In summary,the research shows that designing new upper bound through heuristic algorithm and new lower bound for branch and bound algorithm can achieve a balance between the quality and efficiency of the solution.