NAME

Schedule::Activity - Generate activity schedules

VERSION

Version 0.2.5

SYNOPSIS

  use Schedule::Activity;
  my $scheduler=Schedule::Activity->new(
    configuration=>{
      node=>{
        Activity=>{
          message=>'Begin Activity',
          next=>['action 1'],
          tmmin=>5,tmavg=>5,tmmax=>5,
          finish=>'Activity, conclude',
        },
        'action 1'=>{
          message=>'Begin action 1',
          tmmin=>5,tmavg=>10,tmmax=>15,
          next=>['action 1','action 2'],
        },
        'action 2'=>{
          message=>'Begin action 2',
          tmmin=>5,tmavg=>10,tmmax=>15,
          next=>['Activity, conclude'],
        },
        'Activity, conclude'=>{
          message=>'Conclude Activity',
          tmmin=>5,tmavg=>5,tmmax=>5,
        },
      },
      annotations=>{...},
      attributes =>{...},
      messages   =>{...},
    }
	);
  my %schedule=$scheduler->schedule(activities=>[
		[30,'Activity'],
		...
	]);
  if($schedule{error}) { die join("\n",@{$schedule{error}}) }
  print join("\n",map {"$$_[0]:  $$_[1]{message}"} @{$schedule{activities}});

DESCRIPTION

This module permits building schedules of activities each containing randomly-generated lists of actions. Each activity is scheduled to a target time by selecting randomly selecting actions within the configured graph, which may contain repetition and cycles, and by using slack and buffer timing adjustments. Attributes may be attached to events and messages, both for reporting and to control scheduling toward a goal. Annotations permit construction of secondary messages around events.

For additional examples, see the tutorial and the samples/ directory.

CONFIGURATION

Overview

A configuration for scheduling contains the following sections:

%configuration=(
  node       =>{...}
  attributes =>{...} # optional
  annotations=>{...} # optional
  messages   =>{...} # optional
)

The named node entries specify the activities and actions used during schedule construction. The activity/action keys are used to configure the relationship between nodes, but the message configuration within each node is the primary value used when formatting scheduling results.

All other sections are optional and described below.

Activities and Actions

Both activities and actions are configured as named node entries. With this structure, an action and activity may have the same message, but must use different key names.

'activity name'=>{
  tmavg     =>value, ...,
  next      =>[...],
  finish    =>'activity conclusion',
  message   =>...    # optional
  attributes=>{...}, # optional
}
'action name'=>{
  tmavg     =>value, ...,
  next      =>[...],
  message   =>...    # optional
  attributes=>{...}, # optional
  require   =>{...}, # optional
}

The list of next nodes is a list of names, which must be defined in the configuration. During schedule construction, entries will be chosen randomly from the list of next nodes. The conclusion must be reachable from the initial activity, or scheduling will fail. There is no further restriction on the items in next: Scheduling specifically supports cyclic/recursive actions, including self-cycles.

There is no functional difference between activities and actions except that a node must contain finish to be used for activity scheduling. Nomenclature is primarily to support schedule organization: A collection of random actions is used to build an activity; a sequence of activities is used to build a schedule.

The require configuration specifies attribute value prerequisites, computed from the current attribute values, that must be met for an action node to be a candidate for random selection. See Schedule::Activity::NodeFilter for available filtering criteria, but see "SCHEDULING ALGORITHM" regarding attribute value consistency.

Time specification

The only time specification currently supported is:

tmmin=>seconds, tmavg=>seconds, tmmax=>seconds

Values must be non-negative numbers. All three values may be identical. Note that scheduling to a given goal may be impossible without slack or buffer within some of the actions:

slack =tmavg-tmmin
buffer=tmmax-tmavg

The slack is the amount of time that could be reduced in an action before it would need to be removed/replaced in the schedule. The buffer is the amount of time that could be added to an action before additional actions would be needed in the schedule.

Caution: While startup/conclusion of activities may have fixed time specifications (including zero time), it is recommended, though not mandatory, that actions always contain some slack/buffer. There is currently no "relaxing mechanism" during scheduling, so a configuration with no slack nor buffer must exactly meet the goal time requested to succeed.

Providing any time value will automatically set any missing values at the fixed ratios 3,4,5. EG, specifying only tmmax=40 will set tmmin=24 and tmavg=32. If provided two time values, priority is given to tmavg to set the third.

Scheduling may be controlled with the tension settings described below. Future changes may support automatic slack/buffering, univeral slack/buffer ratios, and open-ended/relaxed slack/buffering.

Messages

See "CONFIGURATION" in Schedule::Activity::Message for all possible message configurations.

