factory has n jobs 1, 2, . . . , n to be processed, each requiring one day of processing time. There are two machines available. One can handle one job at a time and process it in one day, whereas the
other can process two jobs simultaneously and complete them both in one day. The jobs are subject to precedence constraints represented by a binary relation ≺, where i ≺ j signifies that job i must be
completed before job j is started. The objective is to complete all the jobs while minimizing d1 + d2, where di is the number of days during which machine i is in use. Formulate this problem as one of finding a maximum matching in a suitably defined graph.