Journal of Applied Mathematics
Volume 2013 (2013), Article ID 135610, 10 pages
http://dx.doi.org/10.1155/2013/135610
Research Article

Single Machine Problem with Multi-Rate-Modifying Activities under a Time-Dependent Deterioration

M. Huang,1 Huaping Wu,1 Vincent Cho,2 W. H. Ip,3 Xingwei Wang,1 and C. K. Ng3

1College of Information Science and Engineering, Northeastern University, and State Key Laboratory of Synthetical Automation for Process Industries (Northeastern University) Shenyang, Wenhua Road, Heping District, No. 11, Lane 3, Shenyang, Liaoning 110819, China
2Department of Management and Marketing, The Hong Kong Polytechnic University, Hong Kong
3Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hong Kong

Received 13 February 2013; Revised 26 April 2013; Accepted 12 May 2013

Academic Editor: Ferenc Hartung

Copyright © 2013 M. Huang 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

The single machine scheduling problem with multi-rate-modifying activities under a time-dependent deterioration to minimize makespan is studied. After examining the characteristics of the problem, a number of properties and a lower bound are proposed. A branch and bound algorithm and a heuristic algorithm are used in the solution, and two special cases are also examined. The computational experiments show that, for the situation with a rate-modifying activity, the proposed branch and bound algorithm can solve situations with 50 jobs within a reasonable time, and the heuristic algorithm can obtain the near-optimal solution with an error percentage less than 0.053 in a very short time. In situations with multi-rate-modifying activities, the proposed branch and bound algorithm can solve the case with 15 jobs within a reasonable time, and the heuristic algorithm can obtain the near-optimal with an error percentage less than 0.070 in a very short time. The branch and bound algorithm and the heuristic algorithm are both shown to be efficient and effective.