Abstract: An approach based on Bin-Packing algorithm and graph theory is proposed to avoid the hotspot and distribute heat evenly on chip surface during test scheduling.First several parallel test set （PTSs） are derived from graph models.Then Bin-Packing algorithm constructs an initial test schedule.A global optimal procedure gets the better test schedule finally.Experiment at results on ITC’02benchmark SoCs show that this method can effectively avoid hot-spot and distribute heat evenly at the expense of a little percentage of test time.