A Model to Solve Multi-Cycles Machine Time Scheduling Problems

Abstract

In today's complex manufacturing setting, with multiple lines of products, each requiring many different steps and machines for completion, the decision maker for the manufacturing plant must find a way to successfully manage resources in order to produce products in the most efficient possible way. The decision-maker needs to design a production plan with different machine environments and different characteristics of the jobs to be performed, and at the same time, he needs to minimize some objectives such as the flow time of a product, the makespan, and/or the total completion time of all jobs. One of the question that the solution of scheduling problem is when will each job performed?. That mean the scheduling problem deal with the time around the jobs (like starting time, setup time, due date,..., etc). One of the most important scheduling problems interest with the time is called Machine Time Scheduling Problem (MTSP). It was considered also an important applications in the area of optimization. The general form of MTSP, there are m machines and k cycles(jobs); each cycle has n operations assigned (with certain processing times) to the given m machines. For each machine, there is a set of preceding machines, and has a prescribed time window for starting time. The main objective in MTSP is to minimize the penalty function of earliest and/or latest starting time of the operation. In general MTSP is NP-hard, Non-convex, Non-differentiable problem. So, for special version of it, the MTSP could be formulated as max separable equation, and will be solved by using the Max-separable technique. The MTSP has been solved in two• cycles only [9], but in practice, there may be many cycles on the machines. So, this thesis aimed to find a optimal starting time for each machine in multi-cycle to minimize a constructed penalty function. The main goal of this thesis is to solve multi-cycle machine time scheduling problems. To achieve this goal the thesis discusses four objectives, as follows: I. Study machine scheduling problems and MTSP. 2. Developing an algorithm to solve MTSP in multi-cycles. 3.. Developing an algorithm to solve approximately MTSP with emptiness feasible set. 4. Developing an algorithm to solve MTSP with stochastic processing time.