A heuristic-based hybrid solution for parallel machine scheduling problems with earliness and tardiness penalties

An identical parallel machine scheduling problem with earliness and tardiness penalties is studied. First, a hybrid method adopting the meta-heuristics, e.g., the simulated annealing method combined with list scheduling techniques is proposed, where the heuristic procedure MPA (minimum penalty increase assignment) and the SD (start-time decision) are newly introduced. Then, through several computational experiments, the effectiveness and the potential of the proposed method are investigated.