Open AccessBest-case lower bounds in a group sequence for the job shop problem
Author(s) -
Guillaume Pinot,
Nasser Mebarki
Publication year - 2008
Publication title -
hal (le centre pour la communication scientifique directe)
Language(s) - English
Resource type - Conference proceedings
DOI - 10.3182/20080706-5-kr-1001.1295
Subject(s) - sequence (biology) , group (periodic table) , job shop , computer science , job shop scheduling , flow shop scheduling , mathematical optimization , mathematics , computer network , chemistry , biochemistry , routing (electronic design automation) , organic chemistry
International audienceGroup sequencing is a well-studied scheduling method for the job shop problem. The goal of this method is to have a sequential flexibility during the execution of the schedule and to guarantee a minimal quality corresponding to the worst case. But the best case quality of a group sequence should also be interesting. This article presents new methods to evaluate the best case quality for any regular objective function. More particularly, three new makespan lower bounds are presented. The experiments performed with these lower bounds exhibit very good performances