A novel neighborhood structure for job shop scheduling

An novel neighborhood structure named “space squeezing neighborhood” is proposed in this paper for job shop scheduling problems. To form such neighborhood, the space-squeezing operator moves some procedures on a certain machine backwards by means of an elaborate method, to decrease spaces existing on the machine´s processing queue, consequently improves the global scheduling solution of a job shop problem. Taking in the space-squeezing neighborhood as a necessary part, a taboo search algorithm is constructed solving JSP problems. Computational experiments show that the operator can greatly promotes searching ability of the algorithm.