Two-agent-based single-machine scheduling with switchover time to minimize total weighted completion time and makespan objectives

Shesh Narayan Sahu, Yuvraj Gajpal () and Swapan Debbarma
Additional contact information
Shesh Narayan Sahu: National Institute of Technology, Agartala
Yuvraj Gajpal: University of Manitoba
Swapan Debbarma: National Institute of Technology, Agartala

Annals of Operations Research, 2018, vol. 269, issue 1, No 29, 623-640

Abstract: Abstract We consider a single-machine scheduling problem with two-agents, each with a set of non-pre-emptive jobs, where two agents compete for the use of a single processing resource. A switchover time arises whenever a job of one agent is processed after a job of another agent. Each agent wants to minimize a certain objective function, which depends upon the completion time and switchover time of their own jobs only. This paper considers the minimization of total weighted completion time of the first agent subject to an upper bound on the makespan of the second agent. We introduce some properties to the problem. The properties describe the structure of an optimal solution which is being used for developing an optimal algorithm. We propose an optimal algorithm, a simple heuristic algorithm, and a particle-swarm-based meta heuristic algorithm to solve the problem. The heuristic algorithm is based on the weighted shortest process time-first rule. The performances of the heuristic and particle swarm algorithms are evaluated on randomly generated problem instances. We perform the numerical analysis to reveal the properties of the proposed problem.

Keywords: Scheduling; Competing agents; Heuristic; Combinatorial optimization; Particle swarm optimization (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/s10479-017-2515-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:annopr:v:269:y:2018:i:1:d:10.1007_s10479-017-2515-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2515-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().