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

Anjulika Gupta (), Prabha Sharma () and Hemant Salwan ()
Additional contact information
Anjulika Gupta: R.V. College of Engineering
Prabha Sharma: The NorthCap University
Hemant Salwan: The NorthCap University

EURO Journal on Computational Optimization, 2018, vol. 6, issue 1, No 2, 29-54

Abstract: Abstract 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.

Keywords: Permutation polyhedra; Adjacency; Dominance; Local search; Deteriorating jobs; Relaxed agreeable weights; 90B99 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13675-017-0086-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjco:v:6:y:2018:i:1:d:10.1007_s13675-017-0086-2

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-017-0086-2

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().