Job Sequencing Problem in Kotlin

by

The job sequencing problem is a classic optimization problem in computer science, operations research, and related fields. It involves scheduling a set of jobs to be processed on a single machine or multiple machines, subject to various constraints and objectives.

In the basic version of the problem, each job has a processing time, a deadline, and a penalty cost if it is not completed by its deadline. The objective is to find a schedule that minimizes the total penalty cost. This is known as the “minimization problem” version of the job sequencing problem.

Another version of the problem involves maximizing the total profit earned by completing jobs within their deadlines. In this case, each job has a profit associated with it, and the objective is to find a schedule that maximizes the total profit. This is known as the “maximization problem” version of the job sequencing problem.

There are various algorithms and heuristics that have been developed to solve the job sequencing problem, including greedy algorithms, dynamic programming, and branch-and-bound techniques. The problem has applications in scheduling, project management, production planning, and other areas of operations management.

Example :

val jobs = listOf(
             Job("J1", 4, 20),
             Job("J2", 1, 10),
             Job("J3", 1, 40),
             Job("J4", 1, 30)
             )
  • Job("J1", 4, 20): This job has an ID of “J1”, a deadline of 4 units, and a profit of 20.
  • Job("J2", 1, 10): This job has an ID of “J2”, a deadline of 1 unit, and a profit of 10.
  • Job("J3", 1, 40): This job has an ID of “J3”, a deadline of 1 unit, and a profit of 40.
  • Job("J4", 1, 30): This job has an ID of “J4”, a deadline of 1 unit, and a profit of 30.

We want to find the maximum profit that can be earned by completing these jobs within their deadlines. To solve this problem, we can use the findMaxProfit function:

Kotlin
data class Job(val id: String, val deadline: Int, val profit: Int)

fun findMaxProfit(jobs: List<Job>): Int {
    // Sort the jobs in descending order of profit
    val sortedJobs = jobs.sortedByDescending { it.profit }

    // Find the maximum deadline among all the jobs
    val maxDeadline = sortedJobs.maxByOrNull { it.deadline }?.deadline ?: 0

    // Initialize an array to keep track of available slots
    val slots = BooleanArray(maxDeadline)

    // Iterate over the sorted jobs and assign them to the first available slot
    var totalProfit = 0
    for (job in sortedJobs) {
        for (i in job.deadline - 1 downTo 0) {
            if (!slots[i]) {
                slots[i] = true
                totalProfit += job.profit
                break
            }
        }
    }
    return totalProfit
}

This function sorts the jobs in descending order of profit, so the jobs are processed in the following order:

  1. Job("J3", 1, 40): This job has the highest profit, so it is processed first. Since its deadline is 1 unit, it must be completed within the first unit. The function assigns this job to the first available slot (i.e., the first unit), so it earns a profit of 40.
  2. Job("J4", 1, 30): This job has the next highest profit, so it is processed next. However, the first slot is already occupied by Job("J3", 1, 40), so this job cannot be completed within its deadline. Therefore, the function skips this job and moves on to the next one.
  3. Job("J2", 1, 10): This job has the lowest profit, so it is processed last. However, the first slot is still occupied by Job("J3", 1, 40), so this job also cannot be completed within its deadline. Therefore, the function skips this job and moves on to the next one.
  4. Job("J1", 4, 20): This job has a deadline of 4 units, so it can be completed at any time before the fourth unit. The function assigns this job to the first available slot after Job("J3", 1, 40) (i.e., the second unit), so it earns a profit of 20.

Therefore, the total profit earned by completing the scheduled jobs is 40 + 20 = 60. This is the maximum profit that can be earned by completing the jobs within their deadlines.

Kotlin
data class Job(val id: String, val deadline: Int, val profit: Int)

fun findMaxProfit(jobs: List<Job>): Int {
    // Sort the jobs in descending order of profit
    val sortedJobs = jobs.sortedByDescending { it.profit }

    // Find the maximum deadline among all the jobs
    val maxDeadline = sortedJobs.maxByOrNull { it.deadline }?.deadline ?: 0

    // Initialize an array to keep track of available slots
    val slots = BooleanArray(maxDeadline)

    // Iterate over the sorted jobs and assign them to the first available slot
    var totalProfit = 0
    for (job in sortedJobs) {
        for (i in job.deadline - 1 downTo 0) {
            if (!slots[i]) {
                slots[i] = true
                totalProfit += job.profit
                break
            }
        }
    }
    return totalProfit
}
fun main() {
    // Example jobs
    val jobs = listOf(
        Job("J1", 4, 20),
        Job("J2", 1, 10),
        Job("J3", 1, 40),
        Job("J4", 1, 30)
    )

    // Find the maximum profit that can be earned by completing the jobs
    val maxProfit = findMaxProfit(jobs)

    // Print the result
    println("Maximum profit: $maxProfit")
}

Output : Maximum profit: 60

Leave a Comment