| 1. Identity statement | |
| Reference Type | Journal Article |
| Site | mtc-m16.sid.inpe.br |
| Holder Code | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
| Identifier | 6qtX3pFwXQZsFDuKxG/DbL2M |
| Repository | sid.inpe.br/marciana/2004/08.17.14.34 (restricted access) |
| Last Update | 2004:08.17.03.00.00 (UTC) administrator |
| Metadata Repository | sid.inpe.br/marciana/2004/08.17.14.34.43 |
| Metadata Last Update | 2018:06.05.01.28.42 (UTC) administrator |
| Secondary Key | INPE-11220-PRE/6669 |
| ISBN/ISSN | 0377-2217 |
| ISSN | 0377-2217 |
| Citation Key | LorenaNarc:1996:ReHeGe |
| Title | Relaxation heuristics for a generalized assignment problem  |
| Project | Otimização combinatória |
| Year | 1996 |
| Month | June |
| Access Date | 2024, Apr. 28 |
| Secondary Type | PRE PI |
| Number of Files | 1 |
| Size | 546 KiB |
| 2. Context | |
| Author | 1 Lorena, Luiz Antonio Nogueira 2 Narciso, M. G. |
| Resume Identifier | 1 8JMKD3MGP5W/3C9JHMQ |
| Group | 1 LAC-INPE-MCT-BR |
| Affiliation | 1 Instituto Nacional de Pesquisas Espaciais, Laboratório Associado de Computação e Matemática Aplicada (INPE.LAC) |
| Journal | European Journal of Operational Research |
| Volume | 91 |
| Number | 3 |
| Pages | 600-610 |
| History (UTC) | 2005-06-13 12:41:06 :: sergio -> administrator :: 2006-09-28 22:36:23 :: administrator -> sergio :: 2008-01-07 12:49:57 :: sergio -> administrator :: 2018-06-05 01:28:42 :: administrator -> marciana :: 1996 |
| 3. Content and structure | |
| Is the master or a copy? | is the master |
| Content Stage | completed |
| Transferable | 1 |
| Content Type | External Contribution |
| Keywords | COMPUTER SCIENCE Lagrangian function Heuristic methods Relaxation method (mathematics) COMPUTAÇÃO APLICADA Função lagrangiana Métodos heurísticos Método de relaxação (matemática) |
| Abstract | We propose relaxation heuristics for the problem of maximum profit assignment of n tasks to m agents (n > m), such that each task is assigned to only one agent subject to capacity constraints on the agents. Using Lagrangian or surrogate relaxation, the heuristics perform a subgradient search obtaining feasible solutions. Relaxation considers a vector of multipliers for the capacity constraints. The resolution of the Lagrangian is then immediate. For the surrogate, the resulting problem is a multiple choice knapsack that is again relaxed for continuous values of the variables, and solved in polynomial time. Relaxation multipliers are used with an improved heuristic of Martello and Toth or a new constructive heuristic to find good feasible solutions. Sh heuristics are tested with problems of the literature and random generated problems. Best results are less than 0.5% from the optimal, with reasonable computational times for an AT/386 computer. It seems promising even for problems with correlated coefficients. |
| Area | COMP |
| Arrangement | urlib.net > BDMCI > Fonds > Produção anterior à 2021 > LABAC > Relaxation heuristics for... |
| doc Directory Content | access |
| source Directory Content | there are no files |
| agreement Directory Content | there are no files |
| 4. Conditions of access and use | |
| Language | en |
| Target File | relaxation heuristics.pdf |
| User Group | administrator sergio |
| Visibility | shown |
| Copy Holder | SID/SCD |
| Archiving Policy | denypublisher denyfinaldraft36 |
| Read Permission | deny from all and allow from 150.163 |
| 5. Allied materials | |
| Next Higher Units | 8JMKD3MGPCW/3ESGTTP |
| Dissemination | WEBSCI; PORTALCAPES. |
| Host Collection | sid.inpe.br/banon/2003/08.15.17.40 |
| 6. Notes | |
| Empty Fields | alternatejournal archivist callnumber copyright creatorhistory descriptionlevel documentstage doi e-mailaddress electronicmailaddress format isbn label lineage mark mirrorrepository nextedition notes orcid parameterlist parentrepositories previousedition previouslowerunit progress readergroup rightsholder schedulinginformation secondarydate secondarymark session shorttitle sponsor subject tertiarymark tertiarytype typeofwork url versiontype |
| 7. Description control | |
| e-Mail (login) | marciana |
| update | |