A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system

作者：Shabtay Dvir^*; Bensoussan Yaron; Kaspi Moshe

来源：International Journal of Production Economics, 2012, 136(1): 67-74.

DOI：10.1016/j.ijpe.2011.09.011

• Just-in-time scheduling
• Flow shop
• Controllable processing times
• Resource allocation
• Pseudo-polynomial time algorithm
• FPTAS

We analyze a two-machine flow-shop scheduling problem in which the job processing times are controllable by the allocation of resources to the job operations and the resources can be used in discrete quantities. We provide a bicriteria analysis of the problem where the first criterion is to maximize the weighted number of just-in-time jobs and the second criterion is to minimize the total resource consumption cost. We prove that although the problem is known to be NP-hard even for constant processing times, a pseudo-polynomial time algorithm for its solution exists. In addition, we show how the pseudo-polynomial time algorithm can be converted into a two-dimensional fully polynomial approximation scheme for finding an approximate Pareto solution.

• 出版日期2012-3