A local search algorithm: minimizing makespan of deteriorating jobs with relaxed agreeable weights

In this paper, we consider the problem of minimizing makespan of n deteriorating jobs on a single machine. Rates of deterioration are job-dependent and constant with respect to the starting times. Jobs begin to deteriorate after a common critical date ‘d.’ The concept of relaxed agreeable weights is...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Anjulika Gupta, Prabha Sharma, Hemant Salwan
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2018
Materias:	90B99 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/550f34ab162141cf9c0fe29187f03a6f
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:550f34ab162141cf9c0fe29187f03a6f
record_format	dspace
spelling	oai:doaj.org-article:550f34ab162141cf9c0fe29187f03a6f2021-12-02T05:01:05ZA local search algorithm: minimizing makespan of deteriorating jobs with relaxed agreeable weights2192-440610.1007/s13675-017-0086-2https://doaj.org/article/550f34ab162141cf9c0fe29187f03a6f2018-03-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000940https://doaj.org/toc/2192-4406In this paper, we consider the problem of minimizing makespan of n deteriorating jobs on a single machine. Rates of deterioration are job-dependent and constant with respect to the starting times. Jobs begin to deteriorate after a common critical date ‘d.’ The concept of relaxed agreeable weights is introduced. It is shown that the problem is NP-hard. The condition of relaxed agreeable weights and the structure of the problem are used to show that our local search algorithm, to obtain a locally optimal solution, will require polynomial effort in the number of jobs.Anjulika GuptaPrabha SharmaHemant SalwanElsevierarticle90B99Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 6, Iss 1, Pp 29-54 (2018)
institution	DOAJ
collection	DOAJ
language	EN
topic	90B99 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90B99 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Anjulika Gupta Prabha Sharma Hemant Salwan A local search algorithm: minimizing makespan of deteriorating jobs with relaxed agreeable weights
description	In this paper, we consider the problem of minimizing makespan of n deteriorating jobs on a single machine. Rates of deterioration are job-dependent and constant with respect to the starting times. Jobs begin to deteriorate after a common critical date ‘d.’ The concept of relaxed agreeable weights is introduced. It is shown that the problem is NP-hard. The condition of relaxed agreeable weights and the structure of the problem are used to show that our local search algorithm, to obtain a locally optimal solution, will require polynomial effort in the number of jobs.
format	article
author	Anjulika Gupta Prabha Sharma Hemant Salwan
author_facet	Anjulika Gupta Prabha Sharma Hemant Salwan
author_sort	Anjulika Gupta
title	A local search algorithm: minimizing makespan of deteriorating jobs with relaxed agreeable weights
title_short	A local search algorithm: minimizing makespan of deteriorating jobs with relaxed agreeable weights
title_full	A local search algorithm: minimizing makespan of deteriorating jobs with relaxed agreeable weights
title_fullStr	A local search algorithm: minimizing makespan of deteriorating jobs with relaxed agreeable weights
title_full_unstemmed	A local search algorithm: minimizing makespan of deteriorating jobs with relaxed agreeable weights
title_sort	local search algorithm: minimizing makespan of deteriorating jobs with relaxed agreeable weights
publisher	Elsevier
publishDate	2018
url	https://doaj.org/article/550f34ab162141cf9c0fe29187f03a6f
work_keys_str_mv	AT anjulikagupta alocalsearchalgorithmminimizingmakespanofdeterioratingjobswithrelaxedagreeableweights AT prabhasharma alocalsearchalgorithmminimizingmakespanofdeterioratingjobswithrelaxedagreeableweights AT hemantsalwan alocalsearchalgorithmminimizingmakespanofdeterioratingjobswithrelaxedagreeableweights AT anjulikagupta localsearchalgorithmminimizingmakespanofdeterioratingjobswithrelaxedagreeableweights AT prabhasharma localsearchalgorithmminimizingmakespanofdeterioratingjobswithrelaxedagreeableweights AT hemantsalwan localsearchalgorithmminimizingmakespanofdeterioratingjobswithrelaxedagreeableweights
_version_	1718400828153266176

A local search algorithm: minimizing makespan of deteriorating jobs with relaxed agreeable weights

Ejemplares similares