A genetic scheduling methodology for virtual cellular manufacturing systems: an industrial application

Effective solutions to the cell formation and the production scheduling problems are vital in the design of virtual cellular manufacturing systems (VCMSs). This paper presents a new mathematical model and a scheduling algorithm based on the techniques of genetic algorithms for solving such problems. The objectives are: (1) to minimize the total materials and components travelling distance incurred in manufacturing the products, and (2) to minimize the sum of the tardiness of all products. The proposed algorithm differs from the canonical genetic algorithms in that the populations of candidate solutions consist of individuals of different age groups, and that each individual's birth and survival rates are governed by predefined aging patterns. The condition governing the birth and survival rates is developed to ensure a stable search process. In addition, Markov Chain analysis is used to investigate the convergence properties of the genetic search process theoretically. The results obtained indicate that if the individual representing the best candidate solution obtained is maintained throughout the search process, the genetic search process converges to the global optimal solution exponentially.

The proposed methodology is applied to design the manufacturing system of a company in China producing component parts for internal combustion engines. The performance of the proposed age-based genetic algorithm is compared with that of the conventional genetic algorithm based on this industrial case. The results show that the methodology proposed in this paper provides a simple, effective and efficient method for solving the manufacturing cell formation and production scheduling problems for VCMSs.     

Assignment rules in robotic mobile fulfilment systems for online retailers

We study robotic mobile fulfilment systems for online retailers, where products are stored in movable shelves and robots transport shelves. While previous studies assume random assignment rule of workstations to robots, we propose an assignment rule based on handling speeds of workstations and design a neighbourhood search algorithm to find a near optimal assignment rule. We build semi-open queueing networks and use a two-phase approximate approach for performance estimation. We first replace workstation service processes by a composite service node and then solve the model by the matrix-geometric method. Simulations are used to validate the analytical models. Numerical experiments are conducted to compare random, handling-speeds-based, near optimal and optimal assignment rules, in terms of retrieval throughput time. The results show that the random assignment rule is not a good choice, the handling-speeds-based assignment rule significantly outperforms the random assignment rule when the workers have large handling time difference, and the neighbourhood search approach can provide an assignment rule that is very close to the optimal one, using a much shorter time. Moreover, we design the shelf blocks under the examined assignment rules, and find that the optimal width of shelf block decreases with the width to length ratio.     

OFDMA系统中支持混合业务的跨层调度算法

针对正交频分多址接入(OFDMA)系统下行链路的混合业务调度问题,提出了一种基于队列等待时间的跨层调度算法.该算法联合利用了MAC层的队列等待时间与物理层的信道状态信息作为调度参数,通过队列等待时间反映用户的服务质量要求,并利用多用户分集增益提高系统性能;针对实时和非实时用户的不同服务质量要求,在队列等待时间的计算上采取了不同的策略;在子载波的分配过程中根据分配状态及时更新队列等待时间,使资源的利用更为有效.仿真结果表明,提出的算法可显著降低实时用户的平均时延和最大延时违反概率,同时保证了非实时用户的吞吐量需求,能够有效地支持下一代网络中混合业务的多种服务质量要求.