Title: Order acceptance and scheduling in a parallel machine environment with weighted completion time

Authors: Venkata Prasad Palakiti; Usha Mohan; Viswanath Kumar Ganesan

Addresses: Department of Management Studies, Indian Institute of Technology Madras, Chennai, India ' Department of Management Studies, Indian Institute of Technology Madras, Chennai, India ' Decision Science and Algorithm lab, Tata Consultancy Systems Limited, Chennai 600036, India

Abstract: This paper studies the order acceptance and scheduling (OAS) problem in an identical parallel machine environment where orders are characterised by their revenues, processing times and weights. A mixed integer linear programming (MILP) model is presented for the problem with the objective of maximising the revenue minus the scheduling cost. The problem is NP- hard and a branch and bound (B&B) algorithm is developed to solve the problem. An extension of the B&B algorithm is proposed to solve very large problem instances to obtain ε-optimal solutions. The B&B algorithm and the extended B&B are evaluated for their performances against the solutions obtained by solving the MILP problem formulation using CPLEX solver through computational experiments. [Received 15 June 2017; Revised 2 February 2018; Accepted 10 March 2018]

Keywords: order acceptance; scheduling; parallel machines; branch and bound algorithm; B&B.

DOI: 10.1504/EJIE.2018.093631

European Journal of Industrial Engineering, 2018 Vol.12 No.4, pp.535 - 557

Published online: 30 Jul 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article