Resource-Constrained Project Scheduling Based on ACO-Critical Chain Method

This paper will present ACO – Critical chain method for scheduling resource-constrained projects. It is based on the critical chain and effective heuristic algorithm method suggested by earlier methods. ACO generates activity lists after searching solution spaces and provides the critical chain used in the chain method. The method then applies both the project buffer and flexible coefficient that adjusts the completed time for the project to more accuracy. The paper also adopts resource utilization change rate to indicate the heuristic information. Two flexible coefficients are given to adjust project completed time.

Resource constrained project scheduling problem (RCPSP) is a generalized class of optimization problem. Its purpose is under the circumstances of the relationship between resource constraints and project tasks, and to minimize a project’s duration by optimizing the schedule and resource allocation. Traditional methods like Design Structure matrix (DSM), Program Evaluation and Review Technique (PERT) and critical path method (CPM) cannot properly run multiple projects simultaneously because they ignore the resource constraint. This method optimizes resource allocation

In RCPSP, suppose a project group has N simultaneous projects with D number of tasks and two virtual activities that do not use time and resources. Then the objective function representing the shortest duration can be shown as: min {max Fi | i 1, 2 … N} (Li, Gong & Kou 486). Fi represents the project completed time.

Ant Colony Optimization (ACO) was initially proposed in the 1990s by Dorigo. It designs virtual ants exploring various routes. Over time, they leave the virtual pheromone’s gradual disappearance. They are able to choose the best route as per the principal of “mutually pheromone closer to line”.  If I is an activity list, in ACO it is constructed by I=(1o,1i….1n+i) (n=∑ni). The activities in ACO are assigned one by one to I from 1o to 1n+I where each assignment symbolizes an ant’s decision. While assigning activity 1r to the r position in I, the Nr set of candidates contains activities with predecessors that are already assigned to the list. As the construction goes on, modification of the Nr set is done step by step. The first ant assigns 10=0 to construct an activity. Then, from the Nr set, the ant selects an activity, say j, and assigns 1r=j from r=1 to r=n. This uses both pheromone and heuristic information. ACO then creates precedence feasible activities. By selecting r-1 activities and scheduling the start times for each, it is then possible to determine the allocated resources and finish times of the activities.

The above descriptions present two problems to be solved by ACO. The first is heuristic significant role played by ACO information, which needs to be expressed. ACO recommends the use of the rate of change of resources utilization to indicate the heuristic information. Secondly, a means must be provided for updating the information. ACO recommends three ways to update information. They are global update, evaporation and local update. Therefore, ACO has several advantages. In the choice of feasible activities, one can choose two types of activities that have the same time. For cut rations, ratios between the lengths of the projects can be used without consideration of the resource constraint and the length of the project using ACO in situations where resources are limited.

Work Cited

  • Li, Kewen, Gong, Lina & Kou, Jisong. Resource-Constrained Project Scheduling Based on           ACO-Critical Chain Method. Shandong: China University of Petroleum & Tianjin           University, 2009. Print.

Efficient Stereo Bitrate Allocation for Fully Scalable Audio Codec

Joint stereo coding has been adopted to improve quality of compressed digital audio. Mid and side stereo coding technique is the most popular technique of stereo coding and it is used in MPEG-1 and MPEG-4. According to ISO 14496-3 published in the year2005, MPEG-4 scalable lossless coding is among the currect MPEG audio coding, which has the potential to integrate functions of perceptual audio coding to a single framework. Eradication of complication associated with the truncators and encoders of the SLS is the main objective of designing the efficient stereo bitrate allocation.

Structurally  MPEG-4 SLS RS comprises of the encoder, truncators, and a decoder. Rahardja, Koh and Licontributed significantly to the enhancement of SLS structure. Particularly Y. Kim and Y. Seo and S. Park  identified the MPEG-4 AAC as the key layer in a perpetual audio code. Besides the core layer, the SLS has a non-core mode in which production of scalable LLE bistreams takes place. A fully SLS can be achieved by using this mode. Transformation of the input audio losslessly in SLS RS encoder leads to generation of integer MDCT coefficient. To generate core bitstream, coefficients are introduced to core layer encoder.

According to R. Yu et. al incorporation of CBAC with BPGC increases the efficiency of BPGC to capture statistical dependencies of a data.  When  SLS is non-core a bit-plane coding is applied directly. Its accuracy depends greatly on present bitrate assigned to various channels.  In this scheme, high efficiency is experienced when M channel is of higher amplitude than the S channel.  By use of truncator, SLS bitstreams can be easily truncated. In an effort to develop efficient stereo bitrate allocation enhanced encoder and truncators have been used. To improve the accuracy recovery of the L/R channel in enhanced encoder more resources should be allocated to M channel. The result obtained by J.Johnston and A. Ferreira on perceptual allocation logarithms was inversely applicable in non-core. Adjusting of the bit allocation plays a significant role in improving operation of pure bit-plane coding. Bit allocation in SLS RS truncator is given by . For the enhanced truncators the   and  cases are considered respectively. In the secong case perceptual core bitstream was first allocated before proportional enhancement was done. To test  formances of an enhanced encoder and truncator two tests were carried out. The audio sequence in test two were losslessly encoded by a RS encoder. Results were measured using OPERA interms of ODG which ranges from -4 to zero.

From the two test carried out it was noticed that both the enhanced truncator and encoder worked perfectly in improving the quality of the first four sequence at different bitrates. Due to lower correction for L and R channels in the last two test an improvement was not obvious. The last two sequences are limited from the pro of M/S stereo coding.

For fully scalable and non-core SLS efficient stereo bitrate allocation algorithms can be implemented to increase their efficiency. Additionally, the knowledge of M/S is crucial in understanding and designing the stereo bitrate.

Though the article comprehensively analyzes the concept, it excludes some of the limitation associated with the conceptualization of the idea. Additionally, it does not portray some of the areas which require further study.  The author has provided summarized information thus understanding some technical section like enhancement of the truncators and encoders has been a challenge.