Time constrained scheduling

Time-constrained scheduling (7US) Hnd a feasible (or optimal) schedule for X that obeys the precedence constraints and meets the deadline D. 

Two types of scheduling may be performed at this stage. A time-constrained scheduler finds one of the cheapest schedules under the constraint of the maximum number of control steps While a resource-constrained scheduler finds one of the fastest schedules based on a resource constraint. 

Time-constrained Scheduling Given constraints on the maximum number of time steps, find one of the cheapest schedules. 

The time-constrained scheduling finds its application in real time digital signal processing where the sampling rate dictates how fast a data must be processed. We restrict the input to the time-constrained scheduler be single basic blocks or iterative loops. The resource-constrained scheduler, on the other hand, is applicable to more general applications and accepts inputs that contain multiple loops and/or branches. 

In [4], we have proposed an Integer Linear Programming(ILP) formulation for the time-constrained scheduling problem. Since we use the As-Soon-As-Possible(ASAP) and As-Late-As-Possible(ALAP) scheduling techniques to reduce the solution space, the ILP formulation is very efficient and able to optimally solve practical problems, such as the fifth order elliptic filter[10], in a few seconds. 

We recently combine both the time-constrained scheduling and the function unit selection problems into a single formulation[ll]. Given an internal representation, a design style and a module library, our objective is to find a minimum cost schedule and bind each operation to a type of function unit simultaneously. 

The objective function states that we are going to minimize the total number of control steps. Constraint (4) states that no schedule should invoke more than function units of type t. Note that is a constant. Constraints (5) and (6) are the same as those in the time-constrained scheduling. IMo operations should be scheduled after Cstep, as described in constraint (7). 

Z. K. Hsu and Y. C. Hsu, "Time-Constrained Scheduling with Function Unit Selection", in preparation. 

Each work package in the WBS is decomposed into the activities required to complete its predefined scope. A list of activities is constructed and the time to complete each activity is estimated. Estimates can be deterministic (point estimates) or stochastic (distributions). Precedence relations among activities are defined, and a model such as a Gantt chart, activity on arc (AOA), or activity on nodes (AON) network is constructed (Shtub et al. 1994). An initial schedule is developed based on the model. This unconstrained schedule is a basis for estimating required resources and cash. Based on the constraint imposed by due dates, cash and resource avaUabUity, and resource requirements of other projects, a constrained schedule is developed. Further tuning of the schedule may be possible by changing the resource combination assigned to activities (these resource combinations are known as modes). 

Chekuri C, Motwani R (1999) Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Appl Math 98 29-38... 

We have described an approach for processor synthesis. We divide the problem into three interdependent subtasks, namely, operation scheduling, data path binding and controller synthesis. The first subtask includes both time-constrained and resource-... 

The model of the scheduling problem is based on a discrete representation of time where each period i corresponds to one day. The scheduler assigns the number of batches x to be produced in each period. The capacity of the plant is constrained... 

Clearly, this class of problems requires a triple optimisation, so-called integrated optimisation, at the same time allocating available resources to each production line, production line sequencing and production line scheduling. It is a multidimensional, precedence-constrained, knapsack problem. The knapsack problem is a classical NP-hard problem, and it has been thoroughly studied in the last few decades [2]. 

The top level hierarchical plan becomes the input for the next level of planning, which is the master production schedule (MPS) or master schedule level. This schedule is always prepared in terms of end items (i.e., what is shipped from the factory or plant). If the factory produces bicycles, then the end item is a bicycle. But, if the factory produces front wheels for another factory that assembles them onto frames, then the end item is the front wheel. Planning for the MPS is constrained by the earlier planning which resulted in the production plan. Remember that the production plan was developed in terms of product families. The MPS is very specific about the end item. For example, the production plan for an apparel factory may have scheduled 200 dozen men s long sleeve shirts for the month of January. The production plan did not specify color or design, just the family of shirts that would be produced. The MPS might then divide up these 200 dozen into specific end items to be produced in specific time periods. This is illustrated in Figure 9.3 for the month of January. Note that the shirts that are scheduled to be produced in all of the weeks of January total the 200 dozen scheduled to be produced in January. 

In the final case of minimum-time constraints, conflicts can arise when the constrained operator also has a maximum-time constraint, as shown in Figure 5-7. In this case, constraint Cl requires that the relative time between operators X2 andxg be greater than than time Tl. At the same time, constraint C2 requires that the relative time between operators XQ and X2 be less than time T2. As in the other cases, a new constraint must be added to prevent a conflict between the two constraints. However, the value of the new constraint is now the difference between the maximum-time constraint and the minimumtime constraint. If this difference is positive, then the new constraint must be treated as a maximum-time constraint. However, if it is negative then the new constraint must be treated as a minimum-time constraint. This guarantees that both of the original constraints will be satisfied in scheduling. 

---