Hello,

If your "due dates" are maximum allowable durations for each job, then you are good to use them as an upper bound on decision variable "t". But if you ask me, you need a more structural problem definition first.

Regards.

I assume the problem is: you want to schedule a production line (a machine run time, etc.) in order to minimize the total cost of production/run time. Here it seems that t(i) is your decision variables so it means you want to obtain optimum t(i), right? In your current format the constraints are not correct, see:

d(i) refers to due date for instance 4th Juni 2017

t(i) refers to time length for instance 4 days, 2 hours, etc.  

 So first of all, you need to harmonize your constraints: make them both in terms of time length. And you need to define the parameter types as well, see:

t(i)>=0 (because you don`t want negative time length, do you?)

And one more recommendation, most of the times there is a constraint which defines the sum of t(i) for a machine/production line. For instance, you may need to produce something before the day after tomorrow, see:

sum(t(i))

I think it is a simple formulation, please illustrate your problem more.

I want to model this as a Linear programming, as I simplified it earlier. my main question is the definition of variables, should I define "t" the length of task or the finish time of task? if none what should I define if as? also please tell me in a bi-objective optimization matter which one should I take into account Makespan and Cost or Daedlines and Cost?   Thank you so much for your time. Regards, Soroush safavi

Dear Mr.Ican, Mr.Baharmand and Mr.Heshmat

Thank you so much for your answer and your time, I simplified my problem to a small problem with two Variables to make it easier for others. I illustrate my problem more:

suppose we have some tasks(jobs) which have to scheduled on a Single machine, there are two criteria in this problem Time and Cost, and Time*Cost= Constant,

• if you want to meet deadlines you have to pay more in order to get the tasks completed earlier.
• if you want to get the jobs done cheaper you have to wait more and miss the deadline.

Hey soroush,

I think you should consider the variable 't' as length of tasks cause if you consider them as finishing time of jobs, then you will have problem in your objective function, I mean by considering them as finishing time you will multiply a wrong value to cost variable in your objective function. 

was it helpful? 

Hey Shahriar,

I my self think that is the correct definition for "t" but as earlier Mr.Baharmand Said:

"So first of all, you need to harmonize your constraints: make them both in terms of time length. And you need to define the parameter types as well"

Isn't that correct?

Yes of course it was very helpful:)

Thank you,

Soroush

Dear Soroush,

Consider  t as a variable such as the jobs completion time. but the cost is not variable, it is a parameter. 

yes he is completely right, I've didnt noticed that. So it is clear now, you should change due time ( di ) type as type of ti . sth like it: if d1 = 10 hours and d2 = 1 day = 24 hours

z=c1t1+c2t2 

0 < t1 < 10, 0 < t2  t1+t2

Dear Mahmoud,

thank you, I think according to what you and others said this model has some problem and I think I have to define some more variables to make the model accurate.

Thank you,

Regards,

Soroush

Dear Shahriar.

I still can't get the idea, unfortunately, because if I do as you said then calculating the cost base on 't' becomes hard, I have to use t1-ti-1 to calculate the cost of each task, and please notice that the bigger ti-ti-1 the less cost we have and vice versa.

thank you for your help.

Regards,

Soroush

OK now I understand that your problem is different from what I thought before. Now you are saying if time goes down costs goes up. This implies both time and cost being variables. And this means you are defining an objective function with quadratic terms which can not be solved within the current version. Why? Because as you said

c*t = constant so the objective function always respond z=constant(1) + constant (2)

Do you get my point? Here, again the problem is you need exact definition of your problem. Follow this:

What do you want to get after optimization? time, cost or both

How do you want? Max, Min, Max-Min, or Min-Max

How can you formulate the previous questions? time is limited to upper bound, budget is limited, etc.

Translate the previous into formulas: Min z = ...

Remember, if you want to have two criteria, then your problem goes under Multi-criteria decision making which can be multi-objective or multi-attribute. So do yourself a favor. Begin with very simple and raise it until you reach what you want. For instance, follow the below example.

We have one machines with two tasks with two different costs for every hour c(1) and c(2). Our products should begin with task 1 and then pass task 2 to be delivered in our final due. We need to minimize the total cost of tasks given that ... (here you define your constraints:). Our total budget is limited. We have to produce at least 40 products. Each product need 2 hours work by machine 1 and 4 hours work by machine 2.

Min z = C(total)

Sum[c (i) * t (i,d)] = C(total) %c and t refers to cost and time, i refers to task, d refers to days

Deadline = (Due_date - Current_date) * Sum[W(d)]   %W(d) refers to working hours of the machine for each day.

Sum t(i,d) =40

t(1,d) = product (d)* 2

t(2,d) = product (d)* 4

t(1,d) + t (2,d) 0 %ensures the machine completes the tasks everyday

This is very basic. In order to complete the scheduling, the model must be developed further.

Interesting discussion.

Formulation by Shahriar Minaee Jalil

z=c1t1+c2t2 

0 < t1 < 10, 0 < t2  t1+t2

Hello, first you must know what are the decision variables to search

second : define ressources and constraints.

The solution represents the values taken by different variables / your objective function is optimized.