| In the tradition of classical scheduling problems,and generally assumes the machine number will not change.With the full use of the Internet and other information technology,enterprises access to additional resources more convenient,thus this project breaks its traditional classical scheduling problems on the machine a fixed number of assumptions,research specific characteristics of machine manufacture model number changes on scheduling theory of impact and innovation.The main aspect of this study is the machines influence that additional may have on the objective function makespan under the identical machine scheduling problem,when the number of machine is increased from m to ?m.We measure this influence by a machine impact,which is defined as a ratio of the objective function value computed without using extra machines over the function value computed with additional machines.In this paper,we discuss two kinds of preemptive and nonpreemptive situations in which the identical machine scheduling problem with job release times.(1)For online machine scheduling problem with job release times and preemptive.Firstly,we present a polynomial-time algorithm P,which is based on modified the McNaughton's rule.We prove that the algorithm can find optimal solutions and optimal machines number,and analysis the machines influence.Finally,computational results show that the presented algorithm is efficient and effective.(2)For online machine scheduling problem with job release times and nonpreemptive.It is difficult to get optimal solutions in polynomial time because of this problem is NP-hard,therefore,we propose a heuristic algorithm MLPT.Finally,the performance of the algorithm is analyzed by experiments,and describes the algorithm adapt to the situation.Experimental results showed that increasing the number of machines is an effective method to improve production efficiency,but we should use existing machine resources reasonably,so as to avoid wastage of resources. |
PDF Full Text Request