Parallel Machine Scheduling Problems With Cost Under Cloud Manufacturing

This Paper considers parallel machine scheduling problems with cost under cloud manufacturing. With the development of science and technology, the Internet of things, cloud computing and big data have significant effect on the traditional manufacturing industry. Recently, cloud manufacturing has been proposed as a promising manufacturing model. Cloud manufacturing requires a huge virtual platform and multiple factories which located at different places. Factories can update their status in real time through the cloud manufacturing platform. If customers want to process a set of jobs, they will check on different factories' status. Manufacturing resources can be used effectively through cloud platform.In this paper, we first research production scheduling problem with cost under cloud manufacturing. Our goal is to find a schedule that minimizes the makespan or the total completion time, subject to the constraint that the total cost is not more than a given threshold cost. We give a linear time algorithm to find a minimum length schedule when the preemption is allowed. Then we propose two non-preeemptive heuristics for the two problems - makespan and the total completion time. We also provide some related properties and theorems to prove that our algorithms can get the satisfied solution for these two problems. At last, a large number of random computational experiments are performed to test the average-case performance, and our results indicate that the performance of the algorithms is quite satisfactory.Then, we extend our research field to integration production and delivery scheduling problem. In this problem, we have to consider delivery cost. Our goal is to find a schedule that minimizes the makespan and total completion time, subject to the constraint that the total cost is not more than a given threshold cost. We first describe a linear programming algorithm to slove the preemptive case of the makespan problem. The result of the linear program serves as a low bound of the nonpreemtive case and suggests algorithms to solve the nonpreemptive case. We also show that minimizing the makespan and minimizing the total completion time subject to a given threshold of the cost is NP-complete. At last, Computional experiments are conducted and results show that the algorithms perform very well in practice.