José Marinho, Alexandre Bragança, Carlos Ramos

Keywords: Production Dynamic Scheduling, Decision-Making Support, Operational Management, Heuristics.

One of the most important aspects for competitiveness and success of an organization is the efficient production managing. Deliver the goods on time, with quality and at low-cost, provides a good customer service, these are fundamental factors to achieve and maintain a good marketing acceptance.

However, there are several problems to solve and decisions to make. Surely, the manager must know when to make a decision. However, to do that he must have information (knowledge) that allows analyzing and taking a correct decision. Moreover, we cannot forget the important information (knowledge) from experience acquired along with time. Therefore, it is clear that we need systems that are able to help in decision-making at many levels, namely at the production level.

Some computer systems that support decision-making in production planning and control are based on artificial intelligence [1]. Others are based on constraints [2][3].

Others are based on heuristics [4], for example, for dynamic production scheduling [5]. Others too are hybrid systems [6][7], for example, by way of an expert system based on rules which derive a set of good solutions (nears ideal) that will be processed afterwards by another kind of system, which chooses the best solution [8]. Others systems are based on simulation models.

All those systems are tools to help the manager to analyze the available information. Because commonly there are a lot of interrelated factors that influences and complicates the decisions, and these by your turn interfere ones with others. Therefore search for optimal solutions is, in most situations, unpractical.

Particularly production scheduling is a complex function because the goals are contentious: great productivity, low stock levels, good customer satisfaction via products with quality, resources optimization, etc.

It is obvious the need for a dynamic production planning and control system to help elaborating good schedules (planning) in useful time and also to ensure that those schedules are executed and corrected if necessary (control) depending on events.

Some questions that those systems must answer are:

• What due date promise?
• When starts the task?
• What the status of manufacturing orders?

The Decision Support System for Dynamic Production Scheduling proposed [9] is based on a methodology that finds time intervals for dynamically schedule the manufacturing orders considering deadlines and resources occupation [10].

Depending on the manager's scheduling policy, the system selects the appropriated solution by means of heuristics. If there is no solution obtained the system can suggest possible actions based on further heuristics, to solve the problem in order to obtain a possible solution. These heuristics can be more or less complexes: rules of priority, meta-heuristics [11][12], genetic algorithms [13], methods based on the fuzzy theory [14], etc.

This system involves three stages (Fig. 1):

• Pre-Scheduling
• Dynamic Scheduling
• Re-Scheduling

In the first stage the manufacturing orders are ordered concerning some parameters that are associated with them, for example, the due date. The second phase schedules each one of the orders dispatched in the previous phase, looking and trying to fill the free time intervals of resources, respecting the delivery dates. In the third phase, some orders are reformulated and/or reordered to reschedule afterwards, regarding the data collected through shop-floor control. We need this because the things not always run as planed (defective quality, breakdown of equipment, others situations and lags).

In each of these stages certain kinds of heuristics or a combination of these can be applied. This combination [15] allows achieve better commitment in solutions, considering the manager's scheduling policy.

The manager specifies, at any moment, the scheduling policies to apply to the several situations. Therefore, he has total control on the scheduling activity through support of a flexible system adapted to the practical reality. Besides Bedworth said [16] "in fact the use of the common sense is the best scheduling method when the scenery is complex". Thus, the manager is who decides and controls the operations according to its knowledge and intuition.

This system enhances production systems like batch or job-shop. In those kinds of systems we have variable amounts of different types of products that share the same resources with different processing paths and times. This makes the scheduling complex, worsened by a need of satisfaction of customers' orders. Therefore, the delivery dates are vital for the system and the lags a critical factor.

Depending on the policy of scheduling adopted by the manager, the system selects the most appropriate solution by way of heuristics. In case that no solution is obtained, the system can suggest alternative actions in order to solve the problem.

In the first and last phases simple heuristics are applied (priority rules) to order the manufacturing orders concerning some static or dynamic parameters associated to those heuristics.

Examples of these heuristics:

• FCFS (First Come First Served)
• EDD (Earliest Due Date)
• SPT (Shortest Processing Time)
• MINSLACK (Minimum Slack Time)
• CR (Critical Ratio)
• PCO (Preferred Customer Order)

To understand the dynamic scheduling phase let us explain our concept of behavior. A behavior is a well temporized sequence of sets of operations to produce a good. The figure (Fig. 2) illustrates the behavior for manufacturing the product X. For this product three sets of operations are necessary: S_op1, S_op2 and S_op3. The set S_op1 needs 1 tu (time unit) in line A, set S_op2 needs 3 tu in line B and set S_op3 needs 2 tu in line C.

