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.