In this study, a single machine batch-scheduling problem with incompatible jobs and dynamic arrivals is examined. The objective function is the minimization of the total flow time of the jobs. For solving problems a case specific branch and bound algorithm with a heuristic upper bound scheme and two alternative lower bound procedures is used. An extensive computational experiment is conducted to investigate the effects of certain parameters on the computation time. For the most difficult parameter combination branch and bound algorithm can solve the problems about 25 jobs with 4 different job types in a 10 minutes time on average. For the problem types with higher number of jobs and the most difficult parameter combination proposed upper bound heuristic can be used to obtain near optimal solutions.

Scheduling in the context of manufacturing systems has become increasingly impor- tant in order for organizations to achieve success in dynamic and competitive scenarios. Scheduling can be described as allocation of available jobs over resources to meet the performance criteria defined in a domain. Our research work fo cuses on scheduling a given set of three-dimensional cylindrical items, each characterized by width wj , height hj, and depth dj , onto parallel non-identical rectangular heat treatment kilns, such that the capacities of the kilns is optimally used. The problem is strongly NP-hard as it generalizes the (one-dimensional) Bin Packing Problem (1BP), in which a set of n positive values wj has to be partitioned into the minimum number of subsets so that the total value in each subset does not exceed the bin capacity W. The problem has been formulated as a variant of the 3D-BPP by following the MILP approach, and we propose a weight optimization heuristic that produces solutions comparable to that of the LP problem, in addition to reducing the computational complexity. Finally, we also propose a Decomposition Algorithm (DA) and validate the perfor- mance effectiveness of our heuristic. The numerical analyses provides useful insights that influence the shop-floor decision making process.