earticle

영어

Software development planning usually does not take any advantage of planning and scheduling techniques involving reasoning about time and resources, which are typical in the manufacturing area. This paper proposes a constraint-based model for the Job Shop Scheduling Problem to be solved using local search techniques. The model can be used to represent a multiple software process planning problem when the different (activities of) projects compete for limited staff. The main aspects of the model are: the use of integer variables which represent the relative order of the operations to be scheduled, and two global constraints, alldifferent (all the variable values are forced to be different from the others) and increasing (the variable values are forced to be greater than the previous ones in the sequence), for ensuring feasibility. The AllDifferent and Increasing constraints enforce the conjunction of one binary constraint, the not-equal constraint and the greater constraint respectively, for every pair of variables. By analyzing the set of all relations at the same time, both global constraints offer greater filtering power, enhancing the constraint model and the efficiency in the resolution of the problem. An interesting property of the model is that cycle detection in the schedules is implicit in the satisfaction of the constraints. In order to test the proposed model, a parameterized local search algorithm has been used, with a neighborhood similar to the Nowicki and Smutnicki one, which has been adapted in order to be suitable for the proposed model.