How can a solution be represented in a job sequencing problem?

A solution can be represented in two main ways: as a variable-size subset of selected jobs (e.g.,

S1 = {J_1, J_4}

), or as a fixed-size binary vector where each position corresponds to a job and the value indicates whether the job is done (1) or not (0) (e.g.,

S2 = {1, 0, 0, 1}

Conditions

The problem involves selecting a subset of jobs from a given set.
The representation must clearly indicate which jobs are included in the solution.

Reasoning, step by step

Identify the set of all available jobs.
Method 1 (Subset): List the specific jobs chosen for the solution. The size varies based on the number of selected jobs.
Method 2 (Binary Vector): Create a vector of length equal to the total number of jobs. Set the bit to 1 if the corresponding job is selected, and 0 otherwise.
Verify that both representations convey the same selection information.

Example

For jobs $J_1$ , $J_2$ , $J_3$ , $J_4$ , selecting $J_1$ and $J_4$ can be written as $S1 = {J_1, J_4}$ (subset) or $S2 = {1, 0, 0, 1}$ (binary vector).

Common misconceptions

Assuming the binary vector size changes based on the number of selected jobs.
Confusing the order of jobs in the subset representation with the fixed positions in the binary vector representation.

Watch the explanation

YouTube7 Branch and Bound Introduction

0:55 – 1:38Watch this moment ↗

Explore next

Answers are generated from source material and independently checked. Consult the original video or creator if something is unclear.