Competitive Project Scheduling on Two Unbounded Parallel Batch Machines
- PDF / 413,984 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 80 Downloads / 197 Views
Competitive Project Scheduling on Two Unbounded Parallel Batch Machines Ling-Fa Lu1
· Li-Qi Zhang2
Received: 21 February 2017 / Revised: 5 July 2017 / Accepted: 9 October 2017 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany 2017
Abstract This paper considers competitive project scheduling on two unbounded parallel batch machines. There are two competing firms, and each firm has an unbounded parallel batch machine. All projects must be performed in batches by Firms 1 and 2 on their machines, respectively. The profit that each firm obtains from each project depends on whether the firm finishes the job before or after its competitor. In the first problem, given a feasible schedule for Firm 1, the objective is to find an optimal schedule to maximize the total reward for Firm 2 under the given schedule for Firm 1. The corresponding total reward for Firm 1 is called the worst-case total reward of the given schedule for Firm 1. In the second problem, the objective is to find an optimal schedule for Firm 1 to maximize the worst-case total reward. We provide optimal algorithms for the two problems, respectively. Keywords Project scheduling · Competition · Parallel batch machine Mathematics Subject Classification 90B35
This research was supported in part by the National Natural Science Foundation of China (Nos. 11771406, 11571321 and U1504103).
B
Ling-Fa Lu [email protected] Li-Qi Zhang [email protected]
1
School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
2
College of Information and Management Science, Henan Agricultural University, Zhengzhou 450003, China
123
L.-F. Lu, L.-Q. Zhang
1 Introduction Scheduling is one of the most widely researched areas of operational research in recent 50 years, which is largely due to the rich variety of different problem types in the field. However, little research has been done on scheduling problems in competitive environments. In practice, multiple companies have to compete over raw materials, processing resources, final products and the same group of customers. Thus, it is very necessary to consider competitions in many scheduling problems. Specially, Averbakh and Lebedev [1] pointed out that competitive issues are becoming increasingly important in technology management, namely, in the context of planning projects related with development of new technological products. Quite common situation is where two or more competing companies are developing a new product or a group of products, and profits of a company depend significantly on whether or not it finishes developing the products ahead of its competitors. Generally, a project can be represented as a number of activities. Thus, it is realistic to assume that to develop the final products, all companies should perform similar activities (which may include developing intermediate products), and the profit that a company gets from performing an activity depends on whether it finishes the activity before
Data Loading...