Any activity or action may contain an optional message string or configuration. Messages permit the caller to easily format generated schedules. Messages may contain attributes, which can affect subsequent scheduling. Message attributes are emitted with the attribute response values.

A scheduling configuration may declare a list of named messages, which will be available to all message configurations:

%configuration=(
  messages=>{
    'key name'=>{ message configuration }
    ...
  },
)

RESPONSE

The response from schedule(activities=[...])> is:

%schedule=(
  error=>['list of validation errors, if any',...],
  activities=>[
    [seconds, event],
    ..,
  ],
  annotations=>{...}
  attributes=>{
    name=>{attribute report},
    ...
  },
)

Success Response

When scheduling is successful, the list of events is in the activities array. Each event is an array containing the timestamp, and an event node containing a {message}. Scheduling always occurs in order, so activities should appear in non-decreasing timestamp order. Timestamp units are undefined, so formatting is the responsibility of the caller.

The event{message} is materialized during schedule construction, so the response will only contain the single, chosen message for the event. Alternate messages attached to the underlying event node, or a referenced name message, are not included in the response.

The "annotations" response is described below in "ANNOTATIONS".

For the "attribute report", see "RESPONSE" in Schedule::Activity::Attribute.

Validation Errors

If the configuration fails prechecks, findings will be reported in the error array and scheduling will not be attempted. Configuration errors include invalid type/structures, invalid node keys/values, messages/attributes/annotations, as well as basic activity/action reachability checks. Note that node filtering (via a "require" configuration) may prevent scheduling despite these basic reachability checks.

Unhandled Errors

In addition to validation failures returned through error, the following may cause the scheduler to die(): The requested activity name is undefined. The scheduler was not able to reach the named finish node. The number of retries or backtracking attempts has been exhausted.

The difference between the result time and the goal may cause retries when an excess exceeds the available slack, or when a shortage exceeds the available buffer.

ATTRIBUTES

Attributes permit tracking boolean or numeric values that can be used to affect node selection during schedule construction. The resulting attribute history can be used to verify the final schedule or compute goal scores.

Configuration

For a complete description of attribute configuration options, see Schedule::Activity::Attribute.

Attributes may be referenced from an activity, action, or message. For example:

'action name'=>{
  attributes=>{
    temperature=>{set=>value, incr=>value, decr=>value, note=>'comment'},
    counter    =>{set=>value, incr=>value},
    flag       =>{set=>0/1},
  },
}

The scheduling configuration may also declare attribute names and starting values.

%configuration=(
  attributes=>{
    flagA  =>{type=>'bool'},
    flagB  =>{type=>'bool', value=>1},
    counter=>{type=>'int',  value=>0},
  },
)

Boolean types must be declared in this section. It is recommended to set any non-zero initial values in this fashion, since calling set requires that activity to always be the first requested in the schedule.

Attributes within message alternate configurations and named messages are identified during configuration validation. Together with activity/action configurations, attributes are verified before schedule construction, which will fail if an attribute name is referenced in a conflicting manner.

Precedence

When an activity/action node and a selected message both contain attributes, the value of the attribute is updated first from the action node and then from the message node. For boolean attributes, this means the "value set in the message has precedence". For integer attributes, suppose that the value is initially zero; then, if both the action and message have attribute operators, the result will be:

Action  Message  Value
set=1   set=2      2
incr=3  set=4      4
set=5   incr=6    11
incr=7  incr=8    15

Average Values

Attributes are always logged at the beginning and end of the completed schedule, so that all scheduled time affects the weighted average value calculation. Activities may reset or fix attributes as needed in their beginning or final node; note that the final node is only the "end of the activity" when tmavg=0.

Recomputation

Any schedule of activities associated with the initial configuration can generate a standalone attribute report:

%attributes=$scheduler->computeAttributes(@activities)

This permits manual modification of activities, merging across multiple scheduling runs, or merging of annotations (below) to materialize a final attribute report. This does not affect the attributes within the $scheduler object itself.

ANNOTATIONS

Overview

Annotations are secondary messages and/or attributes that are attached to the scheduling configuration and are inserted around activity/action nodes. Annotations are divided into named groups, permitting separation by category, and each named group contains a list of annotations (or "notes").

Configuration

Annotations are configuration in the annotations section of the scheduling configuration:

%configuration=(
  annotations=>{
    'annotation group'=>[
      {annotation configuration},
      ...
    ],
    ...
  },
)

Each named group is an array, and each note configuration is a hash, as described in Schedule::Activity::Annotation. Annotations may use named messages from the scheduling configuration.

Within an individual group, earlier annotations take priority if two events are scheduled at the same time. Because groups are generated separately, multiple groups of annotations may have conflicting event times in the results. Note that the between setting is only enforced for each annotation individually at this time, and not for notes within the same group.

