As an emerging technology, human-robot collaboration (HRC) has been implemented to enhance the performance of assembly lines and improve the safety of human workers. By integrating the advantages of human workers and collaborative robots (cobots), HRC enables production systems to process tasks consecutively, concurrently, or collaboratively. However, the introduction of cobots also makes the corresponding human-robot collaborative assembly line balancing problem more complex and difficult to solve. To solve this problem, we first propose an enhanced mixed integer program (EMIP) with various enhancement techniques and tighter bounds, and then, we develop an improved combinatorial Benders decomposition algorithm (Algorithm ICBD) with new local search strategies, Benders cuts, and acceleration procedures. To verify the effectiveness of our proposed model and algorithms, we conduct extensive computational experiments, and the results show that our proposed EMIP model is significantly better than the existing mixed integer program model; the percentages of instances that can obtain feasible and optimal solutions are increased from 82.42% to 100% and from 29.17% to 43.5%, respectively, whereas the average gap is decreased from 19.81% to 5.64%. In addition, our proposed Algorithm ICBD can get 100% of feasible solutions and 65.92% of optimal solutions for all of the test instances, and the average gap is only 1.49%. Moreover, compared with existing Benders decomposition methods for this problem, our approach yields comparatively better solutions in notably shorter average computational time when run in the same computational environment. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This research was supported by the National Natural Science Foundation Council of China [Grants 72401214, 92167206, 7221101377, 72471169, and 72231005], the Ministry of Education of China [Grant 24YJC630078], and Computation and Analytics of Complex Management Systems (Tianjin University). This research was also supported by the Tianjin Natural Science Foundation Project [Grant 23JCQNJC01900] and the Tianjin Philosophy and Social Science Planning Project [Grant TJGL21-016]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0279 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0279 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Consider n independent jobs and m uniform machines in parallel. Each job has a processing requirement and a deadline. All jobs are available for processing at time t = 0. Job j must complete its processing before or at its deadline and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines. We present a polynomial-time algorithm that given a feasible set of jobs, constructs a schedule that minimizes the total completion time Σ C j . In the classical α | β | γ scheduling notation, this problem is referred to as Qm | prmt , d¯ j | Σ C j . It is well known that a generalization of this problem with regard to its machine environment results in an NP-hard problem.

Consider n independent jobs and m identical machines in parallel. Job j has a processing time p j and a deadline $\bar{d}_j$. It must complete its processing before or at its deadline. All jobs are available for processing at time t=0 and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines; such a schedule is called a feasible schedule. Given a feasible set of jobs, our goal is to find a schedule that minimizes the total completion time $\sum C_j$. In the classical $\alpha \mid \beta \mid \gamma$ scheduling notation this problem is referred to as $P \mid prmt, \bar{d}_j \mid \sum C_j$. Lawler (Recent Results in the Theory of Machine Scheduling, in Mathematical Programming: The State of the Art, A. Bachem, M. Grötschel, and B. Korte, eds., Springer, Berlin, 1982, pp. 202-234) raised the question of whether or not the problem is NP-hard. In this paper we present a polynomial-time algorithm for every $m \ge 2$, and we show that the more general problem with m unrelated machines, i.e., $R \mid prmt, \bar{d}_j \mid \sum C_j$, is strongly NP-hard.

We consider the problem of scheduling n jobs without precedence constraints on m uniform machines (i.e., the machines are identical except for speed), with preemptions allowed at no cost. We are interested in generating the entire tradeoff curve of schedules which are Pareto-optimal (undominated) for the flowtime and makespan objectives. To achieve this, we first develop an O(mn) algorithm that produces a schedule with minimum flowtime, subject to a fixed makespan deadline. This algorithm alternates between the Shortest Processing Time on Fastest Machine (SPT-FM) rule and the Longest Remaining Processing Time on Fastest Machine (LRPT-FM) rule. We then investigate how the behavior of the algorithm changes as the deadline is varied parametrically. Our knowledge of the structure of optimal schedules allows us to characterize breakpoints on the (piecewise linear) tradeoff curve, and then to compute all of the O(mn) breakpoints in O(m3n) time. Our analysis yields various useful sensitivity results as a by-product. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.