Sum-of-Processing-Times-Based Two-Agent Single-Machine Scheduling with Aging Effects and Tardiness

Do Gyun Kim and Jin Young Choi

Mathematical Problems in Engineering, 2015, vol. 2015, 1-12

Abstract:

We consider a two-agent single-machine scheduling problem that minimizes the total weighted tardiness of one agent under the restriction that the second agent is prohibited from having tardy jobs. The actual processing times of all jobs are affected by a sum-of-processing-times-based aging effect. After showing the NP-hardness of the problem, we design a branch-and-bound (B&B) algorithm to find an optimal solution by developing dominance properties and a lower bound for the total weighted tardiness to increase search efficiency. Because B&B takes a long time to find an optimal solution, we propose a genetic algorithm as an efficient, near optimal solution approach. Four methods for generating initial populations are considered, and edge recombination crossover is adopted as a genetic operator. Through numerical experiments, we verify the outstanding performance of the proposed genetic algorithm.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2015/768148.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2015/768148.xml (text/xml)

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:hin:jnlmpe:768148

DOI: 10.1155/2015/768148

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().