Algorithms For Several Scheduling Problems

Scheduling problem is an important branch in combinatorial optimization and theoretical computer science, focusing on allocating the scarce resources to different jobs in certain time. The allocation process can also be understood as a decision-making process for optimize one or more objects. Most of scheduling problemes belong to NP-hard problem which is impossible to find the related optimal algorithms with polynomial time complexity. According to the real-time of the input information, scheduling problems can be divided into three categories:online, offline and semi-online. In view of the accuracy of the output, the scheduling problems can be divided into precise algorithms, approximation algorithms (including heuristic algorithms). Scheduling problem has been widely used in real life, such as energy-saving scheduling, load balancing, job scheduling, nurse scheduling, dynamic vehicle scheduling, flight scheduling, batch job scheduling, the flow shop and so on. Scheduling problems are widely used in real life and therefore the scheduling gets much attention and studied by lots of people.This paper focuses on parallel machine scheduling, flow shop scheduling and single machine scheduling for different scheduling models.(l)Online scheduling of parallel machines with buffers:This paper gives three online algorithms and proved the proposed aogorithms improving the previous research results:1) Form> 51 identical machines, giving a 1.5-competitive online algorithm with a buffer of size[1.5m].2) For three identical machines, giving an optimal online algorithm with a buffer size six, better than the previous nine;3) For m uniform machines, using a buffer of sizem, improve the competitive ratio from 2+ε to 2-1/m+ε, where ε> 0 is sufficiently small and m is a constant of the machines’number.(2)Online deadline scheduling has recently received lots attentionin recent years, especially in production and manufacturing, real-time systems, network flow. We studied the online deadline scheduling under the preemption penalty model with single machine. We proposed atraditional heuristic algorithms based on WAL algorithms called D-WAL algorithm and found that D-WAL algorithm works really good when the number of jobs is big by analyzing the experiments results.(3)Flow shop scheduling:We studied a flowshop scheduling problem considering the transportion time F2→D|v=1,c≥1|Cmax, which the jobs are first processed on two flow machines then carried to the destination by the transporter. The target is to minimize the completion time when all the jobs are carried to the destination. There is only one transporter and carrying at most c jobs in each delivery batch. In this paper, we study the special case where each job has identical processing time on machine B, and give an optimal algorithm.(4)Offline parallel machine scheduling:In this paper, we use the particle swarm optimization (PSO) algorithm and proposed LPSO algorithmy joining the Levy Flight optimizing the PSO algorithm. After analyzing the results of experients, we find that the Levy Flight method significantly reduces the disadvantage of PSO algorithm running into prematurity easily and makes full use of the PSO algorithm’s advantages of simplicity and efficiency.