SINGLE MACHINE FAMILY SCHEDULING WITH TWO COMPETING AGENTS TO MINIMIZE MAKESPAN

Guosheng Ding and Shijie Sun ()
Additional contact information
Guosheng Ding: School of Science, Nantong University, Nantong 226007, People's, Republic of China
Shijie Sun: Department of Mathematics, Shanghai University, Shanghai 200444, People's, Republic of China

Asia-Pacific Journal of Operational Research (APJOR), 2011, vol. 28, issue 06, 773-785

Abstract: We consider two-agent scheduling on a single machine, where there are job families and setup requirements exist between these families. Each agent's objective function is to minimize his own makespan. One of our goals is to find the optimal solution for one agent with a constraint on the other agent's makespan (constrained optimization). This problem is equivalent to the caudate Knapsack problem that we define in the paper. The other goal is to find single nondominated schedules (i.e., such that a better schedule for one of the two agents necessarily result in a worse schedule of the other agent), and to enumerate all nondominated schedules. Finally, two special cases, one with equal job processing times and the other with equal family setups are studied. We prove that the constrained optimization problems in both cases can be solved in polynomial time and that the cases have a polynomial number of nondominated schedules.

Keywords: Family scheduling; Multi-agent deterministic sequencing; setup (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S021759591100334X
Access to full text is restricted to subscribers

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:wsi:apjorx:v:28:y:2011:i:06:n:s021759591100334x

Ordering information: This journal article can be ordered from

DOI: 10.1142/S021759591100334X

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().