Two - Stage Supply Chain Scheduling Problem With Deterioration Effect

The theory of scheduling is one of the important branches in operations research. Supply chain scheduling is a new field that combines scheduling and batch delivery. We research the coordinated scheduling problem of production and transportation in which each semi-finished job is transported from the storage to a manufacturing facility for further processing. Our problem consists of a transportation stage from the storage to the manufacturing factory and a production stage on the batching machine. We thus call this problem TBS problem.Deterioration effect has been discovered in many production situations such as the steel production. Thus the model with deteriorating effect has very significant practical significance.Based on the above scheduling problem as the background, we discuss several related scheduling problems. The structure of this article is as follows:In the first chapter, we introduce some notions that we will use in this article and the main work of this paper.In the second chapter, we study the TBS problem with deterioration considerations. The processing time of a job will increase if the duration from the time leaving the storage to the start of its processing exceeds a given threshold. The time needed to process a batch is the longest of the job processing times in the batch. The batching processing cost is constant. We consider the problem that there is a vehicle in the transportation stage and unbounded batching machines in the production stage. We study the two objectives as follows:(1) The objective is to minimize the sum of total completion time and the total processing cost.(2) The objective is to minimize the sum of maximum lateness and the total production cost. We prove that the two problems are both strongly NP-hard and further develop polynomial time algorithms for their special cases.In the third chapter, we discuss the batching processing cost which is not constant. It depends on the batching processing time, without loss of generality, the longer processing time,the more cost on the processing. We also consider the inventory holding cost, each job has the same unit inventory cost, the inventory time is the duration from the time at t ?0 to the start of its processing time. We research the two problems as follows:(1) There is a vehicle in the transportation stage and unbounded batching machines in the production stage, we minimize the sum of total inventory holding cost and the total production cost.(2) There are m vehicles in the transportation stage and unbounded batching machines in the production stage, we minimize the sum of total inventory holding cost and the total production cost. We prove thatthe two problems are both strongly NP-hard and further develop polynomial time algorithms for its special cases.