However for producing N products we will not spend N*6 tu. The figure (Fig. 3) illustrates that we have overlapped between the manufacturing of products. In this figure we see the manufacturing of 5 products X by appending the basic behavior. In fact, after the first product we will be able to deliver a new product every 3 tu.

Let us consider D tpi as the processing time for the set of operations i and D twi as the waiting time for the next similar processing.

Considering those values we can calculate the occupation time for each production line (D toci), assuming N products to be manufactured and using the formula (1).

Another important value to consider is the time interval from the beginning (or end) of a set of operations until the beginning (or end) of another set of operations (the first set precedes the second), D tin and D tfin.

One can use the concept of behaviors to deal with more realistic situations of Manufacturing Systems [17] (e.g. setup times, transport times, queues, parallel execution of the operations of the same task dealing with cases more complex than simple job shop, configuration of the system).

The dynamic scheduling phase applies other kind of heuristics to give an answer to eventual indecision situations resulting from the base-algorithm.

Examples of these heuristics:

• Earliest finish: to choose the solution that allows earlier finish of the manufacturing order (Fig. 4)
• Latest finish: to choose the solution that allows the closest due date finish of the manufacturing order
  (Fig. 4)
• Minimum/Maximum Slack Fitting: to choose the solution that has the smallest/largest slack fitting in the free intervals to fill (Fig. 5)
• Smallest Free Intervals: to choose the solution that occupies the shorter free intervals to fill (Fig. 6)
• Fit to Left/Right: when a solution has slack fitting, it fits in way to begin as soon/late as possible (Fig. 5)

Still in this phase, when it is not possible to schedule a manufacturing order there are other heuristic rules that can be used to help in reformulating the order or applying other methods.

Examples of these heuristics:

• Maximum/Minimum Fitting Batch Division: to divide the batch into smaller batches in order to fit first the largest/smallest free intervals (Fig. 7)
• Minimum Delay: determine the minimum delay behind the deadline with this order schedule (Fig. 7)
• Free Time Compaction: try to compact the free time intervals of resources in order to obtain bigger free intervals where manufacturing orders can be scheduled.

For the manager to solve those scheduling problems, it is not enough to have a supporting software system with the adequate algorithms. It is fundamental to give adequate information to the manager at any time and that the manager can interact with the system in a graphical and intuitive way.

Therefore, the interface should be intelligent and dynamic to presenting the essential information in an appropriate way and allowing its manipulation in a friendly way. The interface must supports actively manager's activities and allows monitoring of operations [18]. The interface of a system like this is decisive to its success. The balance between autonomy and interactivity is important for the applicability of these systems. The system should be enough flexible to allow the manager to make its own suggestions or decisions, but it also can dynamically acts and guide, mainly in critical situations.

One of the main purposes in developing this system was its flexibility, accessibility and easy way of using. The system is supported by a dynamic graphical user friendly interface (Fig. 8) for the manager easily to access and to manipulate the information about the manufacturing orders, the resources, the processes and the operations [19]. The interface still allows the definition of the scheduling policies to apply to the several situations, the direct graphic manipulation of the schedules, presented like a Gantt graph. It also allows to visualize and to compare the real scenery, that is what is happening in the production, with the scenery planed in order to correct or to minimize eventual deviations. Still, allows comparing several simulated scenarios ("what-if" simulation) resultant from the application of different scheduling policies. This way the manager can better evaluate the future consequences of several alternatives and correctly decide before dispatching to the execution.

Today, to achieve efficiency in production managing, we must use the guidance provided by computer systems that support the complex function of decision-making, particularly in the production scheduling operation.

In this paper, we have presented a Decision Support System for Dynamic Production Scheduling that mainly considers the deadlines of manufacturing orders and the resources occupation. The deadlines are very important for customer satisfaction and the resources optimization is very important for the productivity and production costs. These are strategic factors for the competitiveness and success of an industrial organization.

Oriented by the production manager's scheduling policies, this tool helps in the analysis of the available information suggesting appropriate solutions, through heuristics, for scheduling the manufacturing orders. The system is simple and flexible allowing the manager to make its own suggestions or decisions.

The user interface is very important too for the system’s success. The manager can interact with the system in a graphical and intuitive way. The evaluation of results and their change if necessary (reactive scheduling) helps detecting and avoiding future problems. It is intelligent enough to focus the adequate information to the manager. This is very important in critical situations allowing a significant improvement in solving unpredictable events.

Several refinements in the module of dynamic scheduling and in the user interface are in progress. It is in design stage the integration with the other two modules.

The research now concerns the distributed implementation of the scheduling algorithm based on holonic manufacturing systems [20]. It is also in study the integration of this system with a system for line balancing and simulation [21], supported on a common interface.

Its integration with other production support systems will be studied: MRP, maintenance planning, shop-floor control, etc.