Mathematical modelling is the first step in using mathematical methods to solve a practical problem. But for scheduling problem, there is a big difficult for some order related constrains to be depicted in formula. I think it is impossible to obtain an general model for different problems, but we can try on concrete problems. I have interesting on mathematical modelling, if you have any problem, we can discuss it! 

Read please В.С. Михалевич, В.А. Трубин, Н.З. Шор Оптимизационные задачи производственно транспортного планирования (in Russian). 

Dear Behrad,

you can find a lot of mathematical models concerning different scheduling issues, i.e. single machine, flow shop, job shop, parallel machines and hybrid systems as well.

Most of papers usually use the mathematical programming (MP) for solving small sized issues. On the other hand, evolutionary computation as well as metaheuristcs are employed to tackle large sized issues, once their efficacy has been tested through the global optima found by the MP for small sized test cases.  Indeed, most scheduling problems are NP-hard so that justifies why mathematical programming is not so diffused for scheduling applications where the best trade-off between quality of solutions and computational times has to be ensured.

good luck!

Antonio

Dear Behrad,

You can consult Baptiste P., Le Pape C., Nuijten W. Constraint-based Scheduling. Kluwer Academic Publishers. 2001. 198 pp.

Several integer programming formulations of machine scheduling problems are surveyed in this paper:

http://web.mit.edu/schulz/www/epapers/queyranne-schulz.pdf

I can also recommend this book as a general text on modelling skills in optimisation:

http://eu.wiley.com/WileyCDA/WileyTitle/productCd-1118443330.html

thanks for all quick responses to this Question, maybe i should restate my question more specifically although I am still looking for a general approach to formulating scheduling problem with Mathematical programming.

actually my kind of problem consist of ordering some finite services per client in static (or maybe dynamic) and also optimize the time of service for each client where each service time has its own effect on the utility function of each client. the effect of service time on the utility function is highly dependent on ordering of the service.

Yes of course you can model any scheduling problem with Mathematical model and after that write it on a solver like Cplex or implement your own exact method like brunch and bound. But what do you mean by a "general approach "? you can find a large variety of formulating scheduling problem in the literature and what you can do is trying to be inspired about that works like how the constraints are formulated and try to formulate "mathematically" the constraints of your problem", but a "GENERAL" formulation that you can apply to any scheduling problem?!! No, I don't think so,... maybe two or three constrains but not all the model because each problem has his specific contraints to take on concideration

Many Scheduling problems are NP Complete (which roughly means that they can be transformed to another NP Complete problem in theoretically linear time) ... You can find many such conversion/transformations in literature. Still, based on my limited knowledge, a General Scheduling Problem Formulation (covering all types of scheduling scenarios) has not been discovered, yet. 

As Yakov mentioned, Constraint-Programming (CP) is a good framework for modeling and solving scheduling problems. Modern CP approaches have extended the mathematical concepts that can be used to model scheduling problems (thanks to the notions of interval variables and function variables) and efficient (and exact) resolution algorithms are available. A good example is CP Optimizer, the CP optimization engine available in IBM CPLEX Optimization Studio (you can start with this introductory presentation: http://www.slideshare.net/PhilippeLaborie/an-introduction-to-cp-optimizer).

ok for clarifying the subject better, lets I have a CP problem that I wish to convert it into a standard optimization problem. a standard optimization problem consists of an objective to be minimized subject to the intersection of multiple inequalities  and general inequalities that are called the feasible set of the optimization problem.I have brought my CP in a raw form in the attached jpg file which my goal is to convert it to a standard optimization problem.

What you describe is a mathematical formulation of your optimization problem and this is indeed a prerequisite before trying to solve it.

Now, if you want to solve your problem you need to re-formulate it in a way that is strictly equivalent but that is understood by the resolution approach you are using.

If, for instance, you want to solve your problem using a Mixed Integer Programming engine, you will for example have to reformulate your constraints t_k != t_i as a set of linear constraints (probably by introducing some big-Ms).

My point is that scheduling problems are often difficult to model in MIP because they often imply to introduce a large number of variables (for instance a boolean variable x_it for each possible time value t stating that an activity i starts at time t) and/or a large number of constraints (like the quadratic number of linear constraints to model the quadratic number of constraints t_k != t_i in your mathematical formulation). And these models are difficult to solve because of their size (and also because the LP relaxation is often not very tight for these problems).

As an alternative, CP provides a richer set of variables, constraints and expressions that, especially for scheduling problems, makes it easier to reformulate your mathematical formulation into an equivalent CP formulation. For instance CP provides global constraints like AllDifferent(x1,...,xn) that globally handles a set of disequalities xi != xj, typically you would use one instance of this constraint to model the t_k != t_l constraints. If the t_k's would represent some activities (with non-unit duration), you could define them as 'interval variables' and define a 'noOverlap' constraint on the set of activities.

In general CP formulations for scheduling problems are much more compact than MIP ones (quite often, the size of the CP model grows linearly with the size of the data that defines the problem instance). They are also more natural to write (though, I agree this is a bit more subjective). And as far as resolution is concerned, engines like CP optimizer are generally very efficient and continuously improve. For instance for the famous job-shop scheduling problem you mention, a comparison between a CP Optimizer model, a set of state-of-the-art MIP formulations and state-of-the-art "jobshop dedicated" algorithms is provided in this recent article:

W.W. Ku and J.C. Beck. "Mixed Integer Programming Models for Job Shop Scheduling: A Computational Analysis". Computers & Operations Research. Vol 73, p165-173, Sept. 2016.

phillipe you have guided me on this topic very smart and and i am too much appreciated for both of your answers! i would take a look at this articles which I guess is my lost ring!

though your answer was sufficiently acceptable but do you know if any SDP /SOCP  relaxation to job shop scheduling exists?