Uniform Parallel Machine Scheduling Problem With Machine Use Cost

This paper considers uniform parallel machine scheduling problems with machine use cost under the background of cloud manufacturing.Manufacturing industry as a pillar industry of our country,since reform and opening up,developed rapidly,but still has a great gap with developed country.Cloud manufacturing is a new kind of manufacturing mode produced by the combination of emerging information technology and manufacturing.The online transactions of the using right of online entities manufacturing resources via the cloud manufacturing platform online and offline production,can achieve effectively integrating of scattered manufacturing resources from different addresses,then can highly share resources and services,to reduce the waste of manufacturing resources,so it has the vital significance to manufacturing industry in our country.The essence of cloud manufacturing is to share manufacturing resource via the Internet,so,it must consider the using cost of machines in production scheduling under the background of cloud manufacturing.The paper assumes the using cost of machines is fixed in the production cycle,and study a uniform parallel machine scheduling problem considering the using cost of machines.The goal is to minimize the makespan with a given budget of total cost,and to achieve the balance of production cost and production efficiency.All the jobs are homogeneous,i.e.,the processing time of the jobs are identical.Non-preemptive and preemptive problems are studied.We show that this problem is NP-hard through analyzing it.For the non-preemptive problem,we give a 2[1+1/(h-1)]-approximation algorithm,where h is the number of the machine which can not be selected the first time.For the preemptive problem,we give an algorithm whose worst-case bound equals to 1+1/(h-1).Finally,preliminary experimental results indicate that the proposed algorithms are reasonably accurate compared with the lower bounds.Then,we study a uniform parallel machine scheduling problem considering the using cost of machines and normal jobs(the processing times of the jobs are different).The goal is also to minimize the makespan with a given budget of total cost.Non-preemptive and preemptive problems are studied.For the non-preemptive problem,it gives and proves a 2[1+1/(h-1)]-approximation heuristic algorithm based on the improvement of the classical LPT algorithm,where h is the number of the machine which can not be selected the first time.Finally,the experimental results show the effectiveness of the algorithm.For the preemptive problem,we give an algorithm on the base of Level algorithm to solve it.