doctor - an automatic doctor scheduler

ABOUT THIS TOOL

This is an automatic doctor scheduling tool. This tool is mainly written for my wife. Hence, the basic assumptions and request types are tailored for the hospital where my wife is working.

In this tool, a hospital has branches, places, and doctors. Usually, doctors may need to be on duty in different branches on different dates. A place is a unit that belongs to some branch and needs a doctor on duty everyday. A slot is a pair of a date and a place, which is a basic unit that may require one doctor on duty. A slot is open if it really requires exactly one doctor on duty. A doctor may make requests for duty days. For example, the doctor may request for no duty days on some dates or in some branches.

All the configurations of the hospital and the schedule can be specified in a plain text file. With the configuration file as an input, this tool will try to find a satisfiable assignment. Usually not all the doctors' requests can be satisfied. It is the user's talent to adjust the requests to find a satisfiable assignment. In this tool, two real examples are included.

By default, the duty days of a doctor falls in the following range:
  (floor(number of slots / number of doctors) - duty days error,
   ceil(number of slots / number of doctors) + duty days error)
where "duty days error" is a configurable option. This tool tries to average the duty weekdays and the duty weekends of all doctors. There is a duty point system in this tool. That is, a duty weekday, a duty Saturday, and a duty Sunday can have different duty points. With the duty points configured, this tool will also try to average the duty points of doctors in the following range:
  (floor(number of duty points / number of doctors) - duty points error,
   ceil(number of duty points / number of doctors) + duty points error)
where
  number of duty points =
    number of weekday slots * weekday points +
    number of Saturday slots * Saturday points +
    number of Sunday slots * Sunday points

Technically, this tool creates arithmetic constraints in the Yices SMT (Satisfiability Modulo Theories) solver based on the configuration and the doctor's requests. If Yices finds a satisfiable model, then we find an arrangement satisfying all the constraints.

SCREENSHOTS

The results of a schedule in January 2011 are shown below. There are two branches, 13 places, 17 doctors, and 60 open slots. The real names are masked.

Requests

Schedule Table

The results of a schedule in March 2011 are shown below. There are 73 open slots and many more requests.

Requests

Schedule Table

REQUIREMENTS

Due to the license of Yices, the Yices binaries and libraries are neither distributed nor linked statically with this tool. Hence, the dynamic library of Yices is required to be installed before running this tool. The Yices dynamic library can be found in http://yices.csl.sri.com/.

• Yices 1.0.29 with GMP dynamically linked
• GMP dynamic libraries

DOWNLOAD

For Mac OS X: doctor-1.0-mac.tar.gz

For Linux: doctor-1.0-linux.tar.gz

For Windows: doctor-1.0-win.zip

INSTALLATION

For Mac OS X

1. Install MacPorts: You can find the MacPorts package from its website. By default, MacPorts will be installed to /opt/local.
2. Install gmp:
1. Open a terminal.
2. Execute the command "sudo port install gmp".
3. Install Yices: Download the Yices binary with GMP dynamically linked: "Mac OS X Leopard (version 10.5), and Mac OS X Snow Leopard (version 10.6), for Intel, compiled in 64bit mode". Extract libyices.dylib to /opt/local/lib.
4. Extract doctor-1.0-mac.tar.gz.  Before running this tool in a terminal, execute "export DYLD_LIBRARY_PATH=/opt/local/lib" first.

For Linux

1. Install gmp: The name of the gmp package may vary on different Linux distributions.
2. Install Yices: Download the Yices binary with GMP dynamically linked for Linux. Extract libyices.so to /usr/local/lib.
3. Extract doctor-1.0-linux.tar.gz.

For Windows

1. Extract dotor-1.0-win.zip.
2. Download the Yices binary with GMP dynamically linked for "Cygwin (32bit Intel Pentium)". Extract cygyices.dll to the same folder of this tool.

USAGE


This tool can be invoked by the following command:

  doctor FILE

where FILE is a configuration file of the schedule. In the configuration file, the configurable options are divided into the following sections: Options, Branches, Places, Doctors, Slots, and Requests. The C-like and OCaml-like multi-line comments can be used. For example,
  /* This is a C-like multi-line
     comments */
  (* This is a OCaml-like multi-line
     comments *)

The C-like and BASH-like line comments can also be used. For example,
  // This is a C-like line comment.
  # This is a BASH-like line comment.

