Machine scheduling with a rate-modifying activity |
| |
| Institution: | 1. School of Mathematics, Shanghai University of Finance and Economics, Shanghai 200433, China;2. Department of Mathematics, East China University of Science and Technology, Shanghai 200237, China;3. College of Economics and Management, Shanghai University of Electric Power, Shanghai 200090, China;4. School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA;5. School of Mathematics and Statistics, Shandong University, Weihai, Shandong 264209, China;6. School of Mechanical, Electrical & Information Engineering, Shandong University, Weihai, Shandong 264209, China;1. Department of Administrative Management, Jinan University, Guangzhou 510632, People’s Republic of China;2. Department of Computer, Guangdong University of Finance, Guangzhou 510520, People’s Republic of China |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
