Fixed Job Online Scheduling Problems With Multiprocessor Task Study

This paper combines together two emerging areas of scheduling research, multiprocessor task problems and fixed interval problems, and takes online scheduling into account, which is more consistent with real life situations. It introduces the concept of online scheduling and competitive ratio analysis in the beginning, followed by several examples of practical backgrounds, such as production planning and control, computation processing, warehouse management, hotel management and ticket booking. Apparently this problem is NP-hard, so we employ competitive ratio analysis method to evaluate the performance of our heuristics, which is well accepted by the scholars.According to the combination of three variable factors of this problem (allow preemption or not, designate the concurrent machine set or not, value all jobs the same or not), this paper studies the corresponding eight sub-problems, mainly focusing on finding the lower bound and proposing the heuristics.As to preemptive sub-problems whose job weights are the same or equal to the product of processing time and number of concurrent machines, this paper provides the optimal algorithms (HEU1, HEU2, HEU3, HEU4) whose competitive ratios are the same as lower bound. As to preemptive sub-problems whose job weights are arbitrarily designated, we prove that there exists no deterministic algorithm with definite competitive ratio.However, as to non-preemptive sub-problems, we point out that FCFS (First Come Fist Serve) is the best possible deterministic algorithms. Furthermore, we consider a kind of problem in which both start and end processing times are integers and the number of simultaneous processors is bounded. Upper bound for any FCFS algorithms and lower bound for First-Fit algorithm are given.The research of this paper is of certain value for the practical production. The results can also assist the decision makers in solving scheduling problems in real life.