Modeling and solving static m identical parallel machines scheduling problem with a common server and sequence dependent setup times

- The static m identical parallel machines scheduling problem is addressed.
- Setup times are sequence dependent and setups are performed by a common server.
- A mixed integer linear programming model is developed for the problem.
- Metaheuristic based solution approaches are developed for the problem.
- The objective is to minimize the length of schedule (makespan).

This paper addresses the static m identical parallel machines scheduling problem with a common server and sequence dependent setup times. Initially, a mixed integer linear programming (MILP) model is presented for the problem to minimize the makespan. Due to the complexity of the problem, simulated annealing (SA) and genetic algorithm (GA) based solution approaches are developed. Subsequently, the performance of the proposed MILP model, SA and GA based solution approaches are compared with the performance of basic dispatching rules such as, shortest processing time first (SPT) and longest processing time first (LPT) over a set of randomly generated problem instances. The results of the computational experiments indicate that the proposed GA is generally more effective and efficient in solving this problem when it is compared to the proposed MILP model, SA, SPT and LPT.