Parallel Machine Scheduling Problem With Two-Dimensional Delivery Time

This paper researches the machine scheduling problem with two-dimensional delivery time.The wide application of the new generation of information technology brings about the sharing of manufacturing resources and the unprecedented development of transportation industry has produced the huge influence to the modern manufacturing industry production operation management.In the classic scheduling model,it is generally assumed that the direct delivery time of each job is the unique value.However,considering the manufacturing resource sharing and delivery mode selection,the direct delivery time of a job often depends on the geographical location of the machine and the delivery mode.Therefore,it is necessary to consider the influence of the geographical location of the machine or the distribution mode for the distribution process.This problem has important theoretical and practical significance.First,this paper considers the scheduling problem with delivery mode dependent direct delivery times,the scheduling goal is to minimize the total service time under the distribution resource constraint.Based on problem analysis,we constructed a heuristic algorithm FD for distribution resource allocation,and this algorithm can obtain a excellent distribution resource allocation mode.Three heuristic algorithms FD-SPT,FD-ERT and FD-EST are constructed based on the scheduling rules.Many random data experiments were conducted to test the computational efficiency and applicability of the proposed algorithm.The results show that the proposed algorithm can provide high quality satisfactory solutions.Then,this paper considers the scheduling problem with machine dependent direct delivery times,the objective is to minimize the total service time.Since the job has machine dependent direct delivery times,the jobs should be arranged to the machines with relatively small direct delivery time when scheduling the jobs.We constructed two heuristic algorithms EST and MEST,the solution of MEST algorithm is improved by a sub-heuristic simulated annealing algorithm.Many random data experiments were conducted to test the computational efficiency and applicability of the proposed algorithm.The results show that the proposed algorithm can provide high quality satisfactory solutions.