Abstract: In this study, the triangular membership functions are used for flexible flow-lines with m machine centers to examine processing-time uncertainties and to make scheduling more suitable for real applications. A methodology is developed for modeling flexible flow line scheduling with fuzzy processing times, fuzzy due dates, fuzzy set-up times, fuzzy holding costs and fuzzy shortage costs. A fuzzy scheduling model is presented and a hybrid algorithm is also designed for its solution. Finally, some numerical examples are developed and solved to demonstrate the computational efficiency of the proposed algorithm.
INTRODUCTION
In simple flow-line problems, each machine center has just one machine. If at least one machine center has more than one machine, then the problem is called a flexible flow-line problem (Allaoui and Artiba, 2006). Flexible flow-lines are thus generalizations of simple flow-lines. Scheduling jobs in flexible flow-lines is considered an NP-complete problem (Janiak et al., 2007).
Flexible flow-line problems have received considerable attention from researchers during the last two decades. However, the scheduling criterion most frequently considered in those papers was the maximum completion time (Chang et al., 2004; Logendran et al., 2005). Furthermore, these studies propose either an exact algorithms, which can solve only up to moderate size problem instances, or different types of heuristic and approximation algorithms (Chang et al., 2004; Kyparisis and Koulamas, 2001). Botta-Genoulaz (2000) has proposed six heuristic approaches for minimizing the maximum tardiness in a scheduling problem with N jobs and M stages in a flexible flow-line environment with identical parallel machines and under time lag and due date constraints. Lin and Liao (2003) also proposed a near optimal heuristic approach for minimizing the maximum tardiness in a two-stage flexible flow-line scheduling problem. They applied an integer linear programming model, a genetic algorithm and a lower bound as approximate methods respectively. Vob and Witt (2007) studied a 16 stage real-life scheduling problem in a flexible flow-line environment with the objective of minimizing the tardiness. They proposed a limited resource mathematical model based on this scheduling problem and then solved it using a heuristic approach. Liu and Chang (2000) also have studied a Lagrangean Relaxation approach for solving a flexible flow-line problem with m stages that minimize the sum of set-up and preparation times. Kurz and Askin (2003, 2004) have examined the m-stage flexible flow-line problem for minimizing the maximum makespan considering the sequence-related set-up times. Pugazhendhi et al. (2004) applied heuristic approaches in m stage flexible flow-line problem to minimize the total weighted flow-time. Ruiz et al. (2006, 2008) and Ruiz and Maroto (2006) in three articles has used heuristic and meta-heuristic GA approaches for minimizing the maximum makespan in m stage flexible flow-line problem.
In the conventional scheduling problem, the parameters such as job processing times, ready times, due dates have been assumed to be deterministic (Jin et al., 2006). However, in the real-world situations, these parameters are often encountered with uncertainties. Accordingly, scheduling problems have been mainly branched into two categories: deterministic scheduling and uncertain (stochastic, fuzzy, etc.) scheduling. In fact, various factors involved in the scheduling problems are often imprecise or uncertain in nature when we formulate scheduling problems in the real-world. This is especially true when human-made factors are incorporated into the problems. In these cases, it seems more appropriate to consider fuzzy processing times, fuzzy due-dates and so on.
Konno and Ishii (2000) discussed an open line scheduling problem with fuzzy allowable time and fuzzy resource constraint. Litoiu and Tadei (2001) presented some new models for real-time task scheduling with fuzzy deadlines and processing times.
There are three main approaches reported in the literature for the fuzzy scheduling problems: fuzzifying directly the classical dispatching rules (Ozelkan and Duckstein, 1999), using fuzzy ranking (McCahon and Lee, 1990) and fuzzy dominance relation methods (Asano and Ohta, 1996) and solving mathematical programming models to determine the optimal schedules by heuristic approximation methods (Hapke and Slowinski, 1996) including Genetic Algorithm (GA) (Sakawa and Kubota, 2000), simulated annealing (Kolonko, 1999), tabu search (Armentano and Ronconi, 1999), etc.
A limited amount of literature has been devoted to Fuzzy Flexible Flow-Line Scheduling Problems (FFFLPs). In this paper, as a practical application, we focus on the FFFLPs with fuzzy processing times, fuzzy due dates, fuzzy set-up times, fuzzy holding costs and fuzzy shortage costs. Triangular fuzzy numbers that can be used to present the natural pessimistic, moderate and optimistic estimates of uncertain execution times are used to represent fuzzy task values. We use triangular membership functions for flexible flow-lines with m machine centers to examine processing-time uncertainties and to make scheduling more suitable for real applications. Since the processing time, due date, set up time, holding cost and shortage cost of each job are uncertain, the final completion time, starting time, earliness and tardiness are also uncertain and can be represented by a triangular membership function. We design a hybrid algorithm to solve the formulated scheduling model. Effectiveness of the proposed algorithm is demonstrated through some numerical experiments.
ASSUMPTION NOTATION AND MATHEMATICAL MODEL
In this study, the assumptions and notations for FFFLPs are described as follows:
ASSUMPTIONS
| • | Each machine can process only one job at a time |
| • | All jobs are available for machine processing simultaneously at time zero |
| • | Jobs are not pre-emptive |
| • | Each job has m tasks to be executed in sequence on m machine centers |
| • | All machine centers have the same number of identical machines |
| • | The processing times, due date, set up times, holding cost and shortage cost membership functions of each task are triangular and known |
NOTATIONS
| I = 1, 2,. . . , n | : | The jobs to be scheduled |
| k = 1, 2,. . . , m | : | The machines |
| j = 1, 2,. . . , m | : | The stages |
| : | Completion time of job i | |
| : | Completion time of job i in stage j | |
| : | Earliness of job i | |
| : | Tardiness of job i | |
| : | Due date of job i | |
| : | Ready time of job i | |
| : | Processing time of job i in stage j | |
| : | Set-up time of job i in stage j | |
| : | Holding cost of job i per time unit | |
| : | Shortage cost of job i per time unit | |
| : | Starting time of job i in stage j | |
A fuzzy flexible flow-line system is defined by the set M = {1,…,j,…,m}
of m processing stages (machine centers). Each stage j, j ∈ M is
a set composed of k identical machines. Set I = {1,…,i,…,n} composed
of n independent jobs has to be processed at the M stages and one of K identical
machines at each stage. Each job i, i ∈ I is considered as a sequence of
m operations with processing times
| (1) |
Subject to:
| (2) |
| (3) |
| (4) |
| (5) |
| (6) |
| (7) |
| (8) |
| (9) |
| (10) |
The objective is to minimize the total fuzzy holding and shortage costassociated with earliness and tardiness. Relation (2) reflects the fuzzy earliness or fuzzy tardiness for each part with respect to the defined fuzzy due date. Relation (3) indicates that job i in stage j requires only one machine. Relation (4) guarantees that a machine can process at most one job at a time. Relation (5) assures that completion time of each job that immediately precedes another job is greater than or equal to the sum of fuzzy processing and set-up times of that job on all machines. In this relation L denotes larger positive number. Relation (6) ensures that completion time of each job in stage j is greater than or equal to the sum of fuzzy processing and set-up times on all machines. Relation (7) shows that total fuzzy starting time of each job at stage j is greater than or equal to its fuzzy starting time in the previous stage and its fuzzy processing and set-up times at that stage. Relation (8) represents the starting time constraint for job i and Relations (9) and (10) represent the state of the variables.
HEURISTIC ALGORITHMS
As described earlier, an ordinary flow-line scheduling problem is a problem with only one machine at each stage. So, it’s a NP-hard type problem. Two-stage problem would also be NP-hard in case there is more than one machine in each production stage. Thus, HFS problem is generally considered as an NP-hard and the complexity level of the problem increases significantly with the number of stages. In this paper a heuristic approach is presented based on three algorithms. (1) job allocating algorithm, (2) production scheduling algorithm for each ordinary flow-line and (3) resource leveling algorithm. In the first algorithm, the order and sequence of the jobs to be done on machines are determined. In the second algorithm, the allocated jobs are ordered and scheduled on each machine and finally, in the third algorithm resource leveling for each job is performed according to its fuzzy due date. If after several iterations, no improvement is observed in the solution then stopping condition is satisfied.
Algorithm 1: allocating jobs to machines: This algorithm includes the following steps:
Step 1: Calculate the total fuzzy processing times in each work center.
| (11) |
Step 2: Calculate the average time required for each machine in each work center.
| (12) |
in which, K is the number of machines at each stage.
Step 3: Determine the bottleneck work center by fuzzy ranking numbers.
| (13) |
Step 4: Sequence the existing jobs in the bottleneck work center j according to SPT rule.
| (14) |
in which, j is the bottleneck work center.
Step 5: Assign K jobs to machines in stage j from the ordered list in step 4 (These jobs have the minimum processing time in stage j)
Step 6: Assign the next job in the list to a machine with the smallest allocated processing time.
Step 7: Continue calculation until all jobs of stage j are assigned to a machine.
Step 8: Provide a list of these jobs and then distribute other jobs of the work centers to machines by fuzzy ranking numbers.
In step 8, according to list of the assigned jobs to each machine, K flexible flow-lines are decomposed into K ordinary flow-lines.
Algorithm 2: The allocated jobs: In order to solve the fuzzy ordinary flow-line problems regarding the total cost minimization objective of the fuzzy tardiness and earliness, a hybrid approach (EDD+JIT) has been developed. In this approach an initial sequence is determined using the EDD rule. The difference between fuzzy earliness and tardiness values is minimized using the JIT criteria, in which a job is replaced with another job until a specific job sequence is obtained. In this study, the jobs are considered to be individual, independent and processed on all machines. The problem n/m/F/ETSum is solved as follows:
Step 1: Order all jobs according to EDD rule and then allocate them to machines in the obtained order.
| (15) |
Step 2: Calculate the completion time (
| (16) |
Step 3: Calculate the completion time for each job
Step 4: Calculate the fuzzy earliness and tardiness values for each job according to the sequence obtained in step 3.
| (17) |
Step 5: Calculate the sum of the fuzzy earliness and tardiness values
| (18) |
Step 6: Improve the operational sequence in fuzzy ordinary flow-line problems. This step includes the following sub-steps:
|
(a) |
Choose the job with maximum fuzzy tardiness value in the operational sequence determined in step 3. If there is no fuzzy tardy, go to algorithm C. |
| (19) |
|
(b) |
Choose the job with maximum fuzzy earliness value in the determined operation sequence in step 3. If there’s no fuzzy early, go to algorithm C. |
| (20) |
|
(c) |
Change the sequence of the chosen jobs in step (a) and (b) to the operation sequence in step 1. |
Step 7: Recalculate step 3, 4, 5 for the new operation sequence.
Step 8: Comparison criterion and better solution determination, calculate
the
Step 9: Algorithm stopping condition, which includes the following sub-steps:
| (a) |
If new |
| (b) | If no remarkable improvement is observed go to algorithm C (minimum remarkable improvement is considered to be 5%). |
| (c) | If number of iterations reaches to 20 go to algorithm C. |
Step 10: If none of the stopping conditions mentioned above are reached
and the new
Algorithm 3: leveling the remaining resources: This algorithm includes the following steps:
Step 1: Calculate the fuzzy earliness and tardiness for K ordinary flow-lines.
| (21) |
Step 2: Calculate the fuzzy earliness and tardiness for each ordinary fuzzy flow-line.
| (22) |
Step 3: Improve the operational sequence in fuzzy flexible flow-line. It includes the following sub-steps:
|
(a) |
Determine the fuzzy ordinary flow-line with maximum fuzzy tardiness. This job has the maximum fuzzy tardiness among K ordinary flow-lines. If there’s no ordinary flow-line with fuzzy tardiness value we stop. |
| (23) |
|
(b) |
Determine the fuzzy ordinary flow-line with maximum fuzzy earliness. This job has the maximum fuzzy earliness among K ordinary flow-lines. If there’s no ordinary flow-line with fuzzy earliness value we stop. |
| (24) |
|
(c) |
Choose the job with maximum fuzzy tardiness value in the determined fuzzy ordinary flow-line in step (a). If there’s no line with fuzzy tardiness value we stop. |
| (25) |
|
(d) |
Choose the job with maximum fuzzy earliness value in the determined fuzzy ordinary flow-line in step (b). If there’s no line with fuzzy earliness value we stop. |
| (26) |
| (e) | Replace the chosen job in step (c) from the selected fuzzy ordinary flow-line in step (a) with the chosen job in step (d) from the selected fuzzy ordinary flow-line in step (b). |
Step 4: Reapply algorithm B for the two selected fuzzy ordinary flow-line in steps (a) and (b) with respect to the resource leveling.
Step 5: Comparison criterion and the better solution determination; Calculate the Z value for the new state using relation (21) and go to step 6.
Step 6: Algorithm C stopping condition, which includes the following sub-steps:
| (a) | If new |
| (b) | If no remarkable improvement is observed we stop (minimum remarkable improvement is considered to be 5%). |
| (c) | If the number of iterations reaches to 20 we stop. |
Step 7: If none of the stopping conditions mentioned above are reached
and the new
COMPUTATIONAL EXPERIMENTS
The efficiency of the proposed algorithms is verified by choosing 400 random instances with the following characteristics:
| • | Dimensions of the problems are between (NMK) = (20x5x3) and (NMK) = (200x300x20) |
| • | Set-up times for each job at each stage are chosen fuzzy numbers (1, 8, 15). |
| • | Holding (earliness) and shortage (tardiness) costs for each job at each stage are chosen fuzzy numbers (1, 8, 15). |
| • | Operation processing time for each job at each stage is chosen fuzzy numbers (10, 25, 40). |
| • | Due date for each job at each final stage is chosen fuzzy numbers (150, 300, 450). |
| Table 1: | Comparison of STE for three methods |
| 1: (a+4b+c)/6, 2: (a+4b+c)/6, | |
| Table 2: | Comparison of time for three methods |
To solve the above problems, a computer program has been developed based on (EDD+JIT) algorithm. This algorithm is evaluated on the basis of the deviation from the optimal solution using the formula:
| (27) |
where, STE is the sum of fuzzy tardiness and earliness costs.
The results obtained by using Eq. 27 is shown in Table 1. It can be seen that the results of the proposed heuristic solution are very close to the optimal solution.
Comparative results reveal that the solution time obtained by EDD+JIT approach is less than those obtained by the optimal solution (Table 2).
Figure 1 provides a comparison of the solution time in (EDD+JIT) and optimal solution. Figure 2 provides a comparison of objective function value in (EDD+JIT) and optimal solution.
Moreover, EDD+JIT algorithm is able to solve large size problems with a high accuracy in a lesser time compared to the optimal solution software algorithm (conventional method).
| Fig. 1: | Comparison of time in the two methods |
| Fig. 2: | Comparison of STE in the two methods |
The conventional method has a limited executing time i.e., 240 min, in which the huge problems can not be solved in due times, but the proposed program can solve large size problems in less than 240 min.
CONCLUSION
Appropriate scheduling not only reduces manufacturing costs but also reduces the possibility of violating due dates. Finding good schedules for given set of jobs can thus help factory supervisors control job flows and provide for nearly optimal job sequencing. Scheduling jobs in flexible flow-lines has long been known to be an NP complete problem. Since task processing times, set-up times, due dates, holding costs and shortage costs in real applications are usually uncertain, in this paper; we have proposed a fuzzy hybrid scheduling algorithm for scheduling jobs in flexible flow-lines with m machine centers. The scheduling results are a fuzzy set and can help system managers have broader views of scheduling and make good analysis. Computational experiments presented in this research imply the near optimal utilization of the limited resources (bottleneck) and its superiority over integer linear programming from the time reduction point of view. Moreover, it was shown that due to the computational complexity and time increase in the solution of large size problems, the EDD+JIT approach seems to be much better.