In this study, preemptive shop scheduling problems have been considered, and two exact methods have been developed to minimize makespan. The first method is based on mathematical models. At first, a new MIBP model is presented. The dimensions of new model, despite available models, depend only on the number of jobs and machines, and the processing times have no effect on it. This model is used in an exact two-phase approach. In addition, different preemptive flow shop problems as special cases of pJ are studied, and the new mathematical model is specifically developed for them. Comparing new model with the best available model shows the higher efficiency of new model both theoretically and computationally. The second exact method is based on a disjunctive graph. After designing a new disjunctive graph for demonstrating pJ, an exact branch and bound algorithm is presented, and some lower bounds, dominance rules and other techniques are used to improve its efficiency. Computational experiments show that the presented method is much stronger than available methods in that it has been able to achieve the optimal answer of open benchmark problems, and solve problems with the size of and for the first time.
