The theoretical research literature on Manufacturing Schedule Optimisation has yielded few applications of dynamic schedule optimisation to actual manufacturing situations. This is particularly true of the classical job-shop scheduling model. Conventional job-shop scheduling problem (JSP) approaches were found to be based on an over simplified assumption set and a single optimisation objective. Most JSP algorithms neglect issues such as sequence-dependent set-ups, and parallel resources. An actual job-shop scheduling problem in a case study firm is used to identify the deficiencies in the traditional JSP solution approaches. A more realistic scheduling model was formulated and addressed using Constraint Satisfaction Problem (CSP) formulation and heuristic techniques. This combined heuristic and CSP approach was found in practice to be able to deal with an industrial scale problem and achieved superior plant performance in terms of order tardiness and machine utilisation. This approach represented much more effectively the real world manufacturing problem than the conventional approach.