Research On Models And Algorithms Of Some Single Machine Batch Scheduling Problems Under Fuzzy Environment

Scheduling problem is an important branch of opeartions research, and its research problem involves many areas, such as production of industry and agriculture, transportation, urban planning,management science, semiconductor manufacturing, communication and network technology, computer science and information technology. Scheduling concerns the allocation of limited resources to tasks over time. It is a decision-making process that has as a goal the optimization of one or more objectives. Batch scheduling is to group the jobs on each machine into batches and to schedule these batches with the aim of minimizing objective. The objective functions to weigh the schedule is good or bad. Batch scheduling theory has a major role in guiding to improve production efficiency, production technology and the service quality. Based on the previous research, this dissertation studies some single machine batch scheduling problems under fuzzy environment, including batch size problem, precedence constraint problem, due-date problem, processing time problem. These problems have wide applications in actual, such as production organization, market management, transportation arrangement and the processing of information etc. The main work of this dissertation can be summarized as follows:1. We make some extensions on some models of batch size problem and propose two kinds of batch size problem. The first is bi-criteria single machine batch scheduling problem with fixed limit of batch size, and the bi-criteria considered are minimization of the maximal completion time and the flowtime. The second is three-criteria single machine batch scheduling problem with flexible bound of batch size. Here the fuzzy batch size describes the satisfaction level about common upper bound. The three-criteria considered are maximization of minimal satisfaction degree about common upper bound, minimization of the maximal completion time and the flowtime. For these two problems, we propose the pseudo algorithm to seek solutions. Finally, numerical example is presented to illustrate runs of the algorithm.2. Four kinds of mathematical models with precedence constraint and due-date are proposed, i.e., single machine sequence batch scheduling problem with ordinary precedence constraint and crisp due-date, single machine sequence batch scheduling problem with fuzzy precedence constraint and crisp due-date, single machine parallel batch scheduling problem with ordinary precedence constraint and fuzzy due-date, and single machine parallel batch scheduling problem with fuzzy precedence constraint and fuzzy due-date. Here, the fuzzy precedence constraint expresses the satisfaction level with respect to precedence between two jobs, and the fuzzy due-date denotes the degree of satisfaction with respect to completion times of jobs. The objective is to maximize the minimum satisfaction level of fuzzy due-date and the fuzzy precedence constraint. For these four problems, we propose corresponding algorithms to seek solutions respectively, including the non-dominated solutions.We also show the time complexity of the algorithms. Finally, numerical example is presented to illustrate runs of the algorithm.3. We propose a model dealing with uncertain processing times, that is, s ingle machine batch scheduling problem with fuzzy processing time and crisp due-date. Here, a special form of triangle fuzzy numbers is originally used to describe fuzzy processing times. A new concept of batch lateness l-N tardiness is defined at the first time. Necessity measure is perfectly introduced to compare fuzzy numbers.An efficient algorithm is designed on the basis of the procesure of Moore’s model to find an optimal batch sequence consisting of a batch number and allocation of jobs to batches to minimize the total number of tardy jobs under a common limited batch size. We also show the time complexity of the algorithm. Finally, numerical example is presented to illustrate runs of the algorithm. And taking Matlab as the platform, develop fuzzy processing time batch scheduling optimization program. The program verifies the correctness of time complexity degree for algorithm, but also the ability of the program to deal with complex problems of big data.