3
\$\begingroup\$

This code attempts to solve a suggested challenge by myself a while back on meta, transcribed here for simplicity.

Allocate resources efficiently on a work environment

The company Code42Review demands that their employees are able to handle work items as efficiently as possible.

Those work items are assigned according to the work item chooser that decides which work items get assigned to which employees. The work item chooser takes into account the skills needed by a certain work item and tries to match them as close as possible to the skills of an employee. While some skills are mandatory others are "nice to have". The work item chooser may delay assignment due to not having any employee available with a required skill.

A work item only exists if a work candidate has acquired all resources sucessfully. Acquiring a resource is a process that may require time, in this particular work envoirnment, up to 20 seconds. The process of acquiring a resource is not guarteed to succeed because such resources might not be available. (the successful rate of resource acquisition is tipically under 50%)

In this work enviorment an employee may take up to several minutes to complete a work item. Usually something between 2 and 20 minutes. An employee that is handling a work item is considered to be busy and may not have another work item assigned to him.

A work item should be assigned to an employee within the shortest amount of time possible, if it's not assigned to an employee within a reasonable time, the resources may no longer be available. In this scenario the work item will be replaced by another.

I am just covering the very basics of my challenge. I have a work producer that keeps producing work items if at least one worker is available. The work item is assigned to the first available employee. I also keep track of the time that each employee has worked and the amount of time each employee has waited.

This is my first time trying to do something in so it's only natural that there will be lots of things to improve.

The module WorkItem is where most of the code is at. Basically there is WorkItem type that represents a workitem in any given state (new, assigned, completed).

There is the operation assignWorkItem to assign a workItem to a worker.

The operation completeWorkItem to complete a workItem.

The handleWork which is basically waiting a random amount of time, simulating the worker getting the work item done.

And the workitemCreator that is able to create work items based on a policy (which employee should perform said work item).

module WorkItem

open System
open System.Threading.Tasks
open System.Linq
open System.Threading

    [<StructuredFormatDisplay("{Date} - {FastTime}")>]
    type TimeReference() =
        let time = DateTime.UtcNow
        let now = Environment.TickCount
        member x.FastTime = now
        member x.Date = time
        static member (-) (a : TimeReference, b : TimeReference) = TimeSpan.FromMilliseconds (float (a.FastTime - b.FastTime))

    type WorkResult =
        | FullyCompleted
        | NotAssignedInTime
        | Abandoned
        | AssigneeAbandoned

    type Assignee = {
        mutable isBusy:bool; 
        name:string; 
        mutable totalWorkTime:int64; 
        mutable totalWaitTime:int64; 
        mutable lastCompletedTime:TimeReference
    }

    let createWorker name =
        {isBusy = false; name = name; totalWorkTime = 0L; totalWaitTime = 0L; lastCompletedTime = new TimeReference()}

    type NewWorkItem = {
        createdAt:TimeReference
    }

    type AssignedWorkItem = {
        createdAt:TimeReference; 
        assignedAt:TimeReference; 
        firstAssignee:Assignee
    }

    type FinnishedWorkItem =  {
        createdAt:TimeReference; 
        assignedAt:TimeReference option; 
        firstAssignee:Assignee option; 
        completedAt:TimeReference; 
        workResult:WorkResult
    }

    type WorkItem =
        | NewWorkItem of NewWorkItem
        | AssignedWorkItem of AssignedWorkItem
        | CompletedWorkItem of FinnishedWorkItem


    let assignWorkItem (item:NewWorkItem) (assignee:Assignee) =  
        if not assignee.isBusy then
            assignee.isBusy <- true
            Some (AssignedWorkItem {
                createdAt = item.createdAt; 
                assignedAt = new TimeReference(); 
                firstAssignee = assignee
            })
        else 
            None

    let completeWorkItem (item:AssignedWorkItem) workTime =
        item.firstAssignee.totalWorkTime <- item.firstAssignee.totalWorkTime + workTime
        item.firstAssignee.lastCompletedTime <- new TimeReference();
        item.firstAssignee.isBusy <- false
        printfn "%A WorkT-%A WaitT-%A" item.firstAssignee.name 
            (TimeSpan.FromMilliseconds(float item.firstAssignee.totalWorkTime)) 
            (TimeSpan.FromMilliseconds(float item.firstAssignee.totalWaitTime)) 
        CompletedWorkItem {
            createdAt = item.createdAt; 
            assignedAt = Some item.assignedAt;
            firstAssignee = Some item.firstAssignee;
            completedAt = new TimeReference();
            workResult = FullyCompleted
        }

    let assigneeAbandonWorkItem (item:AssignedWorkItem) =
        CompletedWorkItem {
            createdAt = item.createdAt; 
            assignedAt = Some item.assignedAt;
            firstAssignee = Some item.firstAssignee;
            completedAt = new TimeReference();
            workResult = AssigneeAbandoned
        }

    let private createWorkItem chance =
        Enumerable.Range(1, Utils.accumulativeChance chance |> fst)
        |> Seq.map (fun  _ -> Utils.randTime (TimeSpan.FromSeconds(5.0)) (TimeSpan.FromSeconds(12.0)))
        |> Seq.iter (fun delay -> 
            Task.Delay(delay) |> Async.AwaitTask |> ignore
        )
        { createdAt = new TimeReference() }

    type assignmentPolicy = Assignee list -> Assignee Option
    type workProduced = AssignedWorkItem -> Assignee -> Unit
    type workThroughputConstrainer = Assignee list -> bool

    let firstAvailablePolicy (workers: Assignee list) =
        workers
        |> Seq.tryFind(fun worker -> not worker.isBusy)

    let handleWork (assignment:AssignedWorkItem) (worker:Assignee) =
        printfn "%A is handling %A" worker.name assignment.createdAt
        let workTime = Utils.randTime (TimeSpan.FromMinutes(2.0)) (TimeSpan.FromMinutes(20.0))
        let elapsed = (new TimeReference() - worker.lastCompletedTime).TotalMilliseconds
        worker.totalWaitTime <- worker.totalWaitTime + int64 elapsed
        Thread.Sleep(workTime)
        completeWorkItem assignment (int64 workTime.TotalMilliseconds)

    let shouldCreateWorkItem (workers:Assignee list) =
        workers
        |> Seq.exists (fun worker -> not worker.isBusy)

    let workitemCreator chance (workers:Assignee list) (assignmentPolicy:assignmentPolicy) (constrainer:workThroughputConstrainer) =
        Utils.createTimer 100 (fun _ -> 
            if not (constrainer workers) then ()
            let work = createWorkItem chance
            let worker = assignmentPolicy workers
            match worker with
            | Some worker -> 
                let assignment = assignWorkItem work worker
                match assignment with
                | Some (AssignedWorkItem assignment) -> handleWork assignment worker |> ignore
                | _ -> ()
            | None -> ()
            ()
        )

    let firstAvailableWorkItemCreator workers = workitemCreator 0.5 workers firstAvailablePolicy shouldCreateWorkItem

