Uniform Parallel Machine Scheduling Problems With Unit Machine Cost

This paper considers uniform parallel machine scheduling problems with consideration of per unit time machine costs under cloud manufacturing.The new information technology is widespread used into the manufacturing,and it becomes one of the typical characteristics of modern advanced manufacturing.A new manufacturing model is emerging,in which the using rights of production machines can be bought via Internet.It is usually called as cloud manufacturing.Cloud manufacturing can integrate the discrete idle manufacturing resources,form a larger production capability,and increase the efficiency of the production machines,so it is significant to the manufacturers and the government.Different with the assumption that the machines belong to the manufacturers in classical scheduling theory,the machines in cloud manufacturing are rented.It must consider machine cost during the production process.In this paper,we study a uniform parallel machine scheduling problem with consideration of the machine costs.They have different processing speeds,and construct a uniform parallel machine production system.Before the process of manufacturing,the unit cost of any machine is given.Our goal is to minimize the makespan with a given limitation of total cost.First introduced the concept of cost-effective,the definition of machine cost and speed ratio is defined as cost-effective.In this paper,we also suppose that the cost-effective is non-decreasing with the development of technology.All task are common task,that is,the processing time is different.We consider two cases,the preemptive problem and the non-preemptive problem.For the preemptive problem,we give an optimal algorithm 3.1.For the non-preemptive problem,we give a heuristic algorithm for the NP-hard problem.It is showed that the heuristic solution of non-preemptive problem is very accurate by experimentation.Then,we relaxed the constraints,remove the cost-effective of the constraints,make it closer to reality.An integer programming model for this kind of problem is constructed.The four heuristic algorithms are constructed under the rule of LPT.And calculate their time complexity.The experimental results indicate that these algorithms are very well in practice.