Parallel Machine Scheduling With Batch Setup Time And Mold Quantity Constraint

Parallel machine scheduling problem is one of the most difficult scheduling problem,and it is very common in the real world,and widely studied in academy and industry field.This paper is inspired from a real production problem in a typical footwear factory and reduce the problem to a Parallel machine scheduling problem with setup time and mold constraint.It can be named as Pm|STsi,b,mold quantity|Cmax,in which Pm for m identical parallel machine,STsi b for sequence independent batch setup time,mold quantity for considering mold quantity constraint,and Cmax for the objective is minimizing the makespan。To solve the problem,the paper provides an integer programing model,and proposes several heuristic rules and scheduling mechanisms.Based on the integer programing model,heuristic rules and scheduling mechanisms,this paper proposes 3 algorithms,which are LSTE(List Scheduling and Try-and-Error Heuristic),PLSS(Partitioning,List Scheduling and Splitting Heuristic)and MLSS(Modified List Scheduling and Splitting Heuristic).The result of computational experience shows that LSTE outperforms in solution quality with a relatively long but acceptable runtime.The pre-allocating mechanism improve the solution quality,but it will increase the computing time.The paper also shows that thought LPT is a classic heuristic,but simply using it without improvement,the result often turns bad.And the good result of application in the actual production management problem also verifies the effectiveness of LSTE.The core idea of the LSTE heuristic can be described as follow:firstly,allocating some given available time and run with the modified LBT to check if the schedule can be finished within the given available time.If it successes,then stop;else if it fails,then allocating more time.Repeating the method until it stops.The paper gives a bottom bound for the available time and actually it is very close to Cmax*.Which guarantee the heuristic can find the optimal and nearly optimal solution within fewer time.