From now, we will use INT for an integer, NAME for an alphanumeric name or a string enclosed by double quotes, DAY for a set of days in a month, and OP for arithmetic operators. DAY can be a single day INT, a range INT-INT, or a day in the week. The day in the week can be Mon, Tue, Wed, Thu, Fri, Sat, or Sun. OP can be <, <=, >, >=, or =.

Options Section

This section is used to set global options. The options are explained below.

year = INT

   Set the target year of the schedule.

month = INT

  Set the target month of the schedule.

points = INT INT INT

  Set the duty points of weekdays, Saturdays, and Sundays. If this option is
  absent, the point system will not be used.

point-error = INT

  Set the error of the average duty points.

day-error = INT

  Set the error of the average duty days.

weekend-error = INT

  Set the error of the average duty weekends.

rest = INT

  Set the minimum number of days that a doctor can take a rest after a duty day.

Branches Section

This section is used to set the branches of the hospitabl. The syntax of a branch is:

  id = NAME, name = NAME

where id is the unique identity of the branch and name is the full name of the branch.

Places Section

This section is used to set the places of the hospitabl. The syntax of a place is:

  id = NAME, name = NAME, branch = NAME

where id is the unique identity of the place, name is the full name of the place, and branch is the branch that the place belongs to.

Doctors Section

This section is used to set the doctors of the hospitabl. The syntax of a doctor is:

  id = NAME, name = NAME

where id is the unique identity of the doctor and name is the full name of the doctor.

Slots Section

This section is used to set the open slot in the schedule. As a reminder, a slot is open if it needs exactly one doctor on duty. The syntax of slots is:

  day INT : NAME ... NAME
  ...
  day INT : NAME ... NAME

Each entry "day i : n1 ... nm" specifies the open slots (i, n1), ..., (i, nm) where i is the i-th day in the month and n1, ..., and nm are places in the hospital.

Requests Section

This section is used to set the doctor's requests. The requests can be in different forms which are explained below.

never doctor = NAME ... NAME, day = DAY ... DAY

  The doctors do not want to be on duty on all the specified days.

never doctor = NAME ... NAME, branch = NAME ... NAME

  The doctors do not want to be on duty in all the specified branches.

never doctor = NAME ... NAME, place = NAME ... NAME

  The doctors do not want to be on duty in all the specified places.

never doctor = NAME ... NAME, day = DAY ... DAY, branch = NAME ... NAME

  The doctors do not want to be on duty on the specified days and in the
  specified branches.

never doctor = NAME ... NAME, day = DAY ... DAY, place = NAME ... NAME

  The doctors do not want to be on duty on the specified days and in the
  specified places.

must doctor = NAME ... NAME, day = DAY ... DAY

  There must be at lease one of the doctors on duty on at lease one of the days.

must doctor = NAME ... NAME, branch = NAME ... NAME

  There must be at lease one of the doctors on duty in at lease one of the
  branches.

must doctor = NAME ... NAME, place = NAME ... NAME

  There must be at lease one of the doctors on duty in at lease one of the
  places.

must doctor = NAME ... NAME, day = DAY ... DAY, branch = NAME ... NAME

  There must be at lease one of the doctors on duty for at lease one combination
  of the days and the branches.

must doctor = NAME ... NAME, day = DAY ... DAY, place = NAME ... NAME

  There must be at lease one of the doctors on duty for at lease one combination
  of the days and the places.

days doctor = NAME ... NAME, num OP INT

  Add the constraint on the duty days for every specified doctor.

days doctor = NAME ... NAME, INT OP num OP INT

  Specify the duty days of the doctors in a range. The OP here can only be < or
  <=. For example, the entry
    days doctor = doctor_1 ... doctor_x, n <= num <= m
  is equivalent to
    days doctor = doctor_1 ... doctor_x, num >= n
    days doctor = doctor_1 ... doctor_x, num <= m

points doctor = NAME ... NAME, num OP INT

  Add the constraint on the duty points for every specified doctor.

points doctor = NAME ... NAME, INT OP num OP INT

  Specify the duty points of the doctors in a range. The OP here can only be <
  or <=. For example, the entry
    points doctor = doctor_1 ... doctor_x, n <= num <= m
  is equivalent to
    points doctor = doctor_1 ... doctor_x, num >= n
    points doctor = doctor_1 ... doctor_x, num <= m

together doctor = NAME, doctor = NAME

  The two doctors must be on duty on the same day and in the same branch for all
  days in the month.

together doctor = NAME, doctor = NAME, day = DAY ... DAY

  The two doctors must be on duty on the same day and in the same branch for the
  specified days.