Abstract: In recent decades, the applications of shared manufacturing resources have caught much interest. Manufacturing resource sharing provides a new service mode for various production industries, and efficientlyimproves the utilization of idle resources and customer satisfaction. Therefore, there has arisen a series of manufacturing sharing platforms in China. As a third-party service platform connecting customers and manufacturers, one sharing platform matches scattered and idle manufacturing resources with customized needs of customers. A satisfying manufacturing resources sharing plan, i.e., an efficient scheduling scheme, can not only reduce the production cost of enterprises, but also shorten the delivery times of customer orders. Thus, it is an interesting and important issue to provide sharing platforms with efficient scheduling schemes for completing any given customer orders. Motivated by the above observations, this work aims to depict the operation of a shared manufacturing platform,and produce an optimal or near optimal solution including resource utilization and order processing schedule. Taking 1688 Tao platform as an example, the sharing platform is described as one parallel machine scheduling problem with machine-order type matching and order splitting. Customers demand various types of products in their orders, in the sharing platform. The platform needs to select a subset of available machines (i.e., representing manufacturers) among idle machines, which have registered in the platform, to complete the given orders.Each machine can only process a few types of customized orders, and thus the selected machines must cover all types of the customer orders, ensuring that all the orders can be processed by the machines. For a given set of customer orders, the greater the number of orders a machine can process, the larger the processing capacity of the machine. It is also assumed that all the machines are of the same processing speed. There occurs a fixed processing or rental cost once any machine is used, and the cost is usually in accordance to the length of the planning time horizon, i.e., the time length of rental. Orders can also be split into sub-orders with integer lengths and processed on valid machines simultaneously.Therefore, the corresponding order can be completed and delivered sooner, resulting in a higher level of customer satisfaction.
This work focuses on the objective of minimizing the sum of total processing cost of machines used and total completion time of orders.We first establish an integer linear programming model for the considered problem, and give two fundamental properties of the problem. Furthermore, a theoretical lower bound is derived by relaxing the processing capabilities of the machines. With the relaxation, all the machines are able to process all types of orders. In this case the selection of machines reduces to the decision on the number of machines used. The commercial solver CPLEX is employed to generate optimal solutions for small-scale problem instances. For medium and large-scale instances, CPLEX cannot output even feasible solutions within a limited time. Therefore, a Capability-Based Greedy(abbr. CBG)heuristic and an improved Genetic Algorithm(abbr. GA)are proposed to solve the considered problem. The main idea of algorithm CBG is to select a subset of available machines one by one in an intuitively greedy mode until all the orders can be satisfied by the selected machines. The orders are then processed in the Shortest Processing Time(abbr. SPT)sequence. After the assignment of each order, it requires that the difference of workloads between the machines which are able to process the order is as small as possible, i.e., the difference is at most one. In the improved GA, the solution of CBG serves as one of the initial solutions so as to accelerate the iteration process. We also test various instances to determine the best parameter settings of GA. We carry out extensive numerical experiments. Numerical results show by comparing CBG and GA with the lower bound in small, medium and large scales that the performances of CBG and GA are very close to the exact method of CPLEX. With regard to running time, CPLEX consumes a lot of time, while both of CBG and GA run much faster than CPLEX does. Considering both solution quality and time consuming, CBG may be an efficient and effective method in producing a complete solution of machine selection and order processing schedule in practice, while GA provides slightly better solutions with more running time. In addition, the larger processing capabilities of machines indicate the smaller gap between the solutions of heuristic algorithms and the lower bound. It indicates that the sharing platform shall give priority to lease machines with largest processing capacities. On the other hand, it needs to balance the machine rental cost and the total work of orders to decide how many machines are to be used. If the rental cost of a machine is high, a smaller number of machines shall be selected for processing, and vice versa. One of future research issues is to develop more efficient algorithms, and considering the scenario with setup time is also an interesting variation.

Key words: scheduling, manufacturing resource sharing, parallel machines, order splitting, heuristic algorithm

摘要： 介绍了制造资源共享环境下共享平台的生产和运作,以1688淘平台为例,将共享平台抽象刻画为考虑可拆分订单和加工类型匹配的平行机调度问题。客户将订单下达到共享平台上,供应商将闲置机器放在平台的资源池里。不同机器具有相同的加工速度但只能加工与其类型匹配的个性化订单,因此,需要决策使用哪些机器。一旦使用某台机器,会产生固定的加工或租赁成本。每个订单可以被拆分成整数长度的多个子订单,并在可用的机器上同时被加工。以最小化所使用机器的总加工成本和订单的总完工时间之和为优化目标,建立了一个整数线性规划模型。对于小规模实例,CPLEX可以求得最优解;对于中规模和大规模例子,提出了基于机器加工能力的贪婪算法和遗传算法。数据实验表明,基于机器加工能力的贪婪算法是一种高效且有效的算法。此外,尽量选择加工能力强的机器加工订单;将订单拆分在多台机器上并行加工可以缩短订单的完成时间。

关键词: 调度, 制造资源共享, 平行机, 订单拆分, 启发式算法