Lab Assignment

Implementation of a simple greedy method to optimally solve the two-stage production (flow) scheduling problem.


1. a. Suppose you have several baskets of laundry to wash and dry, but only one washer and one dryer. For each basket of laundry, you know the number of minutes to wash and the number of minutes to dry.

b. To implement Johnson’s rule efficiently, it is convenient to first order the baskets with a sort that uses the smaller of the two times for each basket as the key. You may do the sort in any way you wish, but you are encouraged to use qsort() from the standard C library. The actual implementation of Johnson’s rule should take linear time.

2. a. Write a C program to read the two times for each basket, perform the sort, then apply Johnson’s rule, and finally print details of the schedule. The first line of the input will be n, the number of baskets. Each of remaining n lines will contain a pair of non-negative integers for a basket’s washing and drying times. The baskets will have indices from 0 to n - 1 to correspond to the order in which they are read.

b. The schedule should be printed with one output line per basket with the following details in this order: index, washing time, drying time, start time on the washer, start time on the dryer. Note that the schedule starts at time 0. If the dryer is ever idle between two baskets, you should print a line that indicates when the gap starts and finishes. After printing the entire schedule, you should print the makespan.

Getting Started:

1. A few observations:

a. The baskets will be processed in the same order on both the washer and dryer.

b. Any ties, in terms of identical processing times, may be broken arbitrarily without affecting the makespan obtained.

c. A basket may not be dried until 1) it has been completely washed and 2) the previous basket has been completely dried.

d. In principle, some of the baskets for the dryer could be delayed to eliminate the gaps without increasing the makespan.
Your solution should not have such delays.

2. It is convenient to get an optimal permutation of the basket indices before attempting to compute and print the required output.

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

#include <stdio.h>
#include <stdlib.h>

// Structure to hold data for a basket
struct basket
int index; // index of the basket
int washTime; // washing time
int dryTime; // drying time
int minTime; // minimum of two times

int min(int a, int b)
if (a < b)
return a;
return b;

// Comparing function that qsort will use for comparison of two baskets
// returns:...
$18.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available C-Family Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats