Single facility scheduling with nonlinear processing times Article

Gupta, JND, Gupta, SK. (1988). Single facility scheduling with nonlinear processing times . COMPUTERS & INDUSTRIAL ENGINEERING, 14(4), 387-393. 10.1016/0360-8352(88)90041-1

cited authors

  • Gupta, JND; Gupta, SK

authors

abstract

  • This paper considers the static single facility scheduling problem where the processing times of jobs are a monotonically increasing function of their starting (waiting) times and the objective is to minimize the total elapsed time (called the makespan) in which all jobs complete their processing. Based on the combinatorial analysis of the problem, an exact optimization algorithm is developed for the general processing time function which is then specialized for the linear case. In view of the excessive computational burden of the exact optimization algorithm for the nonlinear processing time functions, heuristic algorithms are proposed. The effectiveness of these proposed alogrithms is empirically evaluated and found to indicate that these heuristic algorithms yield optimal or near optimal schedules in many cases. © 1988.

publication date

  • January 1, 1988

published in

Digital Object Identifier (DOI)

start page

  • 387

end page

  • 393

volume

  • 14

issue

  • 4