Task Scheduling Algorithms in C: Min-Min, Max-Min, Max-Max, Min-Max & More
Task Scheduling Algorithms in C
1. Min-Min Algorithm
#include
#includevoid main() {
int nT, nM; // number of tasks, number of machines
printf("\nEnter the number of machines and tasks: ");
scanf("%d%d", &nM, &nT);// Declare a 2D array of size nM x nT
// Data should be in the following format:
// T1 T2 T3
// M1 | 140 | 20 | 60 |
// M2 | 100 | 100 | 70 |
int min_min[nM][nT];
int tmp[nM][nT];
int makespan = 0;printf("\nFill Data:\n");
for (int i = 0; i < nM; i++) {
for (int j = 0; j < nT; j++) {
scanf("%d", &min_min[i][j]);
tmp[i][j] = min_min[i][j];
}
}// Visualize data
printf("\nOriginal Data:\n");
for (int i = 0; i < nM; i++) {
for (int j = 0; j < nT; j++) {
printf("%d ", min_min[i][j]);
}
printf("\n");
}// This array will hold the answer
int result_task[nT];
int result_machine[nT];
int result_time[nT];
int ptr = -1; // Indicates if the result set is full or notwhile (ptr < nT - 1) {
int time[nT], machine[nT]; // stores minimum time w.r.t machine of each task
for (int j = 0; j < nT; j++) {
int minimum = INT_MAX;
int pos = -1;
for (int i = 0; i < nM; i++) {
if (min_min[i][j] < minimum) {
minimum = min_min[i][j];
pos = i;
}
}
time[j] = minimum;
machine[j] = pos;
}// Now we find task with the minimum time
int minimum = INT_MAX;
int pos = -1;
for (int j = 0; j < nT; j++) {
if (time[j] < minimum) {
minimum = time[j];
pos = j;
}
}ptr++;
result_task[ptr] = pos;
result_machine[ptr] = machine[pos];
result_time[ptr] = tmp[machine[pos]][pos];if (minimum > makespan)
makespan = minimum;// Resetting states
for (int i = 0; i < nM; i++) {
for (int j = 0; j < nT; j++) {
if (j == result_task[ptr])
min_min[i][j] = INT_MAX;
else if (i == result_machine[ptr] && min_min[i][j] != INT_MAX)
min_min[i][j] += minimum;
else
continue;
}
}
}// Printing the answer
printf("\nScheduled Tasks are:\n");
for (int i = 0; i < nT; i++) {
printf("Task %d runs on Machine %d with Time %d units\n", result_task[i] + 1, result_machine[i] + 1, result_time[i]);
}
printf("\nMakespan : %d units\n", makespan);
}
2. Max-Min Algorithm
#include
#includevoid main() {
int nT, nM; // number of tasks, number of machines
printf("\nEnter the number of machines and tasks: ");
scanf("%d%d", &nM, &nT);// Declare a 2D array of size nM x nT
// Data should be in the following format:
// T1 T2 T3
// M1 | 140 | 20 | 60 |
// M2 | 100 | 100 | 70 |
int max_min[nM][nT];
int tmp[nM][nT];
int makespan = 0;printf("\nFill Data:\n");
for (int i = 0; i < nM; i++) {
for (int j = 0; j < nT; j++) {
scanf("%d", &max_min[i][j]);
tmp[i][j] = max_min[i][j];
}
}// Visualize data
printf("\nOriginal Data:\n");
for (int i = 0; i < nM; i++) {
for (int j = 0; j < nT; j++) {
printf("%d ", max_min[i][j]);
}
printf("\n");
}// This array will hold the answer
int result_task[nT];
int result_machine[nT];
int result_time[nT];
int ptr = -1; // Indicates if the result set is full or notwhile (ptr < nT - 1) {
int time[nT], machine[nT]; // stores minimum time w.r.t machine of each task
for (int j = 0; j < nT; j++) {
int minimum = INT_MAX;
int pos = -1;
for (int i = 0; i < nM; i++) {
if (max_min[i][j] < minimum) {
minimum = max_min[i][j];
pos = i;
}
}
time[j] = minimum;
machine[j] = pos;
}// Now we find the task with maximum time
int maximum = INT_MIN;
int pos = -1;
for (int j = 0; j < nT; j++) {
if (time[j] > maximum && time[j] != INT_MAX) {
maximum = time[j];
pos = j;
}
}ptr++;
result_task[ptr] = pos;
result_machine[ptr] = machine[pos];
result_time[ptr] = tmp[machine[pos]][pos];if (maximum > makespan) {
makespan = maximum;
}// Resetting states
for (int i = 0; i < nM; i++) {
for (int j = 0; j < nT; j++) {
if (j == result_task[ptr]) {
max_min[i][j] = INT_MAX;
} else if (i == result_machine[ptr] && max_min[i][j] != INT_MAX) {
max_min[i][j] += maximum;
} else {
continue;
}
}
}
}// Printing the answer
printf("\nScheduled Tasks are:\n");
for (int i = 0; i < nT; i++) {
printf("Task %d runs on Machine %d with Time %d units\n", result_task[i] + 1, result_machine[i] + 1, result_time[i]);
}
printf("\nTotal elapsed time : %d units\n", makespan);
}
3. Max-Max Algorithm
#include
#includevoid main() {
int nT, nM; // number of tasks, number of machines
printf("\nEnter the number of machines and tasks: ");
scanf("%d%d", &nM, &nT);// Declare a 2D array of size nM x nT
// Data should be in the following format:
// T1 T2 T3
// M1 | 140 | 20 | 60 |
// M2 | 100 | 100 | 70 |
int max_min[nM][nT];
int tmp[nM][nT];
int makespan = 0;printf("\nFill Data:\n");
for (int i = 0; i < nM; i++) {
for (int j = 0; j < nT; j++) {
scanf("%d", &max_min[i][j]);
tmp[i][j] = max_min[i][j];
}
}// Visualize data
printf("\nOriginal Data:\n");
for (int i = 0; i < nM; i++) {
for (int j = 0; j < nT; j++) {
printf("%d ", max_min[i][j]);
}
printf("\n");
}// This array will hold the answer
int result_task[nT];
int result_machine[nT];
int result_time[nT];
int ptr = -1; // Indicates if the result set is full or notwhile (ptr < nT - 1) {
int time[nT], machine[nT]; // stores maximum time w.r.t machine of each task
for (int j = 0; j < nT; j++) {
int maximum = INT_MIN;
int pos = -1;
for (int i = 0; i < nM; i++) {
if (max_min[i][j] > maximum) {
maximum = max_min[i][j];
pos = i;
}
}
time[j] = maximum;
machine[j] = pos;
}// Now we find task with the maximum time
int maximum = INT_MIN;
int pos = -1;
for (int j = 0; j < nT; j++) {
if (time[j] > maximum) {
maximum = time[j];
pos = j;
}
}ptr++;
result_task[ptr] = pos;
result_machine[ptr] = machine[pos];
result_time[ptr] = tmp[machine[pos]][pos];if (maximum > makespan)
makespan = maximum;// Resetting states
for (int i = 0; i < nM; i++) {
for (int j = 0; j < nT; j++) {
if (j == result_task[ptr])
max_min[i][j] = INT_MIN;
else if (i == result_machine[ptr] && max_min[i][j] != INT_MIN)
max_min[i][j] += maximum;
else
continue;
}
}
}// Printing the answer
printf("\nScheduled Tasks are:\n");
for (int i = 0; i < nT; i++) {
printf("Task %d runs on Machine %d with Time %d units\n", result_task[i] + 1, result_machine[i] + 1, result_time[i]);
}
printf("\nMakespan : %d units\n", makespan);
}
4. Min-Max Algorithm
#include
#includevoid main() {
int nT, nM; // number of tasks, number of machines
printf("\nEnter the number of machines and tasks: ");
scanf("%d%d", &nM, &nT);// Declare a 2D array of size nM x nT
// Data should be in the following format:
// T1 T2 T3
// M1 | 140 | 20 | 60 |
// M2 | 100 | 100 | 70 |
int min_max[nM][nT];
int tmp[nM][nT];
int makespan = 0;printf("\nFill Data:\n");
for (int i = 0; i < nM; i++) {
for (int j = 0; j < nT; j++) {
scanf("%d", &min_max[i][j]);
tmp[i][j] = min_max[i][j];
}
}// Visualize data
printf("\nOriginal Data:\n");
for (int i = 0; i < nM; i++) {
for (int j = 0; j < nT; j++) {
printf("%d ", min_max[i][j]);
}
printf("\n");
}// This array will hold the answer
int result_task[nT];
int result_machine[nT];
int result_time[nT];
int ptr = -1; // Indicates if the result set is full or notwhile (ptr < nT - 1) {
int time[nT], machine[nT]; // stores minimum time w.r.t machine of each task
for (int j = 0; j < nT; j++) {
int maximum = INT_MIN;
int pos = -1;
for (int i = 0; i < nM; i++) {
if (min_max[i][j] > maximum) {
maximum = min_max[i][j];
pos = i;
}
}
time[j] = maximum;
machine[j] = pos;
}// Now we find task with minimum time
int minimum = INT_MAX;
int pos = -1;
for (int j = 0; j < nT; j++) {
if (time[j] < minimum && time[j] != INT_MIN) {
minimum = time[j];
pos = j;
}
}ptr++;
result_task[ptr] = pos;
result_machine[ptr] = machine[pos];
result_time[ptr] = tmp[machine[pos]][pos];if (minimum > makespan)
makespan = minimum;// Resetting states
for (int i = 0; i < nM; i++) {
for (int j = 0; j < nT; j++) {
if (j == result_task[ptr])
min_max[i][j] = INT_MIN;
else if (i == result_machine[ptr] && min_max[i][j] != INT_MIN)
min_max[i][j] += minimum;
else
continue;
}
}
}// Printing the answer
printf("\nScheduled Tasks are:\n");
for (int i = 0; i < nT; i++) {
printf("Task %d runs on Machine %d with Time %d units\n", result_task[i] + 1, result_machine[i] + 1, result_time[i]);
}
printf("\nMakeSpan time : %d units\n", makespan);
}
5. Suffrage Heuristic Algorithm
#include
#include
#define MAX_SIZE 100void displayInputs(int sh[MAX_SIZE][MAX_SIZE], int nt, int nv) {
printf("\n");
for (int i = 0; i < nt; i++)
printf(" T%d", i + 1);
printf("\n");
for (int i = 0; i < nv; i++) {
for (int j = 0; j < nt; j++) {
printf("%5d", sh[i][j]);
}
printf(" V%d\n", i + 1);
}
printf("\n");
}void getTranspose(int sh[MAX_SIZE][MAX_SIZE], int nt, int nv, int transpose[MAX_SIZE][MAX_SIZE]) {
for (int i = 0; i < nt; i++) {
for (int j = 0; j < nv; j++) {
transpose[i][j] = sh[j][i];
}
}
}int getTaskIndex(int sh[MAX_SIZE][MAX_SIZE], int nt, int nv) {
int transpose[MAX_SIZE][MAX_SIZE];
getTranspose(sh, nt, nv, transpose);
int subs[MAX_SIZE];
for (int i = 0; i < nt; i++) {
int temp[MAX_SIZE];
for (int j = 0; j < nv; j++)
temp[j] = transpose[i][j];
// Sorting the array
for (int k = 0; k < nv - 1; k++) {
for (int l = 0; l < nv - k - 1; l++) {
if (temp[l] > temp[l + 1]) {
// swap
int temp_swap = temp[l];
temp[l] = temp[l + 1];
temp[l + 1] = temp_swap;
}
}
}
subs[i] = temp[1] - temp[0];
}
// Finding the index of the maximum element
int maxIndex = 0;
for (int i = 1; i < nt; i++) {
if (subs[i] > subs[maxIndex]) {
maxIndex = i;
}
}
return maxIndex;
}void updateSH(int sh[MAX_SIZE][MAX_SIZE], int nt, int nv, int taskIndex, int vmIndex) {
int addedTime = sh[vmIndex][taskIndex];
for (int i = 0; i < nt; i++)
sh[vmIndex][i] += addedTime;
for (int i = 0; i < nv; i++)
sh[i][taskIndex] = INT_MAX;
}int main() {
int sh[MAX_SIZE][MAX_SIZE];
int nt, nv;
int machines[MAX_SIZE] = {0};
printf("Enter number of tasks: ");
scanf("%d", &nt);
printf("Enter number of machines: ");
scanf("%d", &nv);
for (int i = 0; i < nv; i++) {
for (int j = 0; j < nt; j++) {
int tmp;
printf("Enter for task %d VM %d: ", j + 1, i + 1);
scanf("%d", &tmp);
sh[i][j] = tmp;
}
}
displayInputs(sh, nt, nv);
for (int i = 0; i < nt; i++) {
int taskIndex = getTaskIndex(sh, nt, nv);
int transpose[MAX_SIZE][MAX_SIZE];
getTranspose(sh, nt, nv, transpose);
int vmIndex = 0;
for (int j = 1; j < nv; j++) {
if (transpose[taskIndex][j] < transpose[taskIndex][vmIndex]) {
vmIndex = j;
}
}
printf("T%d in V%d takes %d time\n", taskIndex + 1, vmIndex + 1, transpose[taskIndex][vmIndex]);
machines[vmIndex] += transpose[taskIndex][vmIndex];
updateSH(sh, nt, nv, taskIndex, vmIndex);
}
printf("\nTotal time taken: %d\n", machines[0]); // Assuming single-machine scenario
return 0;
}
6. Tic-Tac-Toe
#include
#include
#include
#define SIZE 3// Function to initialize the game board
void initializeBoard(char board[SIZE][SIZE]) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
board[i][j] = ' ';
}
}
}// Function to print the game board
void printBoard(char board[SIZE][SIZE]) {
printf("\n");
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
printf(" %c ", board[i][j]);
if (j < SIZE - 1)
printf("|");
}
printf("\n");
if (i < SIZE - 1) {
for (int k = 0; k < SIZE * 4 - 1; k++) {
printf("-");
}
printf("\n");
}
}
printf("\n");
}// Function to check if the given player has won
int checkWin(char player, char board[SIZE][SIZE]) {
// Check rows and columns
for (int i = 0; i < SIZE; i++) {
if ((board[i][0] == player && board[i][1] == player && board[i][2] == player) ||
(board[0][i] == player && board[1][i] == player && board[2][i] == player)) {
return 1; // Player wins
}
}// Check diagonals
if ((board[0][0] == player && board[1][1] == player && board[2][2] == player) ||
(board[0][2] == player && board[1][1] == player && board[2][0] == player)) {
return 1; // Player wins
}return 0; // No win yet
}// Function to check if the board is full
int isBoardFull(char board[SIZE][SIZE]) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (board[i][j] == ' ') {
return 0; // Board is not full
}
}
}
return 1; // Board is full
}// Function to make a player's move
void makeMove(char player, char board[SIZE][SIZE]) {
int row, col;
printf("Enter your move (row and column, e.g., 1 2): ");
scanf("%d %d", &row, &col);
// Check if the chosen position is valid
while (row < 1 || row > SIZE || col < 1 || col > SIZE || board[row - 1][col - 1] != ' ') {
printf("Invalid move. Try again: ");
scanf("%d %d", &row, &col);
}
// Make the move
board[row - 1][col - 1] = player;
}// Function for the computer's move (simple random move)
void computerMove(char player, char board[SIZE][SIZE]) {
printf("Computer's move:\n");
int row, col;
srand(time(NULL));
// Generate random moves until an empty spot is found
do {
row = rand() % SIZE;
col = rand() % SIZE;
} while (board[row][col] != ' ');
// Make the move
board[row][col] = player;
}// Function to play the TIC-TAC-TOE game
void playTicTacToe() {
char board[SIZE][SIZE];
char player = 'X';
int gameStatus = 0; // 0: In progress, 1: Player wins, 2: Computer wins, 3: DrawinitializeBoard(board);do {
printBoard(board);
if (player == 'X') {
makeMove(player, board);
} else {
computerMove(player, board);
}
gameStatus = checkWin(player, board);
if (!gameStatus) {
if (isBoardFull(board)) {
gameStatus = 3; // Draw
} else {
player = (player == 'X') ? 'O' : 'X'; // Switch player
}
}
} while (!gameStatus);printBoard(board);switch (gameStatus) {
case 1:
printf("Congratulations! You win!\n");
break;
case 2:
printf("Computer wins. Better luck next time!\n");
break;
case 3:
printf("It's a draw!\n");
break;
}
}// Main function
int main() {
playTicTacToe();
return 0;
}
7. Alpha-Beta Pruning with Progressive Deepening
#include
#include#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))// Function to statically evaluate a node
int evaluateNode(char node) {
// Replace with your specific evaluation values
switch (node) {
case 'B':
return 2;
case 'C':
return 5;
case 'D':
return 4;
case 'E':
return 1;
case 'I':
return 3;
case 'K':
return 7;
case 'M':
return 8;
case 'N':
return 6;
// Add more cases if needed
default:
return 0; // Default case
}
}// Function to perform Alpha-Beta pruning with progressive deepening
int alphaBeta(char node, int depth, int alpha, int beta, int maximizingPlayer) {
if (depth == 0) {
return evaluateNode(node);
}// Replace with your logic to generate successors
char successors[] = {'B', 'C', 'D' /* Add more successors if needed */};// Order successors based on previous evaluations at depth d-1
// For simplicity, using a fixed order here. You may need to adapt this based on your game tree structure.
char orderedSuccessors[] = {'B', 'C', 'D' /* Add more ordered successors if needed */};if (maximizingPlayer) {
int value = INT_MIN;
for (int i = 0; i < sizeof(orderedSuccessors) / sizeof(orderedSuccessors[0]); i++) {
value = MAX(value, alphaBeta(orderedSuccessors[i], depth - 1, alpha, beta, 0));
alpha = MAX(alpha, value);
if (beta <= alpha) {
break; // Beta cut-off
}
}
return value;
} else {
int value = INT_MAX;
for (int i = 0; i < sizeof(orderedSuccessors) / sizeof(orderedSuccessors[0]); i++) {
value = MIN(value, alphaBeta(orderedSuccessors[i], depth - 1, alpha, beta, 1));
beta = MIN(beta, value);
if (beta <= alpha) {
break; // Alpha cut-off
}
}
return value;
}
}int main() {
char rootNode = 'A'; // Replace with your root node
int maxDepth = 4; // Replace with the maximum desired depthfor (int depth = 1; depth <= maxDepth; depth++) {
int result = alphaBeta(rootNode, depth, INT_MIN, INT_MAX, 1);
// Print results for each depth
printf("Depth %d: Best Move Value: %d\n", depth, result);
// Add logic to print ordered nodes and other required information
printf("\n");
}
return 0;
}
8. First-Come, First-Served (FCFS) Scheduling
#include#define MAX_PROCESSES 10// Process structure
typedef struct {
int id;
int arrival_time;
int burst_time;
} Process;// Function to calculate waiting time and turn around time for each process
void calculateTimes(Process processes[], int n, int waiting_time[], int turnaround_time[]) {
// Waiting time for first process is 0
waiting_time[0] = 0;// Calculate waiting time
for (int i = 1; i < n; i++) {
waiting_time[i] = waiting_time[i - 1] + processes[i - 1].burst_time;
}// Calculate turn around time
for (int i = 0; i < n; i++) {
turnaround_time[i] = waiting_time[i] + processes[i].burst_time;
}
}// Function to calculate average waiting time and average turn around time
void calculateAverageTimes(Process processes[], int n) {
int waiting_time[MAX_PROCESSES], turnaround_time[MAX_PROCESSES];
int total_waiting_time = 0, total_turnaround_time = 0;// Calculate waiting time and turn around time
calculateTimes(processes, n, waiting_time, turnaround_time);// Calculate total waiting time and total turn around time
for (int i = 0; i < n; i++) {
total_waiting_time += waiting_time[i];
total_turnaround_time += turnaround_time[i];
}// Calculate average waiting time and average turn around time
float avg_waiting_time = (float)total_waiting_time / n;
float avg_turnaround_time = (float)total_turnaround_time / n;// Display results
printf("Average Waiting Time: %.2f\n", avg_waiting_time);
printf("Average Turnaround Time: %.2f\n", avg_turnaround_time);
}int main() {
Process processes[MAX_PROCESSES];
int n;
printf("Enter the number of processes: ");
scanf("%d", &n);// Input process details
for (int i = 0; i < n; i++) {
printf("Enter arrival time and burst time for process %d: ", i + 1);
scanf("%d %d", &processes[i].arrival_time, &processes[i].burst_time);
processes[i].id = i + 1;
}// Calculate average waiting time and average turn around time
calculateAverageTimes(processes, n);return 0;
}