Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem |
| |
Authors: | Fabrice Tercinet Emmanuel Néron Christophe Lenté |
| |
Institution: | 1. Laboratoire d’Informatique de l’Université Fran?ois Rabelais de Tours, EA2101, Tours, France 2. Department of Computer Sciences, Polytech’Tours, 64 av. Jean Portalis, 37200, Tours, France
|
| |
Abstract: | This paper deals with an extension of energetic reasoning, using some efficient lower bounds of the bin-packing problem, to get tight lower bounds for the P|r
i
, q
i
|C
max. The link between P||C
max and bin-packing problem is well-known. Our purpose is to extend the use of efficient lower bounds of the bin-packing problem to P|r
i
, q
i
|C
max. We focus on some time-intervals, to compute the mandatory parts of activities within this time-interval and then to deduce an associated bin-packing instance. Thus, lower bounds of the bin-packing problem are used to get new satisfiability tests for the parallel machine problem. We also propose to extend the classical time-bound adjustments of release dates and deadlines to efficiently use bin-packing lower bounds. Experimental results that prove the efficiency of our approach on several kind of instances are reported. |
| |
Keywords: | Parallel machine scheduling problem Lower bound Bin-packing Energetic reasoning |
本文献已被 SpringerLink 等数据库收录! |
|