This paper studies the on-line supply chain scheduling problem for single machine with multiple customers under the constraint of the unlimited number of vehicles but limited vehicle capacity. The customers place their orders on-line, which means that no information of future jobs is known beforehand. The jobs are processed on a single machine and then delivered to the customers by vehicles. Every vehicle can only contain the jobs of the same customer and every batch has the same fixed cost. The objective of the scheduling is to minimize the total makespan and the total delivery cost. Such a problem is called on-line problem. An on-line algorithm for the problem is designed, which is proved to be 2 + 2-competitive. The paper also presents a case study for demonstrating the robustness and efficiency of the algorithm.
展开▼
