Parallel machine scheduling with a convex resource consumption function |
| |
| Affiliation: | 1. Faculty of Science, Kunming University of Science and Technology, Kunming 650093, China;2. Graduate Institute of Business Administration, Cheng Shiu University, Kaohsiung County, Taiwan;3. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong;4. School of Management Science and Engineering, Dalian University of Technology, Dalian 116023, China;5. Department of Statistics, Feng Chia University, Taichung, Taiwan;1. School of Business, Shanghai Dianji University, Shanghai 201306, China;2. Department of Industrial and Systems Engineering, The University of Tennessee at Knoxville, Knoxville, TN 37996, USA |
| |
| Abstract: | We consider some problems of scheduling jobs on identical parallel machines where job-processing times are controllable through the allocation of a nonrenewable common limited resource. The objective is to assign the jobs to the machines, to sequence the jobs on each machine and to allocate the resource so that the makespan or the sum of completion times is minimized. The optimization is done for both preemptive and nonpreemptive jobs. For the makespan problem with nonpreemptive jobs we apply the equivalent load method in order to allocate the resources, and thereby reduce the problem to a combinatorial one. The reduced problem is shown to be NP-hard. If preemptive jobs are allowed, the makespan problem is shown to be solvable in O(n2) time. Some special cases of this problem with precedence constraints are presented and the problem of minimizing the sum of completion times is shown to be solvable in O(n log n) time. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
