Research On Two-agent And Parallel-batching Scheduling Problems With Deteriorating Jobs

The scheduling problem based on the production planning refers to the decision-making problem to optimize the allocation of manufacturing resources for a batch of manufacturing tasks in time domain,according to the market and enterprise.It is essentially a kind of classical combinatorial optimization problem,involving in aviation,transportation and other fields.It has strong application prospect and theoretical value.With the development of technology rapidly,it can acquire production tasks in time,adjust production planning and detect equipment status in the production processes,which is of great significance to optimize schedules.In this context,manufacturing enterprises seek novel production and manufacturing mode.Hence,outsourcing production gradually emerge.An increasing number of enterprises start to adopt this mode to satisfy the diversified requirements from every customer order.Manufacturing enterprises to developing effective scheduling schemes and optimize allocation of manufacturing resources,will be in an invincible position in furious marketing competitions.This paper is motivated by the processes of aluminum-making in an aluminum plant,and focus collaborative scheduling optimization on two agents between outsourcer and manufacturer.Meanwhile we assume that the processing time of a semi-finished aluminum product will be increasing when this product is processed on a batch machine in a later position.The objective is to minimized the makespan of outsourcer(agent A) with the constraint that the makespan of manufacturer(agent B) is no more than a given threshold.There are two situations including single machine and parallel machines.The paper's main tasks are as follows.(1)A two-agent scheduling problem on a single batch machine is considered.The processing time of a job is depend on its position.the processing time of a batch is the largest processing time of the jobs in this batch.The objective is to minimized the makespan of agent A with the constraint that the makespan of manufacturer agent B is no more than a given threshold.According to this objective,some key structural properties are first identified in two different cases by mathematical induction,substitution and classification discussion.Based on these structural properties,a novel decision tree of scheduling rules is constructed and a heuristic algorithm is designed for solving the problem.(2)A two-agent scheduling problem on parallel batch machines is considered.The objective is to minimized the makespan of agent A with the constraint that the makespan of agent B is no more than a given threshold.Then a mixed integer programming model is formulated.According to the features of our studied problem,the initial solution is generated randomly,and then four neighborhood structures are constructed to improve the quality of the solution.Finally,an improved bacterial foraging algorithm is developed to solve the batch scheduling problem on parallel machines.Computational experiments results indicate that the hybrid BF-VNS algorithm performs quite better than other algorithms in reference to the quality of solution,convergence speed and stability.