Hi Lukasz,

Whenever the optimal solution is out of reach (which is quite often the case, especially for instances of big sizes), you can compare your solution to a lower bound. The aim is, of course, to be able to compute a lower bound of good quality i.e. as close as possible to the optimal solution. In a minimization problem the largest lower bound is the best.

The quality of the lower bound is very important, the closer it is to the optimal solution, the better your comparison is.  Indeed, if your lower bound is of poor quality, your analysis could suggest that your method is not very efficient while it actually is!

You could also compare your results to the so-called "best known solutions (BKS)", which are upper bounds. They are available for many test-beds. It can happen quite often that a BKS is an optimal solution that hasn't been proved to be so yet. Thus, they can be good comparison standards. That would be very interesting if you found solutions that are of better quality than the BKSs.

In fact, improving both lower and upper bounds allows to narrow the optimal interval. 

Best regards,

Imène.

I think that your problem is relevant to the following problem: How to evaluate my approximate solution A(D)? where LB(D)

Hi Lukasz,

Whenever the optimal solution is out of reach (which is quite often the case, especially for instances of big sizes), you can compare your solution to a lower bound. The aim is, of course, to be able to compute a lower bound of good quality i.e. as close as possible to the optimal solution. In a minimization problem the largest lower bound is the best.

The quality of the lower bound is very important, the closer it is to the optimal solution, the better your comparison is.  Indeed, if your lower bound is of poor quality, your analysis could suggest that your method is not very efficient while it actually is!

You could also compare your results to the so-called "best known solutions (BKS)", which are upper bounds. They are available for many test-beds. It can happen quite often that a BKS is an optimal solution that hasn't been proved to be so yet. Thus, they can be good comparison standards. That would be very interesting if you found solutions that are of better quality than the BKSs.

In fact, improving both lower and upper bounds allows to narrow the optimal interval. 

Best regards,

Imène.

Dear Gennady dear Imène,

its seems to be a good approach to find the the lower bound to compare it with the results Im obtaining from my greedy scheduler. However, I need to get familiar with the topic first. Do you have some papers in mind that I should read?

Thank you for your support!

Kind Regards,

Lukasz

Dear Lukasz,

you can obtain lower bounds by solving a relaxed version of your problem. For example, you could relax release dates or non-preemption constraints.

Another way to obtain lower bounds could be relaxing constraints from your problem's mathematical formulation so that it becomes similar to another well-known problem, and solve this relaxed version.

Network problems are important because they often happen to be used as a relaxation of some scheduling problems.

For further details, I would advise you to read the following for they provide many useful examples:

-http://www.utc.fr/~dsavoure/medias/lowerboundspm.pdf

-Handbook on Scheduling: From Theory to Applications by Błażewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., Weglarz, J. Springer editions.

I hope this helped,

Best regards,

Imène.

There have been great answers so far.  Here are some additional techniques I can suggest:

-If you can formulate your problem in Graham notation, it likely can be compared to another scheduling problem that have known methods to be cleanly bounded in polynomial time by some constant factor (or if you are lucky, can maybe be solved in polynomial time).

Let me give you a very quick but simple way of estimating a schedule (using one of the first-known approximation algorithms for the makespan problem on unrelated parallel machines by Ibarra and Kim in 1977, for more about it, see

O. Ibarra and C. Kim. Heuristic algorithms for scheduling independent tasks on

nonidentical processors. Journal of the ACM (JACM), 24(2):280–289, 1977.).

Do the following:  For each job, assign it to the machine for which it completes the earliest.  Upon assigning every job to a machine, return the schedule (this can be done very efficiently).  It is not too hard to prove that any greedy schedule will be bounded by the optimal makespan times the number of machines.  

A classic paper that gave the first 2-approximation algorithm for the makespan problem on unrelated parallel machine describes a p-relaxed procedure (similar to what Imène mentions) that can terminate in polynomial time can be a useful resource in the algorithmic end of optimization problems of this nature.  See, J. Lenstra, D. Shmoys, and E. Tardos. Approximation algorithms for scheduling

unrelated parallel machines. Mathematical Programming, 46(1–3):259–271, 1990.  

Personally, the venture of finding good bounds by considering special cases is a worthwhile venture.  I know it is something I am personally considering in my research along with the study of approximation algorithms.  It really doesn't take much to make an NP-hard scheduling problem out of anything in scheduling.  So the prospect of computing an efficient estimate of the optimal may be hard to obtain, but approximate ones are still in the grasps for some special cases (while others have limitations on approximations, if we assume P!=NP).  What I best suggest is formulating your problem in graham notation, then pursuing it by considering efficient methods others have found for finding approximately good schedules in polynomial time.  The rounding techniques are usually your best friend, but your problem may have special properties that can allot for better approximations without rounding.

Hope this helps!

For this purpose, you may find this article useful: http://www.sciencedirect.com/science/article/pii/037722179390182M . In this benchmark, optimal solutions for some instances are still unknown (due to NP-hardness nature of the problems), and in this case, the best known solutions (BKS) have been used.