Mathematical Problems in Engineering
Volume 2012 (2012), Article ID 939717, 7 pages
http://dx.doi.org/10.1155/2012/939717
Research Article

Online Parallel Machine Scheduling to Maximize the Number of Early Jobs

Feifeng Zheng,1,2 Ming Liu,3,4 Chengbin Chu,3,4 and Yinfeng Xu2

1Glorious Sun School of Business and Management, Donghua University, Shanghai 200092, China
2School of Management, Xi'an Jiaotong University, Xi'an, Shaanxi Province 710049, China
3School of Economics & Management, Tongji University, Shanghai 200092, China
4Laboratoire Génie Industriel, Ecole Centrale Paris, Grande Voie des Vignes, 92295 Châtenay-Malabry Cedex, France

Received 4 August 2011; Accepted 17 November 2011

Academic Editor: Furong Gao

Copyright © 2012 Feifeng Zheng et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

We study a maximization problem: online scheduling on m identical machines to maximize the number of early jobs. The problem is online in the sense that all jobs arrive over time. Each job's characteristics, such as processing time and due date, become known at its arrival time. We consider the preemption-restart model, in which preemption is allowed, while once a job is restarted, it loses all the progress that has been made on this job so far. If in some schedule a job is completed before or at its due date, then it is called early (or on time). The objective is to maximize the number of early jobs. For m identical machines, we prove an upper bound 1-(1/2m) of competitive ratio and show that ECT (earliest completion time) algorithm is 1/2-competitive.