Title: Two-agent single-machine scheduling with release times and deadlines

Authors: Yunqiang Yin; Shuenn-Ren Cheng; T.C.E. Cheng; Wen-Hung Wu; Chin-Chia Wu

Addresses: State Key Laboratory Breeding Base of Nuclear Resources and Environment, East China Institute of Technology, Nanchang, 330013, China. ' Graduate Institute of Business Administration, Cheng Shiu University, Kaohsiung County, No. 840, Chengcing Rd., Niaosong Dist., Kaohsiung City 83347, Taiwan. ' Dean's Office, Faculty of Business, The Hong Kong Polytechnic University, 11 Yuk Choi Road, Hung Hom, Kowloon, Hong Kong. ' Department of Business Administration, Kang-Ning Junior College, No. 137, Lane 75, Sec. 3, Kangning Rd., Neihu District, Taipei City 114, Taiwan. ' Department of Statistics, Feng Chia University, No. 100, Wenhwa Rd., Seatwen, Taichung, Taiwan

Abstract: Multiple-agent scheduling has attracted considerable research attention in recent years. However, studies of multiple-agent scheduling with release times and deadlines are few. In the presence of ready times, sometimes it is beneficial to wait for future job arrivals in constructing a schedule. Inspired by the importance of ready times, we study the single-machine two-agent scheduling problem with releases times and deadlines to minimise the number of tardy jobs of one agent under the restriction that the maximum lateness of the jobs of the other agent cannot exceed a given value Q. Having established that the problem is strongly NP-hard, we provide a branch-and-bound and a simulated annealing algorithm to search for the optimal and approximate solutions, respectively. The results of computational experiments reveal that the SA algorithm can generate near-optimal solutions quickly.

Keywords: single machine scheduling; deadlines; two agents; simulated annealing; release times; multi-agent systems; MAS; agent-based systems; tardy jobs.

DOI: 10.1504/IJSTL.2013.050590

International Journal of Shipping and Transport Logistics, 2013 Vol.5 No.1, pp.75 - 94

Received: 20 Apr 2012
Accepted: 30 Apr 2012
Published online: 28 Feb 2014 *