Single machine problem with multi-rate-modifying activities under a time-dependent deterioration

M. Huang, Huaping Wu, Wing Sing Cho, W. H. Ip, Xingwei Wang, C. K. Ng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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. Huang et al.
Original languageEnglish
Article number135610
JournalJournal of Applied Mathematics
Volume2013
DOIs
Publication statusPublished - 28 Jun 2013

ASJC Scopus subject areas

  • Applied Mathematics

Cite this