Response

Annotation groups are generated after scheduling is complete and are reported in the annotations section as:

annotations=>{
  'group'=>{
    events=>[
      [seconds, message],
      ...
    ]
  },
}

Messages in the response are materialized using any named messages, and have the same structure as the message response for activity/action events.

Annotations do not update the attributes response from schedule. Because annotations may themselves contain attributes, they are retained separately from the main schedule of activities to permit easier rebuilding.

Merging

At this time, the caller must merge groups of annotations into schedule{activities} manually. Group order may matter, and the behavior of overlapping or nearby event times must be prioritized based on needs. When constructing schedules incrementally, it is recommended to use the nonote option described in "Incremental Construction".

Rudimentary merging mechanisms are provided in schedule-activity.pl.

SCHEDULING ALGORITHM

Overview

The configuration of the next actions is the primary contributor to the schedules that can be built. As with all algorithms of this type, there are many configurations that simply won't work well: For example, this is not a maze solver, a best path finder, nor a resourcing optimization system. Scheduling success toward the stated goals generally requires that actions have different tmmin, tmmax, and tmavg, and that actions permit reasonable repetition and recursion. Highly imbalanced actions, such as a branch of length 10 and another of length 5000, may always fail depending on the goal. Neverthless, for the activities and actions so described, how does it work?

The scheduler is a randomized, opportunistic, single-step path growth algorithm. An activity starts at the indicated node. At each step, the next entries are filtered and a random action is chosen, then the process repeats. The selection of the next step is restricted based on the current time (at the end of the action) as follows.

First, a random current time is computed based on the current time, the accumulated slack and buffer, and the tension settings (see below). If the random current time is less than the goal time, the next action will be a random non-final node, if available, or the final node if all other choices are filtered or unavailable.

If the random current time is greater than the goal time and the final action is listed as a next action, it will be chosen.

In all other cases, a random next action will be chosen.

Buffer and Slack

Schedule construction proceeds toward the goal time incrementally, with each action appending its tmavg until the goal is reached. If the accumulated average times were exactly equal to the goal for the activity, schedules would be unambiguous. For repeating, recursive scheduling, however, it's necessary to consider scenarios where the actions don't quite reach the goal or where they extend beyond the goal.

Each activity node and action has buffer and slack, as defined above, that contributes to the accumulated total buffer and slack. The amount of buffer/slack that contributes to the random current time is controlled by including schedule(tensionbuffer=>value) and tensionslack=>value, each between 0 and 1. Tension effectively controls how little of each contributes toward randomization around the goal.

In the 'laziest' mode, with tension=0.0, all available buffer/slack is used to establish the random current time, increasing the likelihood that it is greater than the goal. With a lower buffer tension, for example, scheduling is more likely to reach the final activity node sooner, and thus will contain a smaller number of actions on average, each stretched toward tmmax. With a higher tension, the goal time must be met (or exceeded) before aggressively seeking the final activity node, so schedules will contain a larger number of actions, each compressed toward tmmin.

The tension for slack is similar, with lower values permitting a larger number of actions beyond the goal, each compressed toward tmmin, whereas with tension near 1, scheduling will seek the final activity node as soon as the schedule time exceeds the goal, resulting in a smaller number of activities.

The random computed time is a uniform distribution around the current time, but because actions are scheduled incrementally, this leads to a skewed distribution that favors a smaller number of actions. See samples/tension.png for the distributions where exactly 100 repeated actions would be expected.

The default values are 0.5 for the slack tension, and approximately 0.85 for the buffer tension. This gives an expected number of actions that is very close to goal/tmavg (skewed distribution as plus 10% minus 5%).

The scheduling response contains {stat} that reports the accumulated slack and buffer used for all actions, as well as slackttl and bufferttl which represent the maximum available. The amount of slack used during scheduling is slack/slackttl, and the same for buffer. These values can assist with choosing tension settings based on the specific configuration.

Consistency

Attributes may be used for filtering during schedule construction. When scheduling an activity, a temporary history of attributes is built and used as action nodes are selected.

Node filtering applies to the last recorded attributes, independent of any actions a candidate node may take on attributes. Attribute averages values are updated to the "random current time", as if the attribute value was fixed between the last recorded entry and the random current time, prior to node filtering comparisons.

After any filtering and random selection, each activity/action node will update attributes, after which any materialized message will update attributes.

After reaching the target time for an activity, event times are updated based on the total slack/buffer time available. The actual attribute history is constructed from those adjusted times, and will be visible to the next activity scheduled. Filtering is evaluated as a single pass only, so average values visible during filtering may be slightly different than averages after slack/buffer adjustments.

