In recent years, CP has been an effective method for solving satisfaction and optimization problems [1]}. There are a number of problem domains where CP is proven to be effective, and scheduling is one of these [2]}, [3]}, [4]}, [5]}. Moreover, CP has also been shown to be effective on JSS. The studies by [6]} and [7]}, investigated a CP and tabu search hybrid. Their results showed that this hybrid can generate solutions with low variability and are competitive with local search approaches. [4]} investigated JSS with setup times, and they showed that enhancing the search component of CP can prove to be very effective for this problem.