module Utils
    open System

    let rand = Random()

    /// Generates a random time between min and max Timespans
    let randTime (min:TimeSpan) (max:TimeSpan) =
        let time = rand.Next(int min.TotalMilliseconds, int max.TotalMilliseconds)
        TimeSpan.FromMilliseconds(float time)

    /// Generates compounding random probailities until it reaches the sucessRate.
    /// Meaning that as each probability is generate it is multiplied by all previously generated ones.
    ///
    /// Example: sucessRate = 20% = 0.2
    /// Probability = 1 - successRate = 0.8
    ///
    /// Generated probabilities:
    ///
    /// 1. 10% = 0.1 (compounding = 0.1 < 0.8)
    /// 2. 12% = 0.12 (compounding = 0.232 < 0.8)
    /// 3. 60% = 0.6 (compounding = 0.9712 >= 0.8)
    ///
    /// Returning (3, 0.9712), thus the finally returned probability can be bigger than 1
    let accumulativeChance successRate =
        let mutable currentOdd = 0.0
        let mutable iterations = 0
        while currentOdd < successRate do
            let odd = currentOdd + 1.0
            currentOdd <- 1.0 - odd * (1.0 + rand.NextDouble())
            iterations <- iterations + 1
        (iterations, currentOdd)

    let createTimer timerInterval eventHandler =
        let timer = new System.Timers.Timer(float timerInterval)
        timer.AutoReset <- true
        timer.Elapsed.Add eventHandler
        timer.Start()

open System
open WorkItem
[<StructuredFormatDisplay("{Date} - {FastTime}")>]
type TimeReference() =
    let time = DateTime.UtcNow
    let now = Environment.TickCount
    member x.FastTime = now
    member x.Date = time
    static member (-) (a : TimeReference, b : TimeReference) = TimeSpan.FromMilliseconds (float (a.FastTime - b.FastTime))

[<EntryPoint>]
let main argv =
    let workers = [createWorker "Bob"; createWorker "Alice"]
    WorkItem.firstAvailableWorkItemCreator workers
    Console.ReadLine() |> ignore
    0
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.