Annotations are computed separately by groups. Attributes arising from merged annotations do not affect attributes retroactively (nor, obviously, any node filtering). See "Recomputation".

Scheduling proceeds stepwise, and "consistency" is defined as adherence to the computed values at that time. No recomputation occurs, except through full retries (such as goal seeking). All of the following can create paradoxes that are avoided with this approach: Slack/buffer adjustments can alter attribute average values leading to different node filtering/selection. Slack/buffer adjustments can produce times that open other action branches that may have be unavailable during scheduling. Annotations that are merged may adjust attributes such that the nodes they are annotating would disappear. Nodes may adjust attributes such that the final node is unreachable.

Incremental Construction

For longer schedules with multiple activities, regenerating a full schedule because of issues with a single activity can be time consuming. A more interactive approach would be to build and verify the first activity, then review choices for the second activity schedule, append it, and continue. After full scheduling construction, annotations can be built.

Incremental schedules can be built using the after and nonote options:

# Use nonote to avoid annotation build at this time
my $choiceA=$scheduler->schedule(nonote=>1, activities=>[[600,'activity1']);
my $choiceB=$scheduler->schedule(nonote=>1, activities=>[[600,'activity1']);
#
# two or more choices are reviewed and one is selected
my %res=$scheduler->schedule(after=>$choiceB, activities=>[[600,'activity2']);

The schedule indicated via after signals that the scheduler should build the activities and extend the schedule. Attributes are automatically loaded from the earlier part of the schedule and affect node filtering normally.

Annotations, which may apply to any node by name, are dropped when the schedule is extended. This is because a single annotation may have a limit and match nodes across activities, so full regeneration is necessary. To make generation more efficient, nonote may be set to skip annotation generation in earlier steps.

The final result above does generate annotations, but it's also possible to pass nonote at each step and then generate annotations without adding activities by calling:

my %res=$scheduler->schedule(after=>$earlierSchedule, activities=>[]);

This functionality is experimental starting with Version 0.2.1.

Goals

Goal seeking retries schedule construction and finds the best, random schedule meeting criteria for attribute average values:

%schedule=$scheduler->schedule(goal=>{
  cycles=>N,
  attribute=>{
    'name'=>{op=>'max'},
    'name'=>{op=>'min'},
    'name'=>{op=>'eq', value=>x},
    'name'=>{op=>'ne', value=>x},
  }
},...)

One or more attributes may be included in the goal, and each of the cycles (default 10) schedules will be scored based on the configured conditions. The max and min operators seek the largest/smallest attribute average value for the schedule. The eq and ne operators score near/far from the provided value. Note that generated schedules may have a different number of activities, so some attribute goals may be equivalent to finding the shortest/longest action counts.

Goal scheduling is experimental starting with 0.2.4. Attributes currently have equal weighting and scores are linear. If no schedule can be generated, the most recent error will raise via die(). Goals can be different during different invocations of incremental construction.

IMPORT MECHANISMS

Markdown

Rudimentary markdown support is included for lists of actions that are all equally likely for a given activity:

* Activity One, 5min
  - Action one, 1min
  - Action two, 2min
  - Action three, 3min
2. Activity Two, 5min
  * Action one, 1min
  * Action two, 2min
  * Action three, 3min
- Activity Three, 5min
  * Action one, 5min

Any list identification markers may be used interchangably (number plus period, asterisks, hyphen). One or more leading whitespace (tabs or spaces) indicates an action; otherwise the line indicates an activity. Times are specified as \d+min or \d+sec. If only a single action is included in an activity, its configured time should be equal to the activity time.

The imported configuration permits an activity to be followed by any of its actions, and any action can be followed by any other action within the activity (but not itself). Any action can terminate the activity.

The full settings needed to build a schedule can be loaded with %settings=loadMarkdown(text), and both $settings{configuration} and $settings{activities} will be defined so an immediate call to schedule(%settings) can be made.

BUGS

It is possible for some settings to get stuck in an infinite loop: Be cautious setting tmavg=0 for actions.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

NAME

VERSION

SYNOPSIS

DESCRIPTION

CONFIGURATION

Overview

Activities and Actions

Time specification

Messages

RESPONSE

Success Response

Validation Errors

Unhandled Errors

ATTRIBUTES

Configuration

Precedence

Average Values

Recomputation

ANNOTATIONS

Overview

Configuration

Response

Merging

SCHEDULING ALGORITHM

Overview

Buffer and Slack

Consistency

Incremental Construction

Goals

IMPORT MECHANISMS

Markdown

BUGS

SEE ALSO

Module Install Instructions