Non-permutation flowshop scheduling with dual resources

• Non-permutation flowshop scheduling with dual resource constraints is proposed.
• A mathematical model and three search algorithms based on tabu search are developed.
• Algorithm performs well with 2% deviation from optimal solution in small problems.
• Effectiveness and efficiency of developed algorithms have inverse relation.
• Non-permutation algorithms perform better than permutation algorithm.

Typically, in order to process jobs in a flowshop both machines and labor are required. However, in traditional scheduling problems, labor is assumed to be plentiful and only machine is considered to be a constraint. This assumption could be due to the lower cost of labor compared to machines or the complexity of dual-resource constrained problems. In this paper a mathematical model is developed to minimize the work-in-process inventory while maximizing the service level in a flowshop with dual resources. The model focuses on optimizing a non-permutation flowshop. There are different skill levels considered for labor and the setup times on machines are sequence-dependent. Jobs are allowed to skip one or more stages in the flowshop. Job release and machine availability times are considered to be dynamic. The problem is solved in two layers. The outer layer is a search algorithm to find the schedule of jobs on the machine (traditional flowshop scheduling problem) and the inner layer is a three-step heuristic to find a schedule of jobs on labor in accordance to the machine schedule. Three different search algorithms are developed to solve the proposed NP-hard problem. First algorithm can solve a permutation flowshop while the other two are developed to solve a non-permutation flowshop. The comparison between the optimal solution and the search algorithms in small examples shows a good performance of the algorithms with an average deviation of only 2.00%. An experimental design analyzes the effectiveness and efficiency of the algorithms statistically. The results show that non-permutation algorithms perform better than the permutation algorithm, although the former are less efficient. The effectiveness and efficiency in all three algorithms have an inverse relation. To the best of our knowledge, this research is the first of its kind to provide a comprehensive mathematical model for dual resource flowshop scheduling problem.