PROBLEM
Intense global competition has made effective scheduling more critical. Practical scheduling problems, however, are difficult to solve because of their combinatorial nature. The consideration of uncertain factors in real production systems makes the problem even more difficult. For some situations these uncertainties cannot be ignored, otherwise schedules can become outdated very fast or can lead to poor system performance. Uncertainties can be probabilistic in nature; for example, processing times of a particular operation may follow a normal distribution. Uncertainties can also be fuzzy in nature; for example, operators can go below the "standard" processing times while maintaining production quality if the deadlines are urgent, but somehow at the sacrifice of their "comfort levels." The deterministic (crisp) treatment of processing times may lead to a conservative schedule. This paper addresses the balance of on time delivery of parts and the comfort levels of operators.
Probabilistic uncertainties are generally handled by using probability theory, while as fuzzy uncertainties are handled by using fuzzy set theory (Bellman)Fuzzy scheduling can be based on fuzzy heuristic or fuzzy optimization. Schedules generated by fuzzy rule-based methods are difficult to evaluate because of the heuristic nature of the methods. A fuzzy optimization problem is usually converted to a crisp optimization problem, and then solved by using linear or nonlinear programming techniques. A key issue is whether problems of practical sizes can be effectively and efficiently solved.
PROBLEM FORMULATION
In this paper, the scheduling of single-operation parts on identical machines is considered. The integer programming formulation of Luh and Hoitomt (1993) is extended by having fuzzy processing time requirements. To be specific, processing times are not required to be satisfied crisply, but are fuzzy and are characterized by their nominal processing times at 100% of operators' comfort levels, and their shortest processing times achievable without sacrificing operation quality but at zero degree of their comfort level. As a processing time moves closer to its nominal value, the operator feels more comfortable. The objective function to be minimized is the weighted sum of part tardiness square, subject to machine capacity constraints and the above fuzzy processing time requirements.
SOLUTION METHODOLOGY
The goal of fuzzy optimization is to select operation beginning times and processing times so that the weighted tardiness cost is essentially smaller than or equal to some "aspiration level." In this sense, the objective can be regarded as another fuzzy constraint characterized by its aspiration level at 100% of satisfaction, and the largest acceptable cost at zero degree of satisfaction. As a cost moves closer to its aspiration level, the fuzzy objective constraint is better satisfied. Since the fuzzy objective constraint and fuzzy processing time requirements are both desired to be satisfied, the problem is to maximize the minimum degree of satisfaction among all constraints -- the so called "symmetric approach." The converted problem is a crisp separable problem, and is solved by using the Lagrangian relaxation technique. In this process, machine capacity and objective function constraints are relaxed by using Lagrange multipliers, and the problem is decomposed into part subproblems and a membership subproblem subject to fuzzy processing time requirements. The dual function is then maximized by using a subgradient technique. Finally, subproblem solutions are modified by using a simple heuristic to obtain a feasible schedule.
PRELIMINARY RESULTS
The algorithm has been implemented in C++ on Sun sparc station 10. In the following example, nine single-operation parts are to be scheduled on three identical machines with aspiration level 84 and the largest acceptable tardiness cost 101. The rest of data, a schedule generated by the fuzzy method, and a schedule generated by the crisp method of Luh and Hoitomt (1993) using nominal processing times are presented in the following table.
__________________________________________________________________________________________
| part data | fuzzy solution | crisp solution |
__________________________________________________________________________________________
|id due_date weight estart n_p_time s_time | b_time c_time mach m | b_time c_time mach |
__________________________________________________________________________________________
|1 6 5 1 10 7 | 1 9 1 2/3 | 1 10 1 |
__________________________________________________________________________________________
|2 5 1 0 10 6 | 0 8 2 3/4 | 0 9 2 |
__________________________________________________________________________________________
|3 12 2 0 12 10 | 0 11 3 1 | 0 11 3 |
__________________________________________________________________________________________
|4 19 2 0 8 2 | 10 15 1 2/3 | 12 19 3 |
__________________________________________________________________________________________
|5 22 1 0 9 5 | 16 23 1 3/4 | 19 27 1 |
__________________________________________________________________________________________
|6 23 2 1 11 11 | 16 26 2 1 | 18 28 2 |
__________________________________________________________________________________________
|7 52 2 0 7 5 | 19 25 3 1 | 20 26 3 |
__________________________________________________________________________________________
|8 11 1 0 8 5 | 9 15 2 2/3 | 10 17 2 |
__________________________________________________________________________________________
|9 18 2 0 8 5 | 12 18 3 2/3 | 11 18 1 |
__________________________________________________________________________________________
| | fuzzy cost 89 | crisp cost 207 |
__________________________________________________________________________________________
In the above table, estart is the earliest time when a part can be started, n_p_time is the nominal processing time, s_time is the shortest processing time, b_time and c_time are respectively the beginning and completion times, mach is the machine assigned, and m is the fuzzy comfort level of operators.
The cost obtained by the fuzzy algorithm is 89, which is closer to the aspiration level 84 as opposed to the largest acceptable cost 101, and is much smaller than the cost 207 obtained by the crisp algorithm. Processing times for parts 1, 2, 4, 5, 8, 9 are also closer to their nominal processing times as opposed to their shortest processing times, and parts 3, 6, 7 are processed at their nominal processing times. The minimum degree of satisfaction among all fuzzy constraints is 2/3. The method thus leads to a significant reduction of the tardiness cost, and provides an effective balance between on-time delivery of parts and the comfort levels of operators. In addition, the schedule generated by the fuzzy algorithm is different from the crisp one, implying that it would not be easy to obtain the fuzzy schedule by directly employing the crisp algorithm.
We believe that the method can be effectively extended to handle fuzzy uncertainties in a job-shop environment.