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.