Order acceptance and scheduling on parallel machines with setup time and machine-eligibility constraints

Abstract

Integration of order acceptance and scheduling on unrelated parallel machines is a joint decision problem, and arise from the multi-variety customized production environment, which usually has the following characteristics. First, there are a number of parallel machines (production lines), each of which can only produce a limited variety of products referred as the machine-eligibility constraint. Second, the processing technologies of various machines differ; thus, these parallel machines are unrelated. Third, because the machines are unrelated, the setup time of an order is related not only to the order sequence but also to the machine used, which is called a sequence-and machine-dependent setup time. To minimize total cost, this study investigates the scheduling problems posed by order acceptance and unrelated parallel machines with setup time and machine-eligibility constraints. In this problem, an order has two options, rejection or acceptance. If an order is rejected, it generates a rejection cost. Otherwise, the order process must be completed before the due date, or there will be a tardiness cost. Therefore, the total cost spent is calculated as the sum of the total rejection cost of rejected orders and total weighted tardiness cost of accepted orders. To solve this problem, the effect of rejecting an order on the total cost was analyzed, and a list of rejecting methods and rejection rules were proposed. Furthermore, a cooperative coevolving genetic algorithm (CCGA) was developed. In this CCGA, an encoding scheme was proposed that divides chromosomes into two subsets corresponding to the order list and order assignment. Moreover, a list-rejecting-based decoding procedure was presented for deciding rejection for a chromosome. As the two subsets are independent of each other and their evolutionary constraints are essentially different, a cooperative coevolution strategy was applied to evolve the subpopulations of these subsets using partheno-genetic and traditional genetic operators. Computational experiments on a large set of randomly generated instances were performed to verify the effectiveness and efficiency of this algorithm. Additionally, the impacts of problem size and rejection cost were studied experimentally. The results reveal that in the majority of cases characterized by various problem sizes and rejection costs, the proposed algorithm performs effectively and efficiently.

Keywords

• order acceptance and scheduling
• unrelated parallel machines
• setup time
• machine-eligibility constraint
• genetic algorithm
• cooperative coevolution