Why it is recommended to compare the relaxed versions of each formulation to deduce the running time (and more precisely about the B&B tree size)?
Generally, better (= tighter) is the relaxation of an integer optimization model, better should work a brand-and-bound tree solution approach to this model. Nevertheless, there exist some NP-hard problems for which the cost of the linear relaxation is equal to the cost of an optimal integer solution. Indeed, despite having a cost equal to the optimum integer solution, the relaxed solution may be highly fractional, then bringing no insightful information for the search of an integer one. In conclusion, just looking at the value of the linear relaxation will not inform you so much about the running time of the resolution of the original integer model (by B&B or any other approaches).
Are all the scheduling problems NP-hard? Otherwise how to determine if a problem is NP-hard or not?
Some scheduling problems are easy to solve, by polynomial-time (or even linear-time) combinatorial algorithms. But these problems are generally very basic, not realistic OR problems as you can find in the industry. For example, here is a paper on such an easy problem. To learn about NP-hardness, have a look at the Wikipedia page on the topic; this is a good starting point. You will also find a lot of resources on the web.
