Online Work-Break Problem and its Competitive Analysis
Weimin Ma, Xiaodong Ji · Asia Pacific Journal of Operational Research · 2016
An original online problem with decreasing profit growth rate is proposed to optimize the work hours of employees, named the online work-break problem (WBP). In this problem, the manager has to answer for an abstract worker when he should have a break for his work efficiency declines with the durative time of work period. The efficiency of the worker is presented by a work efficiency function [Formula: see text] in the description of our problem. We present the online algorithms to solve the WBP based on linear estimation of [Formula: see text] under two levels. Both the problems with single-period and dynamic multi-periods have 2-competitive online algorithms.