Can Be Split Parallel Machine Scheduling Problem,

Parallel machine scheduling (PMS) is widely used in the modern manufacturing industry and service industry.Especially, the problem is extended to PMS with splitting jobs to solve problems in mass production of standard products. With three paramatersmethod, the problem is noted as P_m|setup & split|C_max.with the setup time not equal 0,the problem is NP-hard.The paper focuses on the improvement and analysis of heuristics and we employ competitive ratio method to evaluate the performace of our heuristics, which is well accepted by the scholars.The research has several following contributions:As to PMS with splitting jobs and independent setup time,1. The paper provides a better mechanism to solve the small batch problem by improving the second period of the original method. With the same scheduling rules of the first period, we improve the worst case of existing methods.Concretely, we improveLSU's compertive ratio from max{3/2-1/(4M-4),5/3-1/M| to NLSU'smax(?),LBT's max(?) to NLBT's (?).2. For Small Batch problems when M=2, we bring out the LKT method, schedulingaccording to ks_j+p_j(k≥1) in the first period, the competitive ratio of which is relatedto k(k≥1).While k equals 3, we derive a competitive ratio of (?) , which is better thanthat of any existing method when M=2.3. For Large Batch problems when M=2, the paper proposes that any no-dely schededuling and splitting method can reach the optimal solution to Large Batch problem.4. The paper brings out more methods and results for Large Batch Problem in generalcase. Besides, we develop the worst case to max{3/2-1/(4M-4),5/3-1/M},andmake it the same for both Small Batch and Large Batch problems.As to PMS with splitting jobs and independent setup time,5. The paper derives several heuristics and give general worst-case analysis anddraws the conclusion that for the problem with s_ij≤αp_j , DLSS method has a competitive ratio less than (1+α)(2-(?)) and DLTT method has a competitive ratioless than (1+α)(2-(?)).For a special case when s_0j=0 , D method has acompetitive ratio less than(1+α).