Research On Job-shop Scheduling With Deterioration Effect And Setup Time

The manufacturing industry is always the lifeblood of a country, a share of national economy greatly. In order to reduce product cost, improve product quality and productivity, effective scheduling strategy plays an important part in the development of companies such that they can survives in the fierce market competition Therefore, shop scheduling problem is studied by many researchers. Due to the complexity of modeling, computational complexity, many constraints and objectives, such scheduling problem is a typical NP-hard problem such that it is very difficult to solve it. Job-shop scheduling problem can be divided into single machine scheduling and multi-machine scheduling. In practice, many production processes in manufacturing companies with small batch production can be single machine and multi-machine system. In the real manufacturing system, the processing time of a job often takes more time compared with the actual processing time. Such phenomenon is called deteriorating effect in the literature. Based on the assumption that the deteriorating effect is a linear function of the time, this work addresses the group scheduling problem of single machine system subject to deteriorating effect and release time and the scheduling problem of a two machine flow-shop system with both time dependent deteriorating jobs and setup time.In this paper, the research background, significance, and the current studies are introduced in detail. Then, the goals of this work are proposed after that, this work presents the constraints which should be considered in dealing with the scheduling problem of the job shop system.For the problem of single machine group scheduling with time-dependent deteriorating jobs subject to release time, based on the characteristics of the scheduling problem and two given theorems, a polynomial algorithm is devebped to obtain an optimal schedule. At last, an example is given to show the application of the proposed approaches.For the problem of a two machine flow shop with both time dependent deteriorating jobs and setup time, based on the characteristics of the scheduling problem, a mixed integer programming model is developed. Then, this work proposes a heuristic variable neighborhood search algorithm to find a schedule for large si2e problem. The initial solution and neighborhood structure play an important part in that whether the variable neighborhood search algorithm can be applied to find a good solution for the scheduling problem. Thus, a greedy algorithm is developed to obtain an initial solution, and four neighborhood structure operations are proposed to change the neighborhood structures such that the obtained solution by variable neighborhood search algorithm is not the local one. Also, to evaluate the performance of the proposed algorithm, the calculation approaches of two lower bounds are given in this work. Finally, examples are given to show the efficiency and effectiveness of the proposed methods.