برنامه ریزی برای اتمام به موقع در تولید کارگاهی با استفاده از تابع امکان سنجی

This article focuses on job shop type manufacturing systems where a high variety of products of different volumes are requested to be produce on a tight due date. The feasibility function (FF) is addressed in this article to schedule jobs in multi-machine random job shop, where the purpose is to minimize unit penalty by achieving a balance between the number of tardy and early jobs, and reducing the difference between the maximum and the minimum lateness of jobs. A job shop simulation model based on multi-agent architecture developed by the authors provides an environment for comparing the FF to commonly used dispatching rules. The results show the benefit of using the FF. Discussions reveal that this concept is more reliable in case of due dates with different tightness level.

Reliable delivery dates have been of capital importance in make-to-order manufacturing environment since the beginning of production. Before the industrial revolution a craftsman, a member of a guild created a unique product by himself fully satisfying the costumer's requests, planning and scheduling were based on intuitions. Quality and reliable delivery dates represented the trademark of the craftsman. Present manufacturing companies with make-to-order environment yearn for flexibility, quality and ability of customizing these according to the customer's requirements. The modern market of high standard requires high variety of qualitative products, on-time delivery, minimal work in process, short costumer lead times, and maximum utilization of resources. Unfortunately, these goals are conflicting. The goal of the modern production scheduling is to strike a profitable balance among these conflicting objectives (Hopp, Wallace, Spearman, & Mark 1996). The more complex the product and the manufacturing system are the more complex planning and control techniques are needed, intuitions are not effective enough anymore. One of the basic objectives of production scheduling in make-to-order environment is to meet the due dates. Due-date based scheduling of manufacturing systems has been widely examined in the related literature. There are several empirical and mathematical models to schedule jobs in shop floor to obtain better due date performance. Dynamic priority rules are the most used scheduling algorithms in case of due date related real-time scheduling. Scheduling problems can be defined by three separate elements: the machine environment, the optimal criterion, and a set of side constraints and characteristics. In single machine environment earliest due date (EDD) is an exact algorithm for minimizing the maximum lateness (Jackson, 1955). Dertouzos (1974) proved that in a context of queuing system, the EDD algorithm is optimal in a following sense: if any algorithm can schedule a particular task set without missing any deadline, the EDD algorithm can schedule it as well. Mok (1983) proved that the last slack time (LST) algorithm could also complete the above. If we have more than one machine, scheduling problems become more complicated. This article is focused on due-date based dynamic scheduling in job shop type manufacturing systems. Job shops produce small lots with high variety of routings through the plant with different machines. Each job has its own route to follow and unique requirements. Recent research results in the field of job shop scheduling for due date performances point out that the combination of the shortest process time first (SPT) and the critical ratio with allowance (ALL+CR+SPT) scheduling algorithms gives the best performances (Cheng & Jiang, 1997). Due to the complexity of job shop type manufacturing systems benchmark problems are still under development. The first expedient benchmark concept for minimizing maximum lateness was introduced by Demirkol, Mehta, and Uzsoy (1996). Later discussion will point out that in case of dynamic scheduling a realistic simulation model with long-term simulation runs may represent a job shop behavior more genuinely than benchmark problems. The commonly used due date performance measures are unit penalty, mean tardiness, maximum and minimum lateness. It is known that tardy jobs may incur tardiness costs, such as contractual penalties, depending on how late they are. According to the new production technologies, early jobs may incur earliness costs as well, such as inventory holding costs (Yeunga, Oguz, & Cheng, 2001). Thus, minimizing average earliness of jobs has become more important in production scheduling research Baker and Scudder, 1989 and Lee et al., 1991. For this performance the minimizing mean absolute and square lateness measurements are used. The purpose of the presented research work is to develop a scheduling algorithm that minimizes unit penalty by balancing between the number of tardy and early jobs and reducing the difference between the maximum and the minimum lateness of jobs by its nature. This article first introduces a new due date related performance measurement, and then brings out a new scheduling algorithm, called feasibility function (FF). The environment of comparing the FF with the other real-time scheduling algorithms is a job shop simulation model based on multi-agent architecture. Several simulation runs are analyzed, with up to 5500 jobs and 15 machines. To represent the behavior of scheduling algorithms a simulation run with tight due dates is introduced in detail. The evaluation of the simulation results shows the benefit of using the FF concept if on-time completion is of importance. Discussions reveal that this concept is more reliable in case of tight due dates.

The presented research work verifies the establishment of the former research results in the field of job shop due-date scheduling. The algorithms that combine minimizing mean flow time and on time completion criteria work better in job shop scheduling problems. Single due-date based algorithms are not effective enough, because they do not consider the aspect of rational job sequencing in job shops, they use only slack time related sequencing. However, in case of loose due dates they perform as good as the combined algorithms. Due to the longer mean flow time they may approach the due dates in the due window more intensively. The FF-based algorithm introduced in the presented research work operates the most effective in job shop scheduling if ontime completion is of importance. The unit penalty and the mean square lateness decreased with higher effectiveness compared to the other existing algorithms in case the tightness of due-dates are high or different for each job. The future work will focus on dynamic due-date setting method to be able to set the due date tightness according to the fluctuation of the shop floor utilization. During the simulation runs the average FF of jobs was monitored. When the on time completion was in a reassuring way then the average value was determined directly. When the utilization of the machines was increasing then the average value started to oscillating and when it turned to a chaotic situation then the value was very high. The aim of the future research work is to develop a management agent with reinforcement learning method that sets tightness of due dates dynamically adopting the fluctuation of the demand and the shop utilization.