Application of chance-constrained programming for stochastic group shop scheduling problem

作者：Ahmadizar Fardin^*; Ghazanfari Mehdi; Ghomi Seyyed Mohammad Taghi Fatemi

来源：International Journal of Advanced Manufacturing Technology, 2009, 42(3-4): 321-334.

DOI：10.1007/s00170-008-1594-2

• Group shops scheduling
• Uncertain release dates and processing times
• Total weighted completion time
• Chance-constrained programming
• Ant colony algorithm
• Heuristic algorithm

In this paper, we study a group shop scheduling (GSS) problem subject to uncertain release dates and processing times. The GSS problem is: a general formulation including the other shop scheduling problems such as the flow shop, the job shop, and the open shop scheduling problems. The objective is to find a job schedule which minimizes the total weighted completion time. We solve this problem based on the chance-constrained programming. First, the problem is fomulated in a form of stochastic programming and then prepared in a form of deterministic mixed binary integer linear programming such that it can be solved by a linear programming solver. To solve the problem efficiently, we develop an efficient hybrid method. Exploiting a heuristic algorithm in order to satisfy the constraints, an ant colony optimization algorithm is applied to construct high-quality solutions to the problem. The proposed approach is tested on instances where the random variables are normally, uniformly, or exponentially distributed.

• 出版日期2009-5