Suppose we have a linear program (it may be integer, it probably doesn't matter).

Suppose the variables $t_j$ give the tardiness for job $j$, and we want to minimise something to do with this tardiness.

Now, there are at least two options that I know of:

1) Minimise total tardiness: $min \sum_j t_j$

2) Minimise maximum tardiness: $min_z\{z \geq t_j \forall j\}$

So here are the problems with these two: (1) will give a small number of total tardiness, however two solutions with the same total tardiness could look very different (one solution has many slightly tardy jobs, and another solution has only 1 tardy job, but it's extremely late). (2) prevents one exceptionally tardy job, however if only one job is tardy by $1$ unit, then all other jobs are now permitted to be tardy for free. (If a solution with $n$ jobs can be constructed with zero tardiness, then it's possible $n+1$ jobs will lead to one job being tardy by $1$ unit, but since we're only minimising the maximum tardiness, all other jobs can now be tardy by up to $1$ unit without any affect on the objective value).

A third approach which is a bit different would be to minimise the total number of tardy jobs. So if $\hat{t}_j$ is $1$ if job $t_j>0$, or $0$ otherwise: $min \sum_j \hat{t}_j$.

All of these can give wildly different solutions. I understand they are minimising different things (obviously), and I understand mathematics is a very precise science; so technically we are getting exactly what we've asked for. However, somehow, asking for (1), (2), or (3) alone seem to lack something "human". No human would produce a timetable with one exceptionally late jobs in favour of spreading lateness out a little and saying "it's okay - the total tardiness is low". Nor would a human let all jobs be late because one job has to be late and say "it's okay, one job is bit late so all jobs can be a bit late". Nor would they allow one job to be arbitrarily late and say "it's okay. Only one of the jobs is arbitrarily late".

So what is the solution? I don't know.

Perhaps multiply (1) and (2) together? Or some linear combination?


I more or less agree with your suggestion:

You have two objective functions. You must use both and assign a weight to each (according to your best criteria). Initially I would suggest 50% weight each and then fine tune, ie. 30% 1) and 70% 2), but always mantain de sum of weights unitary to maintain consistency or a reference while fine tuning.

  • $\begingroup$ In this case, it doesn't even make sense that the weights should sum to 1. It is the ratio of the weights that determines the solution. Since maximum tardiness and total tardiness are qualitatively very different (despite being in the same units), I don't think maintaining a scale is important at all. $\endgroup$ – timetabler1337 Jan 9 '14 at 5:05
  • $\begingroup$ I think the constant sum of weights (to 1) helps to mantain consistency or a reference while fine tuning on the proportions of the weights given to each objective function. $\endgroup$ – CAGT Jan 9 '14 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.