Machine scheduling with a rate-modifying activity Academic Article

abstract

• Motivated by a problem commonly found in electronic assembly lines, this paper deals with the problem of scheduling jobs and a rate-modifying activity on a single machine. A rate-modifying activity is an activity that changes the production rate of the equipment under consideration. Hence the processing times of jobs vary depending on whether the job is scheduled before or after the rate-modifying activity. The decisions under consideration are when to schedule the rate-modifying activity and the sequence of jobs to optimize some performance measure. In this paper, we develop polynomial algorithms for solving problems of minimizing makespan, and total completion time respectively. We also develop pseudo-polynomial algorithms for solving problems of total weighted completion time under the agreeable ratio assumption. We prove that the problem of minimizing maximum lateness is NP-hard and also provide a pseudo-polynomial time algorithm to solve it optimally.

authors

• Leon, Victor

published proceedings

• EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

author list (cited authors)

• Lee, C. Y., & Leon, V. J.

citation count

• 145

complete list of authors

• Lee, CY||Leon, VJ

publication date

• January 2001

publisher

• Elsevier  Publisher

keywords

• Job Scheduling
• Machine Scheduling
• Performance Measure
• Polynomial Algorithms
• Rate-modifying Activity

Digital Object Identifier (DOI)

• 10.1016/S0377-2217(99)00066-1

start page

• 119

end page

• 128

volume

• 128

issue

• 1

URL

• http://dx.doi.org/10.1016/s0377-2217(99)00066-1