مسئله "تولید با سرعت زیاد" قابل انعطاف با جریان کلی به حداقل رساندن زمان کل

In this study, we consider total flow time problem in a flexible flowshop environment. We develop a branch and bound algorithm to find the optimal schedule. The efficiency of the algorithm is enhanced by upper and lower bounds and a dominance criterion. Computational experience reveals that the algorithm solves moderate sized problems in reasonable solution times.

This paper addresses the problem of scheduling n jobs on w serial stages, each stage including several parallel identical machines. A job should be processed on any one of the parallel machines at each stage. Such an environment is called a flexible flowshop. Our scheduling objective is to minimize total flow time. Flexible flowshops are generalizations of flowshops. The literature for the flowshop problem has grown after Johnson’s (1954) well-known algorithm for the two stage maximum completion time, i.e. the makespan problem. Many of the studies on flowshops consider the minimization of makespan and total flow time. The studies by Gupta and Dudek (1971) and Panwalker et al. (1972) have revealed that total flow time problem is more representative of scheduling costs than makespan. The branch and bound algorithms by Ignall and Schrage, 1965 and Bansal, 1977 and Ahmadi and Bagchi (1990) and heuristic approaches by Ho and Chang, 1991 and Miyazaki et al., 1978 and Rajendran and Chaudhuri (1991) are among various attempts to solve the total flow time problem on flowshops. Recent studies have recognized the importance of flexible flowshops to reduce the delays caused by bottleneck stages. Flexible flowshop problems arise in a number of different settings including polymer, chemical, and petrochemical industries (Salvador, 1973). It has been encountered in certain manufacturing systems (Zijm and Nelissen, 1990) and in assembly lines with parallel machines at workstations (Brah and Hunsucker, 1991), electronics industry (Guinet and Solomon, 1996) and textile industry (Guinet, 1991).

We considered the problem of minimizing total flow time in a flexible flowshop problem. To our knowledge, there is no other published work that considers finding an optimal schedule for this problem. We proposed lower and upper bounding schemes and incorporated them into a branch and bound algorithm. We used two branching schemes. Our computational experiments showed that the algorithm is capable of generating optimal solutions for medium-sized problems. The branch and bound algorithm produces the optimal solution at very early stages and the majority of the time is spent to show that the solution is optimal. A branch and bound algorithm terminated after a prespecified time limit may be an attractive heuristic solution for larger size problems if proving the optimality of the solution is not crucial. The model we studied can be generalized to include due-date related performance measures and/or flexible job shops.