## Synchronizing Schedules for Transportation

Read this article. It discusses synchronizing transportation schedules. Because the logistics segment of the cycle is a large-scale effort, the waiting and queues are magnified. How many different modes of transportation do you think are required to make a product from raw material to the customer's hand?

### 4. Single Machine Assembly Scheduling Problem with random delay

#### 4.2 NP-completeness proof

To prove the assembly scheduling problem is NP-hard, it is reduced to a single machine scheduling problem with distinct due windows and job dependent earliness/tardiness penalty weights. The reduced problem is then proved to be NP-hard. Thus, the assembly scheduling problem investigated in this chapter is also NP-hard. In the following, the equivalence is established between the reduced problem and the problem studied by Wan & Yen, which is NP-hard.

**The reduced problem: **For the present discussion, the air
transportation cost and time is ignored, as well as the final delivery earliness
penalties. This is equivalent to say that these parameters take value zero.
Therefore, the problem basically becomes a scheduling problem with distinct
due-windows and job dependent earliness/tardiness penalty weights for each job.
The due-window has a length equal to the difference between the final customer
delivery time and transportation departure time.

**Distinct due-windows:** There is waiting cost if an order completed
earlier than its assembly due date. As there is no earliness cost for final
delivery, only tardiness cost is taken into account if the order is delivered
later than the final due-date. Also, it is assumed that the air transportation
cost and time are ignored. Therefore, the assembly of orders completed between
assembly due-date and final due-date lead to no penalty. It is obvious that the
number of flights corresponds to the number of due-dates for assembly. Thus,
the assembly due-date is distinct. In addition, the final due-date of each
order is distinct. Hence the reduced problem is a distinct due windows
scheduling problem.

**Job dependent earliness penalty**: If assembly of a job is completed
earlier than its due date, there is a waiting penalty, which depends on the
product of the early time and the quantity of the job.

**Job dependent tardiness penalty**: As assumed that if an order is
delivered later than its final due date, a late delivery penalty, which is the
product of lateness time length and the order quantity, is incurred.

Wan & Yen show that the single machine scheduling problem with distinct due windows to minimize total weighted earliness and tardiness is NP-hard. As the reduced assembly scheduling problem is equivalent to the problem studied by Wan & Yen, the prior problem is NP-hard. Therefore, the assembly scheduling problem studied in this chapter is NP